# Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA

arXiv: https://arxiv.org/abs/2303.06198 · HTML: https://mlsanity.com/paper/2303.06198/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 53 of its 102 references that are in the map.
- First posted on arXiv 10 Mar 2023.

## Builds on (most cited first, 30 of 53)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Inference and Uncertainty Quantification for Noisy Matrix Completion](https://mlsanity.com/paper/1906.04159/) (2019)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [The landscape of the spiked tensor model](https://mlsanity.com/paper/1711.05424/) (2017)
- [Heteroskedastic PCA: Algorithm, Optimality, and Applications](https://mlsanity.com/paper/1810.08316/) (2018)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Statistical limits of spiked tensor models](https://mlsanity.com/paper/1612.07728/) (2016)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Streaming PCA and Subspace Tracking: The Missing Data Case](https://mlsanity.com/paper/1806.04609/) (2018)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)

## Built on by (most cited first, 7 of 7)

- [Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods](https://mlsanity.com/paper/2405.13912/) (2024)
- [Heteroskedastic Tensor Clustering](https://mlsanity.com/paper/2311.02306/) (2023)
- [When can weak latent factors be statistically inferred?](https://mlsanity.com/paper/2407.03616/) (2024)
- [Beyond identifiability: Learning causal representations with few environments and finite samples](https://mlsanity.com/paper/2603.25796/) (2026)
- [On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCA](https://mlsanity.com/paper/2312.03438/) (2023)
- [Adjacency Spectral Embeddings of Correlation Networks](https://mlsanity.com/paper/2602.21055/) (2026)
- [Heteroskedastic Canonical Polyadic Tensor Decomposition](https://mlsanity.com/paper/2610.00498/) (2026)

## Abstract (arXiv)

This paper is concerned with estimating the column subspace of a low-rank matrix boldsymbolX^star ∈ ℝn1× n2 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., n2gg n1). While the state-of-the-art algorithm textsfHeteroPCA 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 boldsymbolX^star grows. In order to overcome this critical issue without compromising the range of allowable SNRs, we propose a novel algorithm, called textsfDeflated-HeteroPCA, that achieves near-optimal and condition-number-free theoretical guarantees in terms of both ℓ2 and ℓ2,∞ statistical accuracy. The proposed algorithm divides the spectrum of boldsymbolX^star into well-conditioned and mutually well-separated subblocks, and applies textsfHeteroPCA to conquer each subblock successively. Further, an application of our algorithm and theory to two canonical examples -- the factor model and tensor PCA -- leads to remarkable improvement for each application.