A0853
Title: Computationally optimal estimation and inference of common subspaces
Authors: Joshua Agterberg - University of Illinois Urbana-Champaign (United States) [presenting]
Abstract: The statistical and computational limits for the common subspace model are investigated, a model wherein one observes a collection of symmetric low-rank matrices perturbed by noise, where each low-rank matrix shares the same common subspace. First, an estimator is proposed based on Grassmannian gradient descent initialized via a spectral sum of squared matrices, and it is shown that it achieves the optimal sin Theta error under a strong signal-to-noise ratio (SNR) condition, and further evidence is given that this SNR condition is necessary for a polynomial-time estimator to exist. Next, estimation and inference are used for the sin Theta distance itself, and it is shown that the estimator achieves an asymptotically Gaussian distribution with a bias term that vanishes under a strong signal requirement. Based on this limiting result, confidence intervals are proposed, and it is shown that they are minimax optimal, though the resulting confidence intervals require knowledge of the SNR. Then, it is turned to designing adaptive confidence intervals for the sin Theta error, and that adaptivity is information-theoretically impossible unless the SNR is sufficiently strong. Consequently, the results unveil a novel phenomenon: despite the SNR being "above" the computational limit for estimation, adaptive statistical inference may still be information-theoretically impossible.
