Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation

Alex Saad-Falcon, Brighton Ancelin, Justin Romberg · 2025

Read Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation by Alex Saad-Falcon, Brighton Ancelin, Justin Romberg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-10882.txt.

Introduction

Alex Saad-Falcon, Brighton Ancelin, and Justin Romberg prove tight rates for finding a top eigenvector from just two adaptive gauges per sample. Their paper from twenty twenty-five revisits principal component analysis under hardware strain. Full samples are a luxury when each read costs. Their variant of Oja's method reads along the current guess and along one random cross direction.

Error falls at a rate the team states in terms of dimension, top eigenvalues, and their gap. A matching lower bound, billed as a first for this compressed task, shows the rate cannot improve. The dimension cost is thus the true price of compression. Non-adaptive schemes pay a steeper power of dimension. Noise with trailing eigenvalues is covered too, a first beyond the clean case. The split between the three regimes is now sharp.

Catalog record

CREATORAlex Saad-Falcon, Brighton Ancelin, Justin Romberg
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-10882

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation Alex Saad-Falcon, Brighton Ancelin, Justin Romberg Abstract Principal component analysis classically requires full d 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 t iterations, the expected sine-squared error to the true eigenvector is 𝒪 ⁡ ( λ 1 ​ λ 2 ​ d 2 / ( Δ 2 ​ t ) ) \mathcal{O}(\lambda_{1}\lambda_{2}d^{2}/(\Delta^{2}t)) , where d d is the ambient dimension, λ 1 , λ 2 \lambda_{1},\lambda_{2} are the leading eigenvalues, and Δ = λ 1 − λ 2 \Delta=\lambda_{1}-\lambda_{2} is the eigengap. We complement this with a matching information-theoretic lower bound of Ω ⁡ ( λ 1 ​ λ 2 ​ d 2 / ( Δ 2 ​ t ) ) \Omega(\lambda_{1}\lambda_{2}d^{2}/(\Delta^{2}t)) — the first for compressed eigenvector estimation — proving that the d 2 d^{2} factor, an additional factor of d d compared to the fully-observed minimax rate Θ ⁡ ( λ 1 ​ λ 2 ​ d / ( Δ 2 ​ t ) ) \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 Ω ⁡ ( λ 2 2 ​ d 3 / ( Δ 2 ​ t ) ) \Omega(\lambda_{2}^{2}d^{3}/(\Delta^{2}t)) , an additional power of d d . This separates fully-observed, adaptive-compressed, and non-adaptive-compressed PCA across three powers of d 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. 1 Introduction Principal component analysis (PCA) is a fundamental technique for identifying low-dimensional structure in high-dimensional data. While batch methods like randomized SVD ( Halko et al., 2011 ) compute principal components efficiently, they require storing or repeatedly accessing the full dataset. Streaming algorithms like Oja’s method ( Oja, 1982 ) overcome this limitation by updating the subspace estimate one sample at a time, requiring only O(d) memory. Both approaches, however, assume access to full d -dimensional samples. This presents a significant limitation in settings where acquiring complete samples is physically infeasible — e.g., radar, wireless communications, genomics, MRI, and recommender systems. In this compressed sensing regime , we observe only a few scalar measurements per sample rather than the full vector. The two-measurement streaming setting arises from either physical or practical constraints in several domains where full-dimensional samples are intractable to attain and/or store. In phased-array radar and mmWave communications, modern hybrid-beamforming architectures pair large antenna arrays with far fewer RF chains: typical 5G mmWave designs use only a handful of RF chains per array, with each chain producing a single scalar measurement per time slot ( Heath et al., 2016 ) . In neural signal processing, implantable recording arrays must compress extracellular signals on-chip before wireless transmission, motivating a body of work on sensor-side compressed sensing for high-channel-count neural interfaces ( Sun and Zhao, 2021 ) . In wideband cognitive-radio spectrum sensing, periodic sub-Nyquist sampling estimates the power spectrum of a wide-sense stationary signal directly from compressed samples, bypassing signal reconstruction at the Nyquist rate ( Ariananda and Leus, 2012 ) . In all three settings, the data is observed once through a physical measurement process and cannot be revisited, so streaming algorithms with provable convergence guarantees are essential. Existing analyses of compressed subspace tracking assume noiseless data where observations lie exactly in the signal subspace (i.e., \lambda_{2}=\dots=\lambda_{d}=0 ). In our “noisy” setting, observations contain variance from trailing eigenvalues ( \lambda_{2}>0 ), which acts as noise when estimating the signal direction \bar{\boldsymbol{u}} . No prior work has established information-theoretic lower bounds for adaptive compressed sensing with a fixed number of measurements per iteration. We develop convergence guarantees for a compressed variant of Oja’s algorithm using only two adaptive measurements per iteration. At each step, we take one measurement along the current estimate and another in a random orthogonal direction, balancing exploitation with exploration. Our main result establishes matching upper and lower bounds: Theorem 1.1 . (Informal) Let \boldsymbol{\Sigma} have leading eigenvalues \lambda_{1}>\lambda_{2} with eigengap \Delta=\lambda_{1}-\lambda_{2} . For Gaussian data \boldsymbol{v}_{t}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Sigma}) observed through two adaptive linear measurements per iteration: Upper bound: Algorithm 1 achieves: \displaystyle\mathbb{E}[1-(\bar{\boldsymbol{u}}^{T}\boldsymbol{u}_{t})^{2}]=\mathcal{O}(\lambda_{1}\lambda_{2}d^{2}/(\Delta^{2}t)) (1) Lower bound: Any estimator satisfies: \displaystyle\mathbb{E}[1-(\bar{\boldsymbol{u}}^{T}\hat{\boldsymbol{u}}_{t})^{2}]=\Omega(\lambda_{1}\lambda_{2}d^{2}/(\Delta^{2}t)) (2) This establishes the minimax rate \Theta(\lambda_{1}\lambda_{2}d^{2}/(\Delta^{2}t)) for adaptive compressed PCA with two measurements per iteration. Compared to fully-observed PCA with rate \Theta(\lambda_{1}\lambda_{2}d/(\Delta^{2}t)) , our rate includes an additional factor of d — the fundamental cost of observing only a 2-dimensional projection at each iteration. The key contributions of this work include: • The first convergence analysis for adaptive compressed PCA with noisy observations, achieving the optimal \Theta(\lambda_{1}\lambda_{2}d^{2}/(\Delta^{2}t)) rate. • A matching information-theoretic lower bound via Assouad’s lemma, proving the d^{2} factor is unavoidable. • A novel Assouad-based derivation of the classical \Omega(\lambda_{1}\lambda_{2}d/(\Delta^{2}t)) lower bound for fully-observed PCA. • Fixed-point analysis for tracking time-varying subspaces. The lower bound proof (Appendix B ) exploits a measurement budget argument: two unit-norm measurements per iteration provide total “energy” 2t that must cover d-1 coordinates where the eigenvector could vary, giving average energy O(t/d) per coordinate and limiting per-coordinate estimation precision. The averaged form of Assouad’s lemma aggregates this difficulty across coordinates, yielding the \Omega(\lambda_{1}\lambda_{2}d^{2}/(\Delta^{2}t)) bound. The paper is organized as follows. Section 2 reviews related work. Section 3 formalizes the problem and presents Algorithm 1 . Section 4 presents the upper bound, lower bound, and tracking analysis. Section 5 sketches the proof techniques. Section 6 provides experimental validation, and Section 7 discusses limitations and extensions to rank- k subspaces. 2 Related Work 2.1 Streaming PCA and Subspace Tracking Subspace tracking algorithms iteratively update the subspace estimate as new data arrives, requiring only O(dk) memory for rank- k estimation. Oja’s algorithm ( Oja, 1982 ) performs a rank-one update followed by normalization at each iteration, with convergence guarantees developed in ( Balsubramani et al., 2013 ; Allen-Zhu and Li, 2017 ; Huang et al., 2021 ; Zhang and Balzano, 2016b ) . The algorithm is equivalent to projected gradient descent on the Grassmann manifold ( Balzano, 2022 ) . 2.2 Randomized and Batch PCA When data can be accessed in multiple passes, randomized methods achieve near-optimal complexity for approximating the sample covariance or its singular value decomposition. Randomized SVD ( Halko et al., 2011 ) computes a rank- k approximation using O(k) passes over the data, with extensions to single-pass streaming via sketching ( Woodruff, 2014 ) . Liberty’s Frequent Directions algorithm ( Liberty, 2013 ) provides deterministic streaming guarantees with optimal O(dk/\epsilon) space for (1+\epsilon) -approximate sample covariance. Block Krylov methods ( Musco and Musco, 2015 ) achieve optimal \tilde{O}(k/\sqrt{\epsilon}) matrix-vector product complexity. These methods treat the observed matrix as the object of interest, providing worst-case guarantees without distributional assumptions. In contrast, Oja’s algorithm and its variants operate under a statistical model where columns are drawn i.i.d. from a distribution with covariance \Sigma , and the

Read the complete text