CS Paper Radar

Unrolling Lanczos for Ideal Low-pass Graph Filter Approximation

Parham Eftekhar, Gene Cheung, Mingxiao Liu, H. Vicky Zhao, Xuejun Han, Eugene Wen

eess.SP ·submitted 2026-09-24 06:13 UTC · v3
theory

Abstract

Low-pass (LP) filtering is a fundamental operation in graph signal processing (GSP). Among finite-order nodal-domain methods, Lanczos-based filtering provides more accurate approximations of ideal LP filters than Chebyshev polynomial methods. We show that the approximation of Lanczos filtering can be further improved through algorithm unrolling and data-driven parameter learning. The key insight is that, because ideal LP filtering is a projection operation into the low-frequency eigen-subspace $\cS_K$, instead of approximating individual eigen-pairs of a graph Laplacian $Ł$ as done in classical Lanczos, an unrolled Lanczos network can directly approximate $\cS_K$. Specifically, we first establish a theorem identifying properties of the Lanczos tridiagonal matrix $\T_m$ that promote accurate approximation of the low-frequency eigen-subspace $\cS_K$. Guided by this theory, we relax the orthogonality constraint on Lanczos vectors, resulting in Ritz vectors that better span $\cS_K$. To ensure numerical stability, we constrain $\T_m$ to be similar to a symmetric matrix, thereby guaranteeing real-valued eigenvalues. Experimental results on random graphs and learned graphs in two natural language processing (NLP) tasks show that our unrolled Lanczos network achieves superior ideal LP filter approximation compared to the classical Lanczos method.

Closest papers

Nearest neighbours by meaning across the whole index.

Unrolling a Graph-Laplacian Denoiser Realizes Only Compositions of Polynomial Graph Filters

eess.SP eess.IV ·2026-08-10 ·Seyed Alireza Hosseini
theory similarity 0.68
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.

0.04

A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation

cs.LG stat.MLstat.ME ·2026-09-06 ·Huan Qing
theoryhot direction similarity 0.62
Abstract · 24 pages

The Davis-Kahan theorem is a fundamental tool in spectral analysis, providing quantitative control over the distance between the eigenspaces of a symmetric matrix and its perturbation. However, when the matrix dimension is large, computing leading eigenvectors is computationally expensive, limiting the practical use of spectral methods in modern large-scale applications. This paper addresses this problem by proposing an independent Bernoulli sampling scheme and proves that the leading left singular vectors of the subsampled matrix faithfully approximate the target subspace of a low-rank symmetric matrix. Our main result is a subsampled Davis-Kahan bound that gives an explicit error bound depending directly on the sampling probability. The bound reveals the trade-off: the computational cost scales linearly with the sampling probability, while the statistical error scales as the inverse square root of the sampling probability. Our result thus extends the Davis-Kahan theorem to the subsampled setting, enabling scalable spectral analysis of large-scale symmetric matrices.

0.25

Deep Unrolling of Lanczos-based Laplacian Eigensolver for Crop Classification in Satellite Images

eess.SP ·2026-11-10 ·Parham Eftekhar, Gene Cheung
theory similarity 0.56
Abstract

Per-pixel crop classification in satellite images is an important pre-processing step in remote crop monitoring. Leveraging progress in signed graph signal processing, we build an interpretable and lightweight neural network for binary crop classification (e.g., corn versus non-corn) in two stages: i) learn a signed graph from data, and ii) unroll a Lanczos-based eigensolver to compute the eigenvector $\u_1$ associated with the smallest eigenvalue of a hybrid graph Laplacian $\cL$ for spectral clustering. Specifically, we first construct a near-balanced signed graph $\cG^s$, where signed edge weights $w_{i,j}\in(-1,1)$ are computed from learned feature distances $d_{i,j}$ via a hyperbolic tangent mapping. Given $\cG^s$, we estimate $\u_1$ by unrolling the Lanczos algorithm and use $\mathrm{sign}(\u_1)$ for binary classification. Mathematically, we develop a theorem establishing conditions under which $\u_1$ can be well approximated after finite Lanczos iterations. Motivated by this theorem, we relax the classical Lanczos orthogonality constraints during unrolling and optimize end-to-end classification performance while promoting the derived conditions for accurate eigenvector approximation. Experiments on real-world Harmonized Landsat-Sentinel imagery show classification performance comparable to state-of-the-art deep learning models while reducing parameters by up to two orders of magnitude.

0.23

Tight Convergence Bounds for the Classical Kaczmarz Method

cs.DS math.OCmath.NA ·2026-09-25 ·Runbo Yu, Jelena Diakonikolas
similarity 0.55
Abstract

The classical method of Kaczmarz, introduced in 1937, is a textbook iterative method for solving linear systems $A x = b.$ Despite its widespread use, particularly in the context of solving inverse problems where it is commonly included in software packages within Matlab, Python, and Julia, the precise characterization of convergence has long been deemed difficult to obtain. While different bounds on convergence rates have been established, they are largely unsatisfying as they cannot explain the classical, cyclic-update method's efficient convergence in practice. In this work, we obtain a tight characterization of convergence of the classical Kaczmarz method, establishing both linear and sublinear convergence bounds. The worst-case tight (i.e., exactly attained by some instances in the considered family) bounds are expressed in terms of a fixed matrix that depends only on $A,$ but are not fully interpretable in terms of the matrix spectrum and row correlations, which had been observed to have an impact on convergence. We thus provide relaxations of these bounds that are fully expressible in terms of matrix row norms, row correlations, rank, and extremal positive singular values. The provided relaxed bounds explain one-cycle convergence in special cases where the matrix rows are all either parallel or orthogonal to each other. We further argue that the dependence on different parameters appearing in the bounds is necessary and within a small constant factor of the best attainable in the worst case. Finally, our bounds explain why the classical cyclic update is faster than the randomized one when matrix rows are weakly correlated, which is often observed in inverse problems where the cyclic method is used.

