mlsanityData to 7 Oct 2026

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

arXiv 2303.06198 ↗First posted 10 Mar 2023math.ST cs.IT cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

53 of 102 references.

References · 53

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  3. 2014A statistical model for tensor PCAcited by 72
  4. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  5. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  6. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  7. 2017Tensor SVD: Statistical and Computational Limitscited by 52
  8. 2021A unifying tutorial on Approximate Message Passingcited by 49
  9. 2017Spectral Method and Regularized MLE Are Both Optimal for Top-K Rankingcited by 46
  10. 2016Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statisticscited by 45
  11. 2019Optimality of Spectral Clustering in the Gaussian Mixture Modelcited by 42
  12. 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
38 more
  1. 2019Inference and Uncertainty Quantification for Noisy Matrix Completioncited by 39
  2. 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
  3. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  4. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
  5. 2017The landscape of the spiked tensor modelcited by 34
  6. 2018Optimality and Sub-optimality of PCA I: Spiked Random Matrix Modelscited by 33
  7. 2018Heteroskedastic PCA: Algorithm, Optimality, and Applicationscited by 33
  8. 2017Near-optimal bounds for phase synchronizationcited by 32
  9. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  10. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  11. 2016Statistical limits of spiked tensor modelscited by 27
  12. 2016Spectral algorithms for tensor completioncited by 27
  13. 2020Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Datacited by 23
  14. 2020Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limitcited by 23
  15. 2021Inference for Heteroskedastic PCA with Missing Datacited by 21
  16. 2018Streaming PCA and Subspace Tracking: The Missing Data Casecited by 18
  17. 2020Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methodscited by 18
  18. 2022A Non-Asymptotic Framework for Approximate Message Passing in Spiked Modelscited by 18
  19. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  20. 2017Unperturbed: spectral analysis beyond Davis-Kahancited by 16
  21. 2019High-dimensional principal component analysis with heterogeneous missingnesscited by 16
  22. 2013OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkagecited by 14
  23. 2022Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clusteringcited by 14
  24. 2018Robust high dimensional factor models with applications to statistical machine learningcited by 13
  25. 2020Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimalitycited by 13
  26. 2016Homotopy Analysis for Tensor PCAcited by 12
  27. 2020Inference for Low-rank Tensors -- No Need to Debiascited by 12
  28. 2021Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependencecited by 12
  29. 2020Optimal High-order Tensor SVD via Tensor-Train Orthogonal Iterationcited by 11
  30. 2020Global and Individualized Community Detection in Inhomogeneous Multilayer Networkscited by 11
  31. 2018Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matricescited by 10
  32. 2015Spectral Thresholds in the Bipartite Stochastic Block Modelcited by 9
  33. 2019A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outlierscited by 9
  34. 2020Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noisecited by 9
  35. 2023Approximate message passing from random initialization with applications to mathbbZ2 synchronizationcited by 9
  36. 2021Tensor Principal Component Analysis in High Dimensional CP Modelscited by 7
  37. 2014Projected principal component analysis in factor modelscited by 5
  38. 2018Sparse spectral estimation with missing and corrupted measurementscited by 5

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 0; 2026: 3.

7 papers.

  1. 2024Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methodscited by 5
  2. 2023Heteroskedastic Tensor Clusteringcited by 3
  3. 2024When can weak latent factors be statistically inferred?cited by 2
  4. 2023On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCAcited by 0
  5. 2026Adjacency Spectral Embeddings of Correlation Networkscited by 0
  6. 2026Beyond identifiability: Learning causal representations with few environments and finite samplescited by 0
  7. 2026Heteroskedastic Canonical Polyadic Tensor Decompositioncited by 0