Abstract
Iterative methods for computing eigenvectors, such as subspace iteration, are typically analyzed using the spectral norm. However, many downstream applications like spectral clustering and node ranking depend on the entrywise accuracy of the eigenvectors. This paper presents the first deterministic convergence analysis for subspace iteration in the entrywise ($\ell_{2 \to \infty}$) norm. We introduce a practical, residual-based stopping criterion that allows for significant computational savings—often 20–80%—by stopping iterations once sufficient entrywise precision is achieved, rather than waiting for global spectral convergence.
Introduction: The Entrywise Gap
In machine learning and network science, eigenvectors are rarely the end goal; their entries are. In Google's PageRank, entries determine search result rankings. In spectral clustering, each row of an eigenvector matrix serves as a coordinate for a data point. Traditionally, numerical analysts measure the "closeness" of an approximate eigenvector using the spectral ($\ell_2$) norm. While mathematically convenient, this global measure can be a poor proxy for entrywise accuracy. If the goal is to identify top-ranked nodes, high-precision global convergence—the target of standard software like ARPACK—is often unnecessary. This work addresses the lack of theoretical guarantees and practical stopping rules for iterative methods when the goal is entrywise precision.
Methods: Analyzing Subspace Iteration
The authors focus on Subspace Iteration, a fundamental method for computing leading eigenvectors.
New Convergence Bounds
The paper provides deterministic bounds showing how the $\ell_{2 \to \infty}$ distance (the maximum $\ell_2$ norm of any row in the error matrix) shrinks. This analysis relies on coherence, which measures how "spread out" eigenvector information is across entries.
Practical Stopping Criterion
A "residual-based" stopping criterion is derived (Equation 10 in the paper), allowing users to stop as soon as the entrywise error falls below a desired threshold. This is a departure from standard methods that wait for global error to minimize. The theory is supported by a technical assumption regarding "noise" behavior in the matrix, which the authors empirically verify on real-world datasets.
Key Insights: Avoiding Computational Overkill
A primary finding is the "Overkill Problem": standard eigensolvers often compute eigenvectors to a much higher global precision than required for downstream tasks. For clustering, a "crude" eigenvector that correctly identifies entry signs is often sufficient.
The speed of entrywise convergence is tied to matrix coherence. In "incoherent" matrices, where no single row dominates, entrywise error is significantly smaller than spectral error, enabling even earlier termination. Furthermore, the $\ell_{2 \to \infty}$ norm is invariant to unitary transformations on the right, making it the natural distance metric for spectral clustering where the subspace spanned is more important than specific vector orientation.
Experimental Results
The methods were evaluated on synthetic matrices and large-scale networks (e.g., CA-HepPh, COM-LiveJournal).
- Eigenvector Centrality: The proposed stopping criterion reduced iterations by 20–40% while maintaining node ranking accuracy.
- Spectral Clustering: Savings reached 70–80% in computation time, as "cut quality" stabilized long before standard spectral norm criteria were met.
- Sweep Cuts: Entrywise-informed stopping achieved optimal conductance much faster than high-precision methods.
Limitations and Future Work
The current analysis is restricted to symmetric matrices, leaving non-symmetric cases as an open challenge. While the technical assumptions were verified empirically, a more general proof would strengthen the theoretical foundation. Finally, while the stopping criterion is general, the specific convergence rates were proven only for subspace iteration; extending this to Krylov methods like the Lanczos algorithm is a promising future direction.
Summary updated