# Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2016.

## Built on by (most cited first, 30 of 45)

- [Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data](https://mlsanity.com/paper/2105.07536/) (2021)
- [The Power of Contrast for Feature Learning: A Theoretical Analysis](https://mlsanity.com/paper/2110.02473/) (2021)
- [Elliptic PDE learning is provably data-efficient](https://mlsanity.com/paper/2302.12888/) (2023)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Nearly Minimax Algorithms for Linear Bandits with Shared Representation](https://mlsanity.com/paper/2203.15664/) (2022)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition](https://mlsanity.com/paper/2106.16042/) (2021)
- [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricing](https://mlsanity.com/paper/2309.08634/) (2023)
- [Learning Good State and Action Representations via Tensor Decomposition](https://mlsanity.com/paper/2105.01136/) (2021)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures](https://mlsanity.com/paper/2201.09040/) (2022)
- [A Spectral Method for Assessing and Combining Multiple Data Visualizations](https://mlsanity.com/paper/2210.13711/) (2022)
- [Optimal Estimation of Shared Singular Subspaces across Multiple Noisy Matrices](https://mlsanity.com/paper/2411.17054/) (2024)
- [One-Way Matching of Datasets with Low Rank Signals](https://mlsanity.com/paper/2204.13858/) (2022)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [Learning Joint and Individual Structure in Network Data with Covariates](https://mlsanity.com/paper/2406.08776/) (2024)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model](https://mlsanity.com/paper/2307.00575/) (2023)
- [On Differentially Private Subspace Estimation in a Distribution-Free Setting](https://mlsanity.com/paper/2402.06465/) (2024)
- [Signed Diverse Multiplex Networks: Clustering and Inference](https://mlsanity.com/paper/2402.10242/) (2024)
- [Provable Affine Identifiability of Nonlinear CCA under Latent Distributional Priors](https://mlsanity.com/paper/2510.04758/) (2025)
- [Concentration bounds on response-based vector embeddings of black-box generative models](https://mlsanity.com/paper/2511.08307/) (2025)
- [Classification of high-dimensional data with spiked covariance matrix structure](https://mlsanity.com/paper/2110.01950/) (2021)
- [Recommending with Recommendations](https://mlsanity.com/paper/2112.00979/) (2021)
- [Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms](https://mlsanity.com/paper/2202.04061/) (2022)

## Abstract (arXiv)

Perturbation bounds for singular spaces, in particular Wedin's sin Theta theorem, are a fundamental tool in many fields including high-dimensional statistics, machine learning, and applied mathematics. In this paper, we establish separate perturbation bounds, measured in both spectral and Frobenius sin Theta distances, for the left and right singular subspaces. Lower bounds, which show that the individual perturbation bounds are rate-optimal, are also given. The new perturbation bounds are applicable to a wide range of problems. In this paper, we consider in detail applications to low-rank matrix denoising and singular space estimation, high-dimensional clustering, and canonical correlation analysis (CCA). In particular, separate matching upper and lower bounds are obtained for estimating the left and right singular spaces. To the best of our knowledge, this is the first result that gives different optimal rates for the left and right singular spaces under the same perturbation. In addition to these problems, applications to other high-dimensional problems such as community detection in bipartite networks, multidimensional scaling, and cross-covariance matrix estimation are also discussed.