All Times EDT

#### Abstract Details

 Activity Number: 387 - Software Type: Contributed Date/Time: Thursday, August 12, 2021 : 12:00 PM to 1:50 PM Sponsor: IMS Abstract #318652 Title: Asymmetric Estimation of Low Rank Matrix: Statistical and Computational Limits Author(s): Yuchen Wu* and Andrea Montanari Companies: Stanford University and Stanford University Keywords: low-rank matrix estimation; Bayesian statistics; information-computation gap; Gaussian mixture model; phase transition; first order algorithm Abstract: We consider estimating singular vectors of a low-rank n by d matrix corrupted by noise with $n,d/to/infty$. SVD could be suboptimal when distribution of singular vector entries is given. In such cases previous work characterized the optimal estimation error in the proportional asymptotics $n/d\to\delta\in (0,\infty)$. Here we consider $n/d\to \{0,\infty\}$, and reveal regimes in which recovery is possible for one-sided singular vectors while impossible for the other. From an algorithmic perspective, we introduce a class of algorithms termed OGFOM, which includes classical first order algorithms like gradient descent and its variants.We prove a sharp characterization of the optimal error achieved by any OGFOM. Next we provide a tight lower bound on the estimation error of one-sided singular vectors achieved by any estimator, by computing exact asymptotics of a suitable free energy functional. We show that in terms of recovering one-sided singular vectors, our model is equivalent to a symmetric signal-plus-noise model.As an application, we consider high-dimensional Gaussian mixture model, and locate the exact minimum separation threshold for partial recovery with target accuracy.

Authors who are presenting talks have a * after their name.