A0906
Title: Deflated heteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA
Authors: Yuxin Chen - University of Pennsylvania (United States) [presenting]
Abstract: The focus is on estimating the column subspace of a low-rank n1 x n2 matrix X from contaminated data. How to obtain optimal statistical accuracy while accommodating the widest range of signal-to-noise ratios (SNRs) becomes particularly challenging in the presence of heteroskedastic noise and unbalanced dimensionality (i.e., n2>>n1). While the state-of-the-art algorithm emerges as a powerful solution for solving this problem, it suffers from "the curse of ill-conditioning," namely, its performance degrades as the condition number of X grows. In order to overcome this critical issue without compromising the range of allowable SNRs, a novel algorithm, called -, is proposed that achieves near-optimal and condition-number-free theoretical guarantees in terms of both L2 and fine-grained statistical accuracy. Further, an application of the algorithm and theory to two canonical examples, the factor model and tensor PCA, leads to remarkable improvement for each application.
