# Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation

arXiv: https://arxiv.org/abs/2505.10882 · HTML: https://mlsanity.com/paper/2505.10882/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 37 references that are in the map.
- First posted on arXiv 16 May 2025.

## Builds on (most cited first, 17 of 17)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems](https://mlsanity.com/paper/1411.1134/) (2014)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Streaming PCA and Subspace Tracking: The Missing Data Case](https://mlsanity.com/paper/1806.04609/) (2018)
- [Convergence of Stochastic Gradient Descent for PCA](https://mlsanity.com/paper/1509.09002/) (2015)
- [The Fast Convergence of Incremental PCA](https://mlsanity.com/paper/1501.03796/) (2015)
- [Near-Optimal Stochastic Approximation for Online Principal Component Estimation](https://mlsanity.com/paper/1603.05305/) (2016)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation](https://mlsanity.com/paper/1506.07405/) (2015)
- [Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation](https://mlsanity.com/paper/1711.06644/) (2017)
- [Subspace Tracking with Dynamical Models on the Grassmannian](https://mlsanity.com/paper/2402.10352/) (2024)
- [Efficient subsampling for high-dimensional data](https://mlsanity.com/paper/2411.06298/) (2024)
- [Blind Compressive Sensing Framework for Collaborative Filtering](https://mlsanity.com/paper/1505.01621/) (2015)
- [Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation From Undersampled Data](https://mlsanity.com/paper/1610.00199/) (2016)

## Abstract (arXiv)

Principal component analysis classically requires full d-dimensional samples, yet in various applications hardware limits acquisition to a few scalar measurements per sample. We analyze a compressed variant of Oja's algorithm for estimating the principal eigenvector of the data covariance matrix using only two adaptive measurements per sample. At each iteration, we observe one measurement along the current estimate and one in a random orthogonal direction. We prove that after t iterations, the expected sine-squared error to the true eigenvector is O(λ1λ2 d2 / (Delta2 t)), where d is the ambient dimension, λ1, λ2 are the leading eigenvalues, and Delta = λ1 - λ2 is the eigengap. We complement this with a matching information-theoretic lower bound of Omega(λ1λ2 d2 / (Delta2 t)) -- the first for compressed eigenvector estimation -- proving that the d2 factor, an additional factor of d compared to the fully-observed minimax rate Theta(λ1λ2 d / (Delta2 t)), is the fundamental cost of compression and cannot be improved. In contrast, any non-adaptive scheme with two measurements per iteration suffers Omega(λ22 d3 / (Delta2 t)), an additional power of d. This separates fully-observed, adaptive-compressed, and non-adaptive-compressed PCA across three powers of d. Our analysis handles the noisy setting where the covariance has nonzero trailing eigenvalues, providing the first convergence guarantee for adaptive compressed subspace tracking beyond the noiseless case.