Graph Fourier Transform Based on $\ell_1$ Norm Variation Minimization

Anna Qi; Chao Huang; Jianfeng Huang; Lihua Yang

REVIEW 3 major objections 6 minor 15 references

Graph Fourier Transform Based on $\ell_1$ Norm Variation Minimization

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper defines an ℓ1-norm graph Fourier basis and proves its local minima have at most k distinct values, with a fast greedy basis.

desk verdict A correct and clean necessary condition for an l1 graph Fourier basis, but the greedy algorithm's core claim is supported only by small-N experiments and has no approximation guarantee. read the letter →

arxiv 1908.06672 v1 pith:Q2CBFOCK submitted 2019-08-19 cs.IT math.IT

Lihua Yang , Anna Qi , Chao Huang , Jianfeng Huang This is my paper · ORCID

classification cs.ITmath.IT MSC 94A1205C5090C26

keywords graphsignalprocessingFouriertransformℓ1normvariationgreedyalgorithmorthogonalbasispiecewiserepresentationnetworkdataanalysis

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a new definition of the graph Fourier transform whose basis vectors minimize $\ell_1$ norm signal variation instead of the $\ell_2$ variation that defines Laplacian eigenvectors. The central theoretical result is a necessary condition: at any local minimum of the $k$-th variation-minimization problem, the vector's entries take at most $k$ distinct values, so the $\ell_1$ basis orders graph frequencies from low to high just as Laplacian eigenvalues do. The paper then replaces the expensive continuous problem with a greedy partition algorithm that merges the two groups of vertices with largest mutual weight at each step, producing an orthonormal basis whose Fourier coefficients are computable in $O(N)$ time. Numerical experiments on graphs with up to eight vertices show the greedy basis has total $\ell_1$ variation close to the exact $\ell_1$ basis, and on simulated and real temperature signals its $n$-term approximation error decays at nearly the same rate as the Laplacian basis.

What carries the argument

The load-bearing object is the piecewise representation $x=Ma$: every signal is written as a sum of indicator vectors of the distinct-value sets, so the $\ell_1$ variation $S(x)$ becomes a locally linear function $f^{\top}a$ with coefficients $f_i = \sum_{j<i}W(A_i,A_j) - \sum_{j>i}W(A_i,A_j)$. The necessary condition $\dim\ker(U^{\top}M)=1$ is derived by linearizing $S$ around a local minimum and applying Lagrange multipliers on the sphere; it implies each local minimum is isolated and the search reduces to finitely many partition matrices. The greedy construction uses the partition sequence $\tau_k$ defined by $W(A,B)=\sum_{i\in A, j\in B} w_{ij}$, picking the pair with maximum mutual weight to merge, which yields a binary tree and an orthonormal basis with a fast $O(N)$ transform.

What would settle it

Compute the exact global $\ell_1$ basis for a connected weighted graph with nine or ten vertices, or for a known graph family, and compare the total $\ell_1$ variation $S(\tilde U)$ with $S(U)$; if the relative error is not small or grows with $N$, the greedy basis is not a reliable approximation. More directly, find a weighted graph on which some greedy basis vector $\tilde u_k$ does not attain the minimum of $S$ over the sphere orthogonal to the earlier greedy vectors.

Watch

Extended reading notes

Core claim

The paper's central claim is that the $\ell_1$ Fourier basis, defined by solving the sequence of problems (4), has a rigid combinatorial structure. Theorem 4 proves that if $x$ is a local minimum with piecewise representation $x=Ma$, where $M$ is the partition matrix, then $\dim\ker(U^{\top}M)=1$; Corollary 5 then gives the $k$-th basis vector at most $k$ distinct component values. The paper further constructs the greedy basis $\tilde U$ from a partition sequence that repeatedly merges the two existing groups with the largest mutual weight, proves in Theorems 8 and 9 that this basis is orthonormal and that each greedy vector is a critical point of the corresponding $\ell_1$ problem, and presents experiments suggesting that the greedy basis is a good approximation to the exact $\ell_1$ basis for $N\le 8$ and has approximation decay comparable to the Laplacian basis.

