Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation

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 $\mathcal{O}(\lambda_1\lambda_2 d^2 / (\Delta^2 t))$, where $d$ is the ambient dimension, $\lambda_1, \lambda_2$ are the leading eigenvalues, and $\Delta = \lambda_1 - \lambda_2$ is the eigengap. We complement this with a matching information-theoretic lower bound of $\Omega(\lambda_1\lambda_2 d^2 / (\Delta^2 t))$ --- the first for compressed eigenvector estimation --- proving that the $d^2$ factor, an additional factor of $d$ compared to the fully-observed minimax rate $\Theta(\lambda_1\lambda_2 d / (\Delta^2 t))$, is the fundamental cost of compression and cannot be improved. In contrast, any non-adaptive scheme with two measurements per iteration suffers $\Omega(\lambda_2^2 d^3 / (\Delta^2 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.

Many modern systems need to find the dominant pattern in a stream of high-dimensional data — for instance, the strongest direction of a signal arriving at an antenna array, or the main trend across many sensors. The standard tool is principal component analysis (PCA), but PCA normally has to examine every dimension of every data point. In many devices that is impossible: hardware, bandwidth, or cost permit only a couple of summary numbers per sample. We study a method that needs just two cheap measurements per data point. It chooses these measurements on the fly — one along its current best guess of the dominant direction, and one in a random perpendicular direction — and refines the guess as new data streams in. We prove that the method reliably homes in on the true direction from any starting point, and we pin down exactly how its accuracy improves with more data. Compression carries a price: because it sees only two numbers instead of the whole sample, the method needs substantially more data — growing in proportion to the number of dimensions — than if it could observe everything. We also prove this price is unavoidable: no method using two measurements per sample can do better. Choosing the measurements adaptively is essential, too — fixed, non-adaptive measurements are far worse. Ours are the first such guarantees for realistic, noisy data, and they extend to tracking a direction that slowly drifts over time.