Locally Approximating the Top Eigenvector of Bounded Entry Matrices
2026-07-09 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors provide a method to quickly estimate the top eigenvector of a large symmetric matrix using only a small number of queries to its entries. Their approach improves on past work by making it possible to calculate each coordinate of the eigenvector locally and efficiently, especially when the smallest eigenvalue is not too large compared to the largest. They prove that their query complexity is close to the best possible and apply their method to create faster algorithms for finding approximate solutions to graph partitioning problems. This work offers practical tools for problems in dense graph models without the huge computational costs seen in earlier methods.
top eigenvectorsymmetric matrixlocal computation algorithmsquery complexityeigenvaluessparsest cutmax cutCheeger's inequalityTrevisan's algorithmdense graph model
Authors
Nicolas Menand, Erik Waingarten
Abstract
We provide a local computation algorithm to approximate the top eigenvector $x \in \mathbb{R}^n$ of a symmetric matrix $A \in \mathbb{R}^{n \times n}$ with entries between $-1$ and $1$, building on the work of Swartworth and Woodruff [SODA 25] who show how to approximate the eigenvalues up to additive-$\varepsilon n$ error using $\tilde{O}(1/\varepsilon^4)$ queries. Our local computation algorithm has a preprocessing complexity of $\tilde{O}(1/\varepsilon^4)$ and per-coordinate query complexity of $\tilde{O}(1/\varepsilon^2)$ for an additive-$\varepsilon n$ approximation whenever {$|λ_{\min}(A)| = O(λ_{\max}(A))$. When $λ_{\min}(A)$ greatly exceeds $λ_{\max}(A)$, our complexity degrades to at most $\tilde{O}(1/\varepsilon^{6.\overline{6}})$ in preprocessing and $\tilde{O}(1/\varepsilon^{3.\overline{3}})$ per query. Furthermore, we show a lower bound of $Ω(n/\varepsilon^2)$ on the total number of queries needed to output an approximately top eigenvector (implying that the per-coordinate query complexity of $Ω(1/\varepsilon^2)$ is necessary). As an application, we use our algorithm to provide local computation algorithms for the sparsest-cut and max-cut problems in the dense graph model of Goldreich, Goldwasser, Ron [JACM 98]. By accessing the top eigenvectors (of an approximate normalized adjacency), we implement local versions of Cheeger's inequality and Trevisan's algorithm [SICOMP 12] to obtain "square-root-opt" approximations in polynomial time (as opposed to exponential-in-$\text{poly}(1/\varepsilon)$ time which is incurred in Goldreich, Goldwasser, Ron.