Load-bearing premise

The greedy merge rule is assumed to produce a basis close to the true $\ell_1$ Fourier basis on large graphs, but the paper tests this only by exhaustive search for graphs with at most eight vertices and gives no error bound.

Editorial extensions

If this is right

For small graphs ($N\le 8$) the exact $\ell_1$ Fourier basis can be obtained by enumerating the finite set $X^*_U$ of critical partition matrices, turning a continuous nonconvex problem into a discrete one.
The greedy basis transform costs $O(N)$ multiplications via the binary tree of merged groups, versus $O(N^2)$ for a dense Laplacian-basis transform, so it offers a faster spectral analysis for large graphs.
Because each greedy basis vector satisfies the same kernel-dimension condition as local minima, the greedy basis is a legitimate 'critical point' candidate for the $\ell_1$ problem, not an arbitrary heuristic.
The at-most-$k$-values property gives a frequency interpretation: as $k$ grows the basis vectors can take more distinct values, so the basis orders signals from slowly varying to rapidly oscillating.
In the reported experiments the $n$-term approximation error of the greedy basis decays at nearly the same rate as the Laplacian basis, supporting use of the greedy basis in compression and denoising.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The greedy merge rule is a one-pass hierarchical clustering of the graph by maximum mutual weight; one could test whether replacing the single merge criterion with a look-ahead or global-cut objective improves the basis for graphs with many vertices.
The necessary condition is not sufficient, so some critical points may have larger variation than the global minimum; a local-search step over nearby partitions might refine the greedy basis without losing its $O(N)$ transform.
The same piecewise-linear analysis should extend to the directed $\ell_1$ variation $\tilde S(x)=\sum w_{ij}(x_i-x_j)_+$, giving a directed greedy basis; the paper states the extension is straightforward but does not prove it.
On large graphs, comparing the greedy basis's $n$-term approximation to wavelet or frame-based graph transforms would clarify where its fast $O(N)$ transform wins or loses against other sparse representations.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper's real contribution is Theorem 4 / Corollary 5: the k-th vector in a sequential l1-variation-minimizing orthonormal basis must have at most k distinct values. The proof is correct, and this is a genuinely new necessary condition for a natural but hard problem. The finiteness of the critical set (around Theorem 6) is a nice byproduct. That part is worth knowing.

The rest of the paper is a greedy algorithm to approximate the l1 basis, and the evidence here is weaker than the claims. The algorithm merges groups with largest raw mutual weight and builds an orthonormal basis from the resulting hierarchy. Theorem 9 shows only that each greedy vector is a critical point of the relevant problem; the authors admit in the text that it need not be a local minimum. No error bound connects the greedy basis to the true l1 basis. Experiments are limited to N<=8 random geometric graphs, which do not probe failure modes like unbalanced clusters. For k=2, the exact u2 maximizes the normalized cut W(A,B)/sqrt(|A||B|), while the greedy partition comes from raw-weight merges. Those objectives differ, and a small relative variation error for small random graphs does not imply the greedy basis is close on larger or different graphs. The paper also skips any complexity analysis for building the greedy hierarchy (the O(N) transform applies only once the tree is known), and it does not compare against Sardellitti et al.'s SOC/PAMAL algorithms.

So the theoretical core is solid, but the central practical claim that the greedy basis is a good l1 Fourier basis is not backed by a proof or adequate experiments. I would still send this to peer review because the necessary condition is a real result and the algorithmic question matters, but the current version needs substantial revision, ideally with a study of where the raw-weight merge rule diverges from normalized cuts and a more convincing validation on larger, structured graphs.

Referee Report

3 major / 6 minor

