arXiv:2505.10882cs.LGstat.ML2025-05中稿 · ICML被引 1

用两次自适应测量实现压缩主成分估计,理论证明效率最优。

Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation

  • 每轮仅需两次自适应测量:当前方向与正交随机方向
  • 误差率随迭代次数呈1/t衰减,含维度平方项d²的理论下界
  • 首次在噪声环境下给出自适应压缩子空间追踪的收敛保证

经典主成分分析需全维采样,但实际中硬件限制通常只能获取每样本少量标量测量。本文分析一种压缩版Oja算法,每轮仅用两个自适应测量(当前估计方向和随机正交方向)估计数据协方差矩阵的主特征向量。我们证明:经过t次迭代后,到真实特征向量的期望sin²误差为𝒪(λ₁λ₂d²/(Δ²t)),其中d为环境维度,λ₁、λ₂为前两个特征值,Δ=λ₁−λ₂为特征值间距。我们进一步给出匹配的信息论下界Ω(λ₁λ₂d²/(Δ²t)),这是首个针对压缩特征向量估计的下界,证明了d²因子是压缩带来的根本代价且不可改进。相较之下,任意非自适应方案误差为Ω(λ₂²d³/(Δ²t)),多出一阶d。该结果在完全观测、自适应压缩与非自适应压缩三类方法间形成三个不同幂次的维度依赖。分析还涵盖存在尾部非零特征值的噪声情形,首次提供自适应压缩子空间追踪在噪声下的收敛性保证。

原文摘要 · Abstract (English)

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}(λ_1λ_2 d^2 / (Δ^2 t))$, where $d$ is the ambient dimension, $λ_1, λ_2$ are the leading eigenvalues, and $Δ= λ_1 - λ_2$ is the eigengap. We complement this with a matching information-theoretic lower bound of $Ω(λ_1λ_2 d^2 / (Δ^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 $Θ(λ_1λ_2 d / (Δ^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))$, 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.

主成分分析自适应测量压缩感知特征向量估计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。