Research map / Learning theory and algorithms / Sample complexity
Approximating the Top Eigenvector in Random Order Streams
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 a single-pass block power method for top eigenvector of A^T A in uniformly random order streams using O(h·d·polylog d) bits, achieving correlation 1-O(1/sqrt R) with a matching-style lower bound.
Problem
Approximating the top eigenvector (top right singular vector) of A^T A in a single pass over streamed rows with small (near-linear in d) memory, for worst-case inputs with a spectral gap R, under uniformly random row order.
Approach
Uses non-overlapping sampled blocks of a random-order stream, each giving an approximate quadratic form B_j^T B_j, multiplies them in sequence on a Gaussian vector (block power method) in one pass; heavy rows are stored explicitly and light rows are row-norm sampled to equal norms.
Key results
- Single-pass random-order algorithm using O(h·d·polylog d) bits outputs v with <v,v_1>^2 >= 1 - O(1/sqrt(R)) for R = Omega(1) (theory).
- Lower bound: any algorithm with 1 - c/R^2 correlation on random-order streams needs Omega(h·d/R) bits.
- Hard instance shows Price and Xun's Oja variant fails at gaps R = Theta(log d / log log d) even in random order.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed heavy/light-row algorithm on uniformly random-order streams | Top eigenvector approximation · Random-order streams with gap R and at most h heavy rows | squared correlation: 1 - 8/√R | Helped |
| Use the block power method with bounded row norms | Top eigenvector approximation · Random-order streams with bounded row norms | squared correlation: 1 - 3α | Helped |
| Subsample rows using row-norm sampling before applying Price and Xun's algorithm | Price and Xun algorithm · Arbitrary-order streams | gap requirement: Ω(log n · log d) -> Ω(log^2 d) | Helped |
| Use the random-order assumption in Price and Xun's analysis | Price and Xun algorithm · Random-order streams | gap requirement: R = Ω(log d) | Helped |
| Use the proposed algorithm instead of the Price and Xun algorithm | Top eigenvector approximation · Random-order streams | gap requirement: Ω(log d) -> Ω(1) | Helped |
| Require any streaming algorithm to attain squared correlation at least 1 - 1/(CR²) | Top eigenvector approximation · Random-order streams with h heavy rows | space: Ω(h · d / R) bits | Hurt |
| Use Oja's algorithm with any fixed learning rate | Oja's algorithm · Hard instances with R = O_c(log d/log log d) | correlation: fails to output ... |⟨v̂, v1⟩| ≥ c | Hurt |
Surprising findings
- The Price and Xun Oja-based algorithm can fail at gaps as large as Theta(log d / log log d) even on random-order streams.
Limitations
- Requires uniformly random row order rather than arbitrary order.
- Space scales with number of heavy rows h, which may be large in some streams.
- Analysis assumes polynomially bounded entries and gap constants.
Experimental setup
Metrics: squared correlation with top eigenvector space in bits
Baselines: Price and Xun (Oja variant) Frequent Directions Oja's algorithm
Builds on: Price and Xun eigenvector streaming algorithm (Oja variant) randomized power method row norm sampling for approximate matrix multiplication Frequent Directions
Closest papers by meaning
- Faster Eigenvector Computation via Shift-and-Invert Preconditioning (ICML 2016 · similarity 0.87)
- Low Precision Streaming PCA (NeurIPS 2025 · similarity 0.84)
- Simple Randomized Rounding for Max-Min Eigenvalue Augmentation (ICML 2025 · similarity 0.83)
- High-Dimensional Geometric Streaming for Nearly Low Rank Data (ICML 2024 · similarity 0.83)
- Optimal Spectral Transitions in High-Dimensional Multi-Index Models (NeurIPS 2025 · similarity 0.82)
- Oja's Algorithm for Streaming Sparse PCA (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.