Summary. The paper proposes an ℓ1-norm-based graph Fourier basis defined by sequentially minimizing S(x)=∑_{i<j} w_{ij}|x_i-x_j| under orthogonality and unit-norm constraints (Definition 1, Eq. (4)). Its main theoretical result, Theorem 4, proves a necessary condition for local minima: for the k-th minimization, the partition matrix M of a local minimum satisfies dim ker(U^T M)=1, leading to Corollary 5 that the k-th ℓ1 basis vector has at most k distinct values. The paper then introduces a greedy algorithm (Definition 7) that hierarchically merges the two groups with maximum raw mutual weight W(A,B), constructs an orthonormal basis ~U from the resulting partitions (Theorem 8), and shows that this basis satisfies the same dimension condition (Theorem 9), though the paper explicitly notes this makes ~u_k a critical point, not necessarily a local minimum. Numerical experiments for N≤8 random geometric graphs compare the greedy basis to the exactly enumerated ℓ1 basis, and a second experiment compares n-term approximation errors for a simulated signal and a real temperature signal under the greedy and Laplacian bases.

Significance. If the greedy basis provably approximated the ℓ1 Fourier basis, the paper would offer a fast, deterministic alternative to Laplacian eigenvector computation for graph Fourier transforms. The theoretical core—Theorem 4 and Corollary 5—is self-contained and appears mathematically correct: the piecewise-linearization argument and the Lagrange-multiplier step are sound, and the finiteness of critical points (Theorem 6 and the set X_U^*) is a genuine structural insight. Theorem 9 is a useful observation that connects the greedy construction to the necessary condition. The O(N) computation of Fourier coefficients from the greedy tree (Section 4.3, Eqs. (25)-(27)) is a concrete practical advantage, and the n-term approximation experiments on a real temperature signal provide some empirical support. However, the central algorithmic claim—that the greedy basis approximates the ℓ1 basis on large graphs—is not established by any approximation guarantee or error bound, and the numerical evidence is limited to N≤8. This gap is load-bearing for the paper's stated purpose, so the result, while potentially valuable, requires substantial additional support before the central claim can be accepted.

major comments (3)

[§4.2, Definition 7 (Eq. (18))] The greedy partition sequence merges the two groups with maximum raw mutual weight W(A,B), but for k=2 the exact ℓ1 basis vector u_2, by Corollary 5 and the zero-mean unit-norm constraint, maximizes the normalized cut W(A,B)/sqrt(|A||B|) (equivalently sqrt(N)W(A,B)/sqrt(|A|(N-|A|))). These two objectives are not equivalent: on graphs where the heaviest raw bipartition is unbalanced in size, or where early max-weight merges trap the hierarchy in an off-optimal pair, the greedy two-group cut can have substantially larger S(~u_2)-S(u_2). Figure 4(a) reports only averages over 100 random geometric graphs with N≤8; it does not probe worst-case or structured graphs, and no error bound is given. Since the abstract and introduction claim that the greedy algorithm 'approximates' the ℓ1 basis, this lack of guarantee leaves the central practical claim unsupported.
[§4.2, Theorem 9 and following remark] Theorem 9 shows only that the greedy partition matrix M satisfies dim ker(~U_{k-1}^T M)=1, which places ~u_k in the critical-point set X^*_{~U_{k-1}}, not among the local minima X^{**}_{~U_{k-1}}. The paper itself states this explicitly. Because the sequential problem (4) is nonconvex (unit-sphere constraint), being a critical point gives no quantitative control over the gap S(~u_k)-S(u_k) to the global minimum; the paper provides no lower or upper bound on this gap, nor any convergence or stability result as N grows. Thus the only theoretical bridge from the greedy construction to the ℓ1 basis is a necessary condition, not an approximation guarantee. This is a load-bearing point for the paper's main claim and needs either a bound or a clearly weakened claim.
[§4.3 and §5] The paper emphasizes that the greedy basis transform of a signal costs O(N) multiplications (Eqs. (25)-(27)), but it does not analyze the complexity of constructing the greedy hierarchy itself. In Definition 7, at each of the N-1 merging steps the algorithm must find the pair of current groups with maximum W(A,B); a naive implementation costs O(N^3) or more, and no data structure or amortized bound is given. Since the motivation is that 'computation of Laplacian eigenvectors is expensive when the graph is large,' the total cost of producing the greedy basis is relevant to the 'fast' claim. The absence of any complexity analysis for the construction step means the practical advantage over an eigensolver is not established.

