REVIEW 3 major objections 5 minor 13 references
Unrolling a Graph-Laplacian Denoiser Realizes Only Compositions of Polynomial Graph Filters
T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read An unrolled graph-Laplacian denoiser with learned coefficients still realizes only polynomial graph filters.
desk verdict A sound negative result for unrolled graph denoisers—worth refereeing despite minor overreach in the abstract and missing code. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the polynomial graph filter, a map of the form $P(\Psi)$ with $\Psi$ the graph-Laplacian denoiser and $P$ a polynomial. The argument has three gears: (1) the TSE module forms a polynomial $t_K(\Psi)$ of degree at most $K$; (2) CG iterates stay in the Krylov subspace $\mathcal{K}_m(t_K(\Psi),y)$, so the solver contributes a polynomial of degree at most $m-1$ regardless of the learned step sizes; (3) composing the two bounds the degree by $K(m-1)$, and counting parameters (dimension $K+2m+1$ versus $\dim\mathcal{P}_{K(m-1)}=K(m-1)+1$) makes the reachable set thin. A fourth piece, Proposition 12, derives $\kappa(\Psi)>1+\mu$ from a sign test on a one-dimensional trigonometric sum, placing the required truncation order well above practice, and the Bernstein basis supplies a direct parameterization of the whole class with a structural nonexpansiveness guarantee.
What would settle it
Run the trained unrolled module on a basis of inputs $y_1,\dots,y_N$; if any output $x_m$ has a component outside $\operatorname{span}\{\Psi^j y_i:0\le j\le K(m-1)\}$, then Theorem 4 is false.
Extended reading notes
Core claim
The central discovery is Theorem 4: when the $m$-step CG module is run on $t_K(\Psi)x = y$ from $x_0 = 0$ with arbitrary fixed step sizes $\{\alpha_k\}$ and $\{\beta_k\}$, the output satisfies $x_m = P(\Psi)y$ with $\deg P \le K(m-1)$ for every setting of the learned coefficients. The proof runs by the Krylov-subspace invariance of CG: each iteration adds one multiplication by $t_K(\Psi)$, so the iterate lies in a Krylov subspace of dimension $m$, and composing the degree-$K$ polynomial $t_K$ with a degree-$(m-1)$ polynomial gives degree at most $K(m-1)$. Proposition 5 sharpens this: the reachable set is the image of a polynomial map from $\mathbb{R}^{K+2m+1}$, so when $K(m-2)>2m$ it is a strict, measure-zero subset of $\mathcal{P}_{K(m-1)}$; for $K=10,m=3$ the reachable dimension is at most 17 inside a 21-dimensional space. The paper further establishes closed-form behavior at initialization (a leaky denoiser with response $g_K(\lambda)=\lambda/(1-(1-\lambda)^{K+1})$, bounded below by $1/(K+1)$), a condition-number lower bound $\kappa(\Psi)>1+\mu$ for the shift-invariant case, and a Bernstein parameterization that spans the full polynomial class with a nonexpansiveness guarantee.
Load-bearing premise
The collapse theorem assumes the conjugate-gradient step sizes $\alpha_k,\beta_k$ are fixed scalars shared across all inputs; if they were allowed to depend on the residual, as in textbook CG, the map would still lie in a Krylov subspace for each input but would not be a single fixed polynomial in $\Psi$, and the central claim would not hold.
Editorial extensions
If this is right
- At any point of training, the unrolled TSE+CG module realizes exactly a polynomial graph filter of degree at most $K(m-1)$, and at $K=10,m=3$ the reachable set is a measure-zero subset of the degree-20 polynomial class, so learning the coefficients cannot cover that class.
- The standard initialization acts as a leaky denoiser: its spectral response $g_K(\lambda)$ lies above $\lambda$ for $\lambda<1$, approaches $1/(K+1)$ as $\lambda\to0^+$, and satisfies the error bound $\lVert x_{\mathrm{init}}-\Psi y\rVert_2 \le \frac{1}{K+1}\lVert y\rVert_2$, tight as $\lambda_{\min}\to0$.
- Because $\kappa(\Psi)>1+\mu$ and $\kappa(\Psi)\approx107$ at $\mu=100$ in the measurements, the condition (11) requires $K\ge488$ for accuracy $\varepsilon=10^{-2}$, far above the $K=10$ used in practice.
- The Bernstein parameterization spans all of $\mathcal{P}_d$, includes the target $\Psi$ exactly at zero approximation error, and offers a convex squared-error objective with a nonexpansiveness guarantee; the unrolled block's only advantage is its optimization path, not its reachable set.
- The collapse extends to stacked blocks sharing a common $\Psi$ (degree bound becomes $LK(m-1)$) and to $\ell^1$ priors with nonlinear shrinkage between blocks, while modules that re-estimate the graph per block leave the polynomial class.
Reading between the lines
- This paper's argument suggests a broader principle: any unrolled solver whose internal coefficients are input-independent constants and whose operator is fixed will produce maps lying in the polynomial algebra generated by that operator, so the same thinness may hold for unrolled proximal or ADMM loops, not only for conjugate gradient.
- If the only difference between parameterizations is conditioning rather than capacity, then reporting test accuracy alone is misleading; reporting the effective rank of the parameter-to-response Jacobian, as done here, would be a more meaningful comparison for unrolled networks.
- The condition-number bound implies that the truncation order must scale with the inverse of the graph's smallest eigenvalue, so any practical fixed-order construction either accepts large error or must let the graph or $\mu$ be estimated from data.
- A direct testable prediction: a larger unrolled block (higher $K$ or $m$) should not improve test PSNR beyond the corresponding Bernstein polynomial of the same degree on the same fixed graph, provided both receive sufficient optimization.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper analyzes a two-module unrolled graph denoiser: a truncated Taylor expansion (TSE) module that forms a system matrix from a graph-Laplacian denoising operator Ψ, followed by m conjugate-gradient steps with learned scalar coefficients. Theorem 4 proves that, for every setting of the learned coefficients, the end-to-end map is q_{m-1}(t_K(Ψ)), a polynomial in Ψ of degree at most K(m-1). Proposition 5 shows that this reachable set has dimension at most K+2m+1 and is therefore a measure-zero subset of P^{K(m-1)} whenever K(m-2)>2m. Proposition 7 derives a closed-form spectral response g_K in the exact-solve limit and shows it is bounded below by 1/(K+1); Proposition 9 gives a Bernstein basis spanning all polynomial filters with a structural nonexpansiveness guarantee; Proposition 12 proves a condition-number lower bound for shift-invariant graph weights. The paper concludes that the unrolled block does not enlarge the polynomial graph-filter class and compares the block against a direct Bernstein parameterization in small image-denoising experiments.
Significance. If its scope qualifications are made precise, this is a significant negative result for the algorithm-unrolling literature: it identifies a broad family of learned TSE+CG modules whose hypothesis space is provably confined to polynomial graph filters, and it quantifies that confinement as measure-zero within the nominal degree budget. The proof of Theorem 4 is a clean Krylov-subspace induction and is correct under the stated fixed-step assumption; Proposition 5's dimension count is valid; and Proposition 9 provides a useful convex baseline. The paper is also honest about its main idealizations, noting in the Fig. 2 caption that the finite-m initialization is far from an exact solve and that the closed-form response is not the m-step response. The numerical experiments are limited but adequate as an illustration. With the overstatements corrected, the result should be of interest to researchers designing and analyzing unrolled graph filters.
major comments (3)
- [§3 (Theorem 4, Remark 6)] The theorem is stated for 'arbitrary step sizes {α_k},{β_k}, learned or otherwise,' and Remark 6 explicitly scopes it to the unrolled regime in which these are constants shared across inputs. The manuscript does not, however, state whether the original architecture in [3] is in this regime. If [3] used textbook CG with residual-dependent steps, the end-to-end map is not a single fixed polynomial and Theorem 4 would not characterize that construction. Please add an explicit statement confirming that [3]'s unrolled CG uses fixed scalar step sizes, or alternatively narrow the introduction and abstract to the architecture defined in Section 2.
- [§4 (Prop. 7), §6, Abstract] Proposition 7 derives g_K under the condition 'If the CG module solves exactly,' so Eq. (8) is an exact-solve idealization. The abstract nevertheless says 'the realized spectral response is obtained in closed form,' and Section 6 states 'the realized gain is g_10(λ_min)=...' while the Fig. 2 caption acknowledges that at initialization the m=3 CG module is far from an exact solve and 'the response there is not g_K.' This is an internal inconsistency in how the closed form is presented. Please either report the actual degree-K(m−1) response at the initialization used in the experiments, or explicitly label Fig. 1 and the spectral-response paragraph as the exact-solve limit and remove 'realized' from the abstract and the contribution list.
- [§6, Title] The experimental network constructs Ψ from each input patch, so the end-to-end map is not a single fixed polynomial filter; Theorem 4 applies per operator. The conclusion's last sentence acknowledges this, but the title and the abstract's claim that 'the resulting map is a polynomial in the denoising operator' are likely to be read as a statement about a fixed hypothesis class. Please state the per-instance qualification in the abstract and in the numerical section, and clarify that the measure-zero statement of Proposition 5 concerns the reachable set for a fixed Ψ.
minor comments (5)
- [§6] The initialization of {α_k} and {β_k} is not specified, so the ablation is not fully reproducible; please give the default values or state that they are initialized randomly and describe the distribution.
- [Fig. 1 caption] The caption calls g_K(λ) of Eq. (8) the 'realized response'; it should be qualified as the exact-solve response, not the m-step response, to match Proposition 7 and the Fig. 2 caption.
- [§2 (Lemma 1)] The all-ones vector is written as 1 without definition; please define it near Eq. (3) for clarity.
- [§6 (Prop. 12)] The symbols p and q are used both as adjacency indices and as the test-vector index in x_p=(-1)^p; consider a less overloaded notation.
- [§1] The sentence 'this paper adds a proof of the correspondence' is slightly ambiguous: the graph-filter/denoiser correspondence already appears in [2], and what is new here is the collapse theorem for the unrolled block. Please rephrase to distinguish the new contribution from the quoted result.
Circularity Check
No circularity: the collapse theorem is proved from the defining equations of the architecture, and the numerical κ comparison is a derived bound versus a measured value, not a fitted input.
full rationale
The paper's central claim, Theorem 4, is a self-contained mathematical result. It proves by induction that m conjugate-gradient steps applied to A_K = t_K(Ψ) keep the iterates in Krylov subspaces, yielding x_m = q_{m-1}(A_K)y. Proposition 3 then shows, by a dimension argument, that t_K(Ψ) is a polynomial in Ψ of degree at most K. The composition therefore has degree at most K(m-1). The proof does not assume the conclusion; it uses only linearity of Ψ, the polynomial form of t_K, and the standard Krylov-subspace property of CG. Proposition 5's measure-zero statement follows from a parameter-counting bound on a semialgebraic image, not from any fitted quantity. The numerical 'prediction' of κ is a derived lower bound from equations (3) and (13), compared with a measured eigenvalue; no parameter is fitted to the measured κ, so the '0.34%' consistency check is not a fitted input renamed as a prediction. The paper cites the author's own prior work [3] to identify the architecture and [9] for a graph-estimation module, but neither citation is load-bearing: the theorem is proved from the defining equations (4)-(5) and the CG recursion, and the comparison class (Bernstein polynomials) is an external, long-established parameterization. The main scope caveat—fixed scalar CG step sizes shared across inputs (Remark 6)—is a limitation on the theorem's applicability, not a circular step. Overall, the derivation chain is self-contained and no circularity is present.
Assumptions & free parameters
free parameters (4)
- s (Taylor expansion center) =
initialized at 1, learned
- a_k (Taylor coefficients, k=0..K) =
initialized at (-1)^k, learned
- alpha_k (CG step sizes, k=0..m-1) =
learned
- beta_k (CG direction coefficients, k=0..m-2) =
learned
assumptions (6)
- domain assumption The graph denoiser Ψ = (I + μ L̃)^{-1} is symmetric, positive definite, and nonexpansive with spec(Ψ) subset of (0,1].
- domain assumption The system matrix equals Ψ^{-1} exactly.
- standard math The conjugate-gradient recursion with fixed step sizes keeps iterates in the Krylov subspace K_k = span{y, A_K y, ..., A_K^{k-1} y}.
- domain assumption For Proposition 12, the shift-invariant graph weight matrix factors as B = T ⊗ T when photometric variation is absent.
- standard math Sylvester's law of inertia: congruent symmetric matrices have the same number of negative eigenvalues.
- standard math Bernstein basis polynomials b_{j,d} are nonnegative, sum to 1 on [0,1], and span P_d.
Cite this review
Pith. "Pith review of Unrolling a Graph-Laplacian Denoiser Realizes Only Compositions of Polynomial Graph Filters." pith.science (2026). https://pith.science/paper/QBE34DYL
@misc{pith2026260809923,
author = {Pith},
title = {Pith review of: Unrolling a Graph-Laplacian Denoiser Realizes Only Compositions of Polynomial Graph Filters},
year = {2026},
howpublished = {\url{https://pith.science/paper/QBE34DYL}},
note = {Machine review of arXiv:2608.09923}
}
read the original abstract
A recent construction of unrolled networks for graph-based image restoration forms a system matrix from a graph-Laplacian denoiser through a truncated Taylor expansion, then inverts it with a fixed number of conjugate-gradient steps, with the coefficients of both stages learned. This paper shows the resulting map is a polynomial in the denoising operator, of degree at most the product of the two truncation orders, for every setting of those coefficients and therefore at every point of training: the learned steps select an element of a Krylov subspace they cannot enlarge. At the orders used in practice the reachable set is moreover a measure-zero subset of the polynomial class of the network's own degree budget, so the composition constrains the hypothesis space rather than enlarging it. At the standard initialization the realized spectral response is obtained in closed form, exceeding the intended response throughout the interior of the spectrum and approaching a nonzero floor. A lower bound on the operator's condition number, internal to the graph construction rather than to image content, then places the order required for a prescribed accuracy well above the order used in practice. The confining class is precisely the spectral graph filters for which a direct, convex parameterization has long been available.
Figures
Reference graph
Works this paper leans on
-
[3]
Constructing an interpretable deep denoiser by unrolling graph Laplacian regularizer,
S. A. Hosseini, T. T. Do, G. Cheung, and Y. Tanaka, “Constructing an interpretable deep denoiser by unrolling graph Laplacian regularizer,” inProc. IEEE Int. Conf. Image Process. (ICIP), 2024, pp. 1431–1437
work page 2024
-
[1]
Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,
V. Monga, Y. Li, and Y. C. Eldar, “Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,”IEEE Signal Process. Mag., vol. 38, no. 2, pp. 18–44, 2021
work page 2021
-
[2]
Performance Analysis of Plug-and-Play ADMM: A Graph Signal Processing Perspective
S. H. Chan, “Performance analysis of plug-and-play ADMM: A graph signal processing per- spective,”IEEE Trans. Comput. Imaging, vol. 5, no. 2, pp. 274–286, 2019, arXiv:1809.00020
work page Pith review arXiv 2019
-
[4]
Mixed graph signal analysis of joint image denoising / interpolation,
N. Viswarupan, G. Cheung, F. Lan, and M. Brown, “Mixed graph signal analysis of joint image denoising / interpolation,” inProc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2024, pp. 9431–9435
work page 2024
-
[5]
G. H. Golub and C. F. Van Loan,Matrix Computations, 4th ed. Johns Hopkins Univ. Press, 2013
work page 2013
-
[6]
The emerging field of signal processing on graphs,
D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs,”IEEE Signal Process. Mag., vol. 30, no. 3, pp. 83–98, 2013
2013
-
[7]
Wavelets on graphs via spectral graph theory,
D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,”Appl. Comput. Harmon. Anal., vol. 30, no. 2, pp. 129–150, 2011
work page 2011
-
[8]
Convolutional neural networks on graphs with fast localized spectral filtering,
M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” inAdv. Neural Inf. Process. Syst. (NeurIPS), 2016. 8
work page 2016
Show all 13 references
-
[9]
Interpretable deep image denoiser by unrolling graph Laplacian regularizer,
S. A. Hosseini, “Interpretable deep image denoiser by unrolling graph Laplacian regularizer,” MASc thesis, York University, Toronto, ON, Canada, 2025
2025
-
[10]
Deep graph Laplacian regularization for robust de- noising of real images,
J. Zeng, J. Pang, W. Sun, and G. Cheung, “Deep graph Laplacian regularization for robust de- noising of real images,” inProc. IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Workshops (CVPR W), 2019, pp. 1759–1768, arXiv:1807.11637
2019 arXiv
-
[11]
G. G. Lorentz,Bernstein Polynomials. Univ. of Toronto Press, 1953
1953
-
[12]
Blind estimation of white Gaus- sian noise variance in highly textured images,
M. Ponomarenko, N. Gapon, V. Voronin, and K. Egiazarian, “Blind estimation of white Gaus- sian noise variance in highly textured images,” inImage Processing: Algorithms and Systems XVI, IS&T Int. Symp. Electronic Imaging, 2018
2018
-
[13]
Piecewise polynomial, positive definite and compactly supported radial func- tions of minimal degree,
H. Wendland, “Piecewise polynomial, positive definite and compactly supported radial func- tions of minimal degree,”Adv. Comput. Math., vol. 4, pp. 389–396, 1995. 9
1995
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.