Research map / Learning theory and algorithms / Matrix and tensor methods
Invariant subspaces and PCA in nearly matrix multiplication time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives an end-to-end floating-point analysis showing spectral projectors of Hermitian definite pencils (and hence PCA/low-rank PCA bases) can be computed to forward error epsilon in nearly matrix-multiplication bit complexity, via a logarithmically stable Cholesky analysis and counting-query spectral gap estimation with smoothed analysis.
Problem
Computing forward-accurate spectral projectors and invariant subspaces of Hermitian definite generalized eigenvalue problems (and PCA) in floating point with bit complexity faster than classical O(n^3) eigensolvers.
Approach
Reduce the GEP to a standard Hermitian problem via a logarithmically stable Cholesky factorization, estimate the spectral gap and midpoint using only eigenvalue counting queries on randomly regularized matrices (smoothed analysis with Wegner estimate, O~(n) random bits), then compute the projector by approximating the matrix sign function via Newton iteration, avoiding any diagonalization.
Key results
- Computes spectral projector to forward error epsilon in O(T_MM(n) polylog(n, 1/eps, kappa(S), 1/gap_k)) bit operations with probability 1-1/n, where T_MM(n)=n^(omega+eta) and omega ~ 2.372.
- Shows Cholesky factorization is logarithmically stable with O(T_MM(n)) arithmetic operations, requiring O(log(n)log(kappa)+log(1/eps)) bits.
- Counting-based gap computation saves a factor of O(log n) over diagonalization-based approach (O(T_MM(n) log^2 n) vs O(T_MM(n) log^3 n) arithmetic ops).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use counting queries instead of diagonalization to estimate spectral gaps and midpoints | Spectral gap and midpoint computation · Spectral gap and midpoint computation | arithmetic operations: O(T_{\mathsf{MM}}(n)\log^3(n)) -> O(T_{\mathsf{MM}}(n)\log^2(n)) | Helped |
| Use counting queries instead of diagonalization to estimate spectral gaps and midpoints | Spectral gap and midpoint computation · Spectral gap and midpoint computation, with ε, gap_k, κ(S)=Θ(1) | arithmetic operations: O(T_{\mathsf{MM}}(n)\log^2(n)) -> O(T_{\mathsf{MM}}(n)\log(n)) | Helped |
| Use counting queries instead of diagonalization | Spectral gap estimation · Spectral gap and midpoint computation, with ε, gap_k, κ^{-1}(S)∈Ω(poly(1/n)) | bits of precision: O(\log^5(n)) | No clear effect |
| Apply a stable fast Cholesky factorization to reduce the GEP to a Hermitian eigenproblem | PROJECTOR · Hermitian definite GEP spectral projector | bit complexity: O(n^3) -> O\left( n^{\omega+\eta}\polylog(n,\epsilon^{-1},\kappa(\matS),\gap_k^{-1}) \right) | Helped |
| Use counting queries to avoid explicit diagonalization when computing spectral gaps | GAP · Spectral gap and midpoint computation | arithmetic operations: O(T_{\mathsf{MM}}(n)\log^2(n)) -> O(T_{\mathsf{MM}}(n)\log(n)) | Helped |
| Use Block-Krylov PCA with the proposed floating-point analysis | Block-Krylov Iteration · Block-Krylov PCA | bit complexity | Helped |
Surprising findings
- The LU factorization of a Hermitian definite matrix does not give the Cholesky factor in floating point, shown by a counter-example.
- Diagonalization is redundant for computing spectral gaps and invariant subspaces, at least with current algorithms; counting queries suffice.
Limitations
- Bit precision requirement is dominated by the sign function (SGN) algorithm, which needs many bits.
- Only theoretical bounds; no empirical experiments reported.
- Sparse or structured matrices (e.g., banded in DFT) are not handled faster than the general bound.
Experimental setup
Metrics: bit complexity forward error ||Pi_k - Pitilde_k||
Baselines: classical O(n^3) eigensolvers diagonalization-based gap computation (EIG) Block-Krylov PCA
Builds on: Demmel-Dumitriu-Holtz-Kleinberg stable fast matrix multiplication Higham-Kressner-style sign function algorithm Cholesky-QR Wegner estimate
Closest papers by meaning
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.84)
- Nonlinear Laplacians: Tunable principal component analysis under directional prior information (NeurIPS 2025 · similarity 0.84)
- Finding Koopman Invariant Subspaces via Personalized PageRank (NeurIPS 2026 · similarity 0.83)
- Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.83)
- A Geometric Analysis of PCA (NeurIPS 2025 · similarity 0.83)
- Generalized Eigenvalue Problems with Generative Priors (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.