minor comments (6)

[§6] The sentence 'We obtains a necessary condition' should read 'We obtain a necessary condition.'
[§2, Remarks] The phrase 'Most results can be generated to the directed case' should be 'generalized' rather than 'generated.'
[Figure 4 caption] The caption refers to red and blue lines; if the journal version is printed in grayscale, the distinct line styles should be indicated or labeled directly.
[§5.1, Figure 4(b)] The observation that r(~U,U) is below zero is interesting but should be discussed more carefully: since each u_k is only sequentially optimal, the sum of variations over the whole basis does not have to be minimized by the ℓ1 basis, so this fact does not contradict the definition.
[§5.2] The simulated signal is generated from its Laplacian-basis coefficients, which may bias the comparison in favor of the Laplacian basis; reporting results for a signal generated from greedy-basis coefficients or from a basis-independent random process would make the comparison more neutral.
[References] Reference [14] (Perraudin et al.) is formatted inconsistently with the other entries; the arXiv identifier and journal/volume information should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation is self-contained and the experimental claims rest on external enumeration benchmarks.

full rationale

The paper's derivation chain is self-contained and does not reduce to its inputs. The l1 Fourier basis is defined by a sequence of optimization problems in Definition 1, and Theorem 4 derives a necessary condition using only the local-minimum definition, Lemma 3, and a Lagrange multiplier argument; Corollary 5 then follows by a rank argument. The greedy basis in Theorem 8 is explicitly constructed by the merge rule of Definition 7, and Theorem 9 shows only that this construction satisfies the same necessary condition, with the paper itself noting that this makes the greedy vector a 'critical point' but 'not necessarily a local minimum'. No parameter is fitted to data and then renamed as a prediction. The numerical experiments compare the greedy basis against an independent external benchmark, the exact l1 basis obtained by exhaustive enumeration of X*_U for N<=8, and the n-term approximation experiments are empirical comparisons without tuned constants. The lack of an approximation guarantee for large graphs is a correctness or support limitation, not a form of circularity. There are no load-bearing self-citations, and no imported uniqueness theorem; the only cited related work, Sardellitti et al., is external and not used as a substitute for proof.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central mathematical results rest on standard optimization and graph assumptions. The only ad hoc element is the greedy merge rule, which is a heuristic choice without a proven optimality bound.

assumptions (4)

domain assumption G is a connected, undirected, weighted graph with nonnegative symmetric edge weights.
Stated in Section 2. Needed for S(x)>0 for non-constant x and for Laplacian eigen-decomposition to exist.
standard math The sequential minimization problem (4) has a global minimizer for each k.
S is continuous and the constraint set is a compact ellipsoid; existence follows from the extreme value theorem. The paper does not address non-uniqueness of minimizers.
standard math Lagrange multiplier necessary conditions apply at local minima of problem (13).
Used in the proof of Theorem 4. The constraint c'^T Q c' = 1 is a smooth manifold with nonzero gradient, so the first-order necessary condition holds.
ad hoc to paper Merging the two groups with maximum mutual weight yields a partition sequence whose associated orthonormal basis is close to the ℓ1 basis.
Definition 7 and Section 4.2. This is the core heuristic; no approximation guarantee is proven, only empirical support for N≤8.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Graph Fourier Transform Based on $\ell_1$ Norm Variation Minimization." pith.science (2026). https://pith.science/paper/Q2CBFOCK

