Research map / Learning theory and algorithms / Matrix and tensor methods
On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysis
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 non-asymptotic error-propagation bounds for Hotelling's deflation with inexact top-eigenvector subroutines, first for an abstract subroutine and then, with tighter exponential-with-constant-base bounds, for power iteration.
Problem
Numerical errors in approximating each principal component propagate through sequential Hotelling's deflation for PCA, but prior analyses assume each leading-eigenvector subroutine is solved exactly.
Approach
Characterizes error propagation through deflation steps for an arbitrary eigenvector subroutine (bounds growing with eigengaps, nearly factorially), and for power iteration exploits the directional structure of the error vector to tighten the bound to exponential growth with constant base, yielding a lower bound of O(log(K/eps)+K) iterations instead of O(log(K/eps)+K log K).
Key results
- Sub-routine agnostic bound grows nearly factorially with K when eigenvalues decay as 1/j, requiring errors to be factorially small.
- With power iteration, the required iteration count improves from O(log(K/eps)+K log K) to O(log(K/eps)+K), saving a log K factor.
- On MNIST spectral clustering, mutual information increases with the number of power iteration steps used in the deflation subroutine.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase power iteration steps in inexact Hotelling deflation | spectral clustering with inexact Hotelling deflation · MNIST | mutual information | Helped |
Surprising findings
- The sub-routine agnostic bound is nearly factorial in K, so errors must be factorially small to guarantee accuracy.
Limitations
- Analysis assumes positive definite matrix with distinct eigenvalues.
- Requires the initial vector to have non-negligible overlap with the target eigenvector (constant c_0).
- Bounds still grow exponentially in K for the power-iteration case.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST spectral clustering (mutual information) synthetic 100x100 matrix with power-law spectrum
Metrics: mutual information absolute inner products |u_k^T u_j^*| error norm ||v_k - u_k^*||
Baselines: sub-routine agnostic deflation bound (Theorem 1)
Builds on: Hotelling's deflation power iteration Weyl's inequality Davis-Kahan sin-theta theorem
Closest papers by meaning
- Correlated-PCA: Principal Components' Analysis when Data and Noise are Correlated (NeurIPS 2016 · similarity 0.85)
- Oja's Algorithm for Streaming Sparse PCA (NeurIPS 2024 · similarity 0.84)
- Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.84)
- A Geometric Analysis of PCA (NeurIPS 2025 · similarity 0.83)
- Capturing the denoising effect of PCA via compression ratio (NeurIPS 2024 · similarity 0.83)
- Nonlinear Laplacians: Tunable principal component analysis under directional prior information (NeurIPS 2025 · similarity 0.83)
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.