Reproduce “Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA” on OpenResearch

About this paper

Yuchen Zhou, Yuxin Chen

Researchers from the University of Illinois Urbana-Champaign and the University of Pennsylvania developed Deflated-HeteroPCA, an algorithm for low-rank matrix subspace estimation that overcomes the curse of ill-conditioning in heteroskedastic PCA. This method achieves condition-number-free statistical guarantees for both spectral norm and row-wise accuracy, matching minimax lower bounds and outperforming prior state-of-the-art methods in ill-conditioned scenarios.

Key insights

• The observed "curse of ill-conditioning" in HeteroPCA stems from its handling of the empirical Gram matrix and can be mitigated by processing the signal in well-conditioned spectral subblocks.
• Applying HeteroPCA to smaller, well-conditioned spectral subblocks allows it to function effectively, even when the overall signal is highly ill-conditioned.
• Condition-number-free theoretical guarantees, particularly for fine-grained "L_2,infinity" accuracy, can be achieved through a novel analytical framework based on a spectral representation lemma rather than traditional leave-one-out arguments.

Summary by alphaXiv.