@misc{pith2026190806672,
  author       = {Pith},
  title        = {Pith review of: Graph Fourier Transform Based on $\ell_1$ Norm Variation Minimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q2CBFOCK}},
  note         = {Machine review of arXiv:1908.06672}
}

abstract

The definition of the graph Fourier transform is a fundamental issue in graph signal processing. Conventional graph Fourier transform is defined through the eigenvectors of the graph Laplacian matrix, which minimize the $\ell_2$ norm signal variation. However, the computation of Laplacian eigenvectors is expensive when the graph is large. In this paper, we propose an alternative definition of graph Fourier transform based on the $\ell_1$ norm variation minimization. We obtain a necessary condition satisfied by the $\ell_1$ Fourier basis, and provide a fast greedy algorithm to approximate the $\ell_1$ Fourier basis. Numerical experiments show the effectiveness of the greedy algorithm. Moreover, the Fourier transform under the greedy basis demonstrates a similar rate of decay to that of Laplacian basis for simulated or real signals.

Figures

Figures reproduced from arXiv: 1908.06672 by the authors.

**Figure 1.** Relation between M∗ U , X ∗∗ U , X ∗ U and XU . Since X ∗ U is finite, to find the global minimum of problem PU , one way is to compute S(x) for all x in X ∗ U and pick out the largest one [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

**Figure 2.** In step k , we combine Ak and Bk of τk to get τk−1 . 4.2. Greedy basis The greedy partition sequence τk defined above yields a sequence of subspaces Vk := span {1A | A ∈ τk}, k = 1, . . . , N, (20) which satisfy the relations span 1 = V1 ⊂ V2 ⊂ · · · ⊂ VN = R N . (21) Denote the orthogonal complement of Vk−1 in Vk by Vk Vk−1 . By definition 7, the partition τk−1 is obtained by combining two groups Ak and Bk in τk . … view at source ↗

**Figure 3.** Binary tree of Ak and Bk in the above example [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Comparison of variation between different bases. [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]

**Figure 5.** Figure 5: n -term approximation under two bases. Red: Greedy basis. Blue: Laplacian basis. created by grouping the vertices according to their mutual weights. Numerical experiments show that the greedy basis provides a good approximation to the `1 basis. Also, the Fourier transf…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Fan R. K. Chung. Spectral graph theory. No. 92. American Mathematical Soc., 1997

work page 1997
[2]

The emerging ﬁeld of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains

David I. Shuman, et al. “The emerging ﬁeld of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.” IEEE Signal Processing Magazine 30.3 (2013): 83-98

work page 2013
[3]

On the graph fourier transform for directed graphs

Stefania Sardellitti, Sergio Barbarossa, and Paolo Di Lorenzo. “On the graph fourier transform for directed graphs.” IEEE Journal of Selected Topics in Signal Processing 11.6 (2017): 796-811

work page 2017
[4]

Discrete Signal Processing on Graphs

Aliaksei Sandryhaila, and Jose M F Moura. “Discrete Signal Processing on Graphs.” IEEE Transactions on Signal Processing 61.7 (2013): 1644-1656

work page 2013
[5]

Vertex-frequency analysis on graphs

David I. Shuman, Benjamin Ricaud, and Pierre Vandergheynst. “Vertex-frequency analysis on graphs.” Applied and Computational Harmonic Analysis 40.2 (2016): 260-291

work page 2016
[6]

Multiscale Wavelets on Trees, Graphs and High Dimen- sional Data: Theory and Applications to Semi Supervised Learning

Matan Gavish, Boaz Nadler, and Ronald R. Coifman. “Multiscale Wavelets on Trees, Graphs and High Dimen- sional Data: Theory and Applications to Semi Supervised Learning.” ICML. 2010

work page 2010
[7]

Wavelets on Graphs via Spectral Graph Theory

David K. Hammond, Pierre Vandergheynst, and Remi Gribonval. “Wavelets on Graphs via Spectral Graph Theory.” Applied and Computational Harmonic Analysis 30.2 (2011): 129-150

work page 2011
[8]

Unsupervised deep haar scattering on graphs

Xu Chen, Xiuyuan Cheng, and Stphane Mallat. “Unsupervised deep haar scattering on graphs.” Advances in Neural Information Processing Systems. 2014

work page 2014

Show all 15 references

[9]

Sparse representation on graphs by tight wavelet frames and applications

Bin Dong. “Sparse representation on graphs by tight wavelet frames and applications.” Applied and Computa- tional Harmonic Analysis 42.3 (2017): 452-479

2017
[10]

Discrete Signal Processing on Graphs: Sampling Theory

Siheng Chen, et al. “Discrete Signal Processing on Graphs: Sampling Theory.” IEEE Transactions on Signal Processing 63.24 (2015): 6510-6523

2015
[11]

A Spectral Graph Uncertainty Principle

Ameya Agaskar, and Yue M. Lu. “A Spectral Graph Uncertainty Principle.” IEEE Transactions on Information Theory 59.7 (2013): 4338-4356

2013
[12]

Convergence and energy landscape for Cheeger cut clustering

Xavier Bresson, et al. “Convergence and energy landscape for Cheeger cut clustering.” Advances in Neural Information Processing Systems. 2012

2012
[13]

A splitting method for orthogonality constrained problems

Rongjie Lai and Stanley Osher. “A splitting method for orthogonality constrained problems.” Journal of Scien- tiﬁc Computing 58.2 (2014): 431-449

2014
[14]

GSPBOX: A toolbox for signal processing on graphs

Nathana¨ el Perraudin et al. “GSPBOX: A toolbox for signal processing on graphs.” Eprint Arxiv 61.7(2016):1644- 1656

2016
[15]

http://www.meteoswiss.admin.ch/product/input/climate-data/normwerte-pro-messgroesse/np8110/ nvrep np8110 tre200m0 e.txt 17

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Fan R. K. Chung. Spectral graph theory. No. 92. American Mathematical Soc., 1997

work page 1997

[2] [2]

The emerging ﬁeld of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains

David I. Shuman, et al. “The emerging ﬁeld of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.” IEEE Signal Processing Magazine 30.3 (2013): 83-98

work page 2013

[3] [3]

On the graph fourier transform for directed graphs

Stefania Sardellitti, Sergio Barbarossa, and Paolo Di Lorenzo. “On the graph fourier transform for directed graphs.” IEEE Journal of Selected Topics in Signal Processing 11.6 (2017): 796-811

work page 2017

[4] [4]

Discrete Signal Processing on Graphs

Aliaksei Sandryhaila, and Jose M F Moura. “Discrete Signal Processing on Graphs.” IEEE Transactions on Signal Processing 61.7 (2013): 1644-1656

work page 2013

[5] [5]

Vertex-frequency analysis on graphs

David I. Shuman, Benjamin Ricaud, and Pierre Vandergheynst. “Vertex-frequency analysis on graphs.” Applied and Computational Harmonic Analysis 40.2 (2016): 260-291

work page 2016

[6] [6]

Multiscale Wavelets on Trees, Graphs and High Dimen- sional Data: Theory and Applications to Semi Supervised Learning

Matan Gavish, Boaz Nadler, and Ronald R. Coifman. “Multiscale Wavelets on Trees, Graphs and High Dimen- sional Data: Theory and Applications to Semi Supervised Learning.” ICML. 2010

work page 2010

[7] [7]

Wavelets on Graphs via Spectral Graph Theory

David K. Hammond, Pierre Vandergheynst, and Remi Gribonval. “Wavelets on Graphs via Spectral Graph Theory.” Applied and Computational Harmonic Analysis 30.2 (2011): 129-150

work page 2011

[8] [8]

Unsupervised deep haar scattering on graphs

Xu Chen, Xiuyuan Cheng, and Stphane Mallat. “Unsupervised deep haar scattering on graphs.” Advances in Neural Information Processing Systems. 2014

work page 2014