0.53

A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture

cs.DS math.FA ·2026-09-16 ·Tarun Kathuria
similarity 0.55
Abstract · The author explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for t…

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.56

ST-GFM: Spectral-Temporal Graph Forecasting with Measured Perturbation Bounds and Masked Spectral Reconstruction

cs.LG eess.SPstat.ML ·2026-11-02 ·Aashish Bohra, Vivek Vijay
theory similarity 0.55
Abstract · 21 Pages, 11 Figures, 12 Tables, Supplementary Materials attached, Under Review

Graph forecasters for sensor networks are trained in one regime and deployed in others, where sensor coupling and signal frequency content both change. We split this spectral shift into an operator channel and a frequency channel, each with a dimensionless measure. ST-GFM (Spectral-Temporal Graph Forecasting Model) filters every input step with Chebyshev and bidirectional diffusion filters on one learned, non-symmetric operator and alternates them with per-node temporal attention. For the operator channel we prove Frobenius-norm perturbation bounds for both graph branches, show that the Chebyshev bound is attained to first order, and compute its constant from the trained weights and the measured operator norm: 17.9 on METR-LA and 21.5 on PEMS-BAY. Under random edge dropout the trained layer moves by 2.0% to 3.1% of this bound. Masked Spectral Reconstruction (MSR), a self-supervised loss active in the first 40 epochs, matches the log power spectrum of the encoder output to that of the input. For small log-spectral residuals on unclamped bins it is proportional to an Itakura-Saito divergence to leading order. Removing it raises the 60-minute MAE by 0.30 on METR-LA, close to the 0.33 lost when all three self-supervised losses go. Under one shared evaluation pipeline, the 60-minute MAE of ST-GFM is 3.5% below a retrained STAEformer on METR-LA and 13.0% below it on PEMS-BAY. Its 60-minute MAE is 3.0980.017 on METR-LA (five seeds) and 1.5760.006 on PEMS-BAY (three seeds), the lowest PEMS-BAY MAE among twelve published baselines.

0.32

Spectral Limits of Polynomial Graph Filters on the Long-Range Ising Model Benchmark

cs.LG ·2026-10-15 ·Amin Najafgholizadeh, Mohsen Afsharchi
benchmarktheory similarity 0.54
Abstract · 30 pages, 4 figures, 15 tables

The Long-Range Ising Model benchmark (LRIM) guarantees long-range dependence by construction: each label is the node's spin times the spin field convolved with a power-law coupling, so any model's distance from the target is measurable. We prove that a readout whose filter is a polynomial in the adjacency, the linear core of isotropic message passing and spectral graph networks, leaves an error floor that no degree lowers, because the target varies along a level set of the spectrum on which every such filter is constant. Computed exactly, the floor and the best filter of each degree predict two spectral networks adapted from published architectures to within a tenth of a decade. A filter escapes the floor only if it weighs separately the offsets the adjacency lumps together, and must still resolve the coupling across the whole lattice. A strided filter of about fifty coefficients does both: fitted to the training labels, its test error is 52 times below the best published network's. A dilated convolutional network beats the best published result at 256 nodes, matches it at 1,024, and gives the first in-domain results at the three larger sizes, while a Fourier neural operator with its standard modes falls further behind as the lattice grows. At its standard budget the dilated network stays two to four orders of magnitude short of a larger strided filter fitted to the labels. The analysis carries over to the benchmark's second coupling.

0.25

Graph Signal Estimation With Unknown Topology

eess.SP ·2026-10-25 ·Tirza Routtenberg
similarity 0.54
Abstract

Graph-signal estimation is commonly designed assuming that the underlying topology is known. In this paper, we consider estimation from general nonlinear measurements when the active topology is latent but is known to belong to a given family of candidate graphs. We first develop a class of topology-blind graph-spectral estimators that jointly exploit the candidate graphs, and characterize the performance loss compared to unconstrained linear estimation. We derive the minimum-mean-squared-error (MSE) multi-basis estimator and show that its optimal operator is the weighted projection of the topology-blind linear MMSE (LMMSE) operator onto the multi-graph filter space. This characterization provides exact expressions for the excess MSE and conditions for attaining the topology-blind LMMSE. To reduce the number of parameters, we develop estimators based on shared spectral responses and low-rank representations, and consider data-dependent estimators that infer the topology from the measurements, by maximum a-posteriori probability (MAP) selection or posterior weighting (multiple-model). We further extend the framework to networks of different sizes by jointly optimizing a common spectral function. We derive its MSE-optimal coefficients and decompose the resulting estimation loss into graph-filter approximation error and the additional cost of sharing a spectral response across networks. The proposed estimators admit sample-based implementations, while the shared spectral function can be applied to unseen graphs without retraining its coefficients. Simulations on IEEE power networks demonstrate the benefits of the proposed graph-spectral estimators under topology uncertainty and cross- network transfer.

0.42