Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics

DOI10.1214/17-AOS1541zbMATH Open1395.62122arXiv1605.00353OpenAlexW2964066048MaRDI QIDQ1747733FDOQ1747733

Authors: Anru Zhang, T. Tony Cai 

Publication date: 27 April 2018

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: Perturbation bounds for singular spaces, in particular Wedin's $sinTheta$ 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 $sinTheta$ 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.

Full work available at URL: https://arxiv.org/abs/1605.00353

Recommendations

• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• An \(\ell_{\infty}\) eigenvector perturbation bound and its application
• Random perturbation of low rank matrices: improving classical bounds
• Singular vectors under random perturbation
• Additive relative perturbation bounds of singular subspaces

zbMATH Keywords

clusteringcanonical correlation analysishigh-dimensional statisticssingular value decompositionperturbation boundspectral method\(\sin\Theta\) distanceslow-rank matrix denoising

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Estimation in multivariate analysis (62H12) Random matrices (algebraic aspects) (15B52)

Cites Work

• Matrix completion from noisy entries
• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis
• Spectral clustering and the high-dimensional stochastic blockmodel
• Modern multidimensional scaling. Theory and applications.
• Title not available (Why is that?)
• The Rotation of Eigenvectors by a Perturbation. III
• Matrix estimation by universal singular value thresholding
• Consistency of spectral clustering in stochastic block models
• On consistency and sparsity for principal components analysis in high dimensions
• RELATIONS BETWEEN TWO SETS OF VARIATES
• Consistency of spectral clustering
• Exact matrix completion via convex optimization
• The Optimal Hard Threshold for Singular Values is <inline-formula> <tex-math notation="TeX">\(4/\sqrt {3}\) </tex-math></inline-formula>
• The singular values and vectors of low rank perturbations of large rectangular random matrices
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Sparse PCA: optimal rates and adaptive estimation
• Influential features PCA for high dimensional clustering
• Title not available (Why is that?)
• Perturbation bounds in connection with singular value decomposition
• Turning big data into tiny data: constant-size coresets for \(k\)-means, PCA and projective clustering
• Phase transitions for high dimensional clustering and related problems
• Canonical Correlation Analysis: An Overview with Application to Learning Methods
• Reconstruction of a low-rank matrix in the presence of Gaussian noise
• On the distribution of the left singular vectors of a random matrix and its applications
• Interior-point method for nuclear norm approximation with application to system identification
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
• Convex multi-task feature learning
• Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators
• Minimax risk of matrix denoising by singular value thresholding
• A note on \(\sin\Theta\) theorems for singular subspace variations
• Uniqueness of low-rank matrix completion by rigidity theory
• Minimax estimation in sparse canonical correlation analysis
• Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Optimal estimation and rank detection for sparse spiked covariance matrices
• Asymptotic theory for estimating the singular vectors and values of a partially-observed low rank matrix with noise
• Singular vectors under random perturbation
• Perturbation of the SVD in the presence of small singular values
• Sparse CCA: adaptive estimation and computational barriers
• Random perturbation of low rank matrices: improving classical bounds
• Singular vector perturbation under Gaussian noise
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Large-scale simultaneous testing of cross-covariance matrices with applications to PheWAS
• Sparse CCA via precision adjusted iterative thresholding

Cited In (45)

• A Schatten-\(q\) low-rank matrix perturbation analysis via perturbation projection error bound
• Hybrid Kronecker Product Decomposition and Approximation
• Title not available (Why is that?)
• A note on the orthogonal Procrustes problem and norm-dependent optimality
• One-dimensional tensor network recovery
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Efficient kernel canonical correlation analysis using Nyström approximation
• Estimation of canonical correlation directions: from Gaussian to sub-Gaussian population
• Two lower bounds about singular subspaces
• Subspace perspective on canonical correlation analysis: dimension reduction and minimax rates
• On the non-asymptotic concentration of heteroskedastic Wishart-type matrix
• Normal approximation and confidence region of singular subspaces
• Optimal estimation and computational limit of low-rank Gaussian mixtures
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Distributed Estimation for Principal Component Analysis: An Enlarged Eigenspace Analysis
• Estimation of misclassification rate in the Asymptotic Rare and Weak model with sub-Gaussian noises
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Perturbation of linear forms of singular vectors under Gaussian noise
• An \(\ell_{\infty}\) eigenvector perturbation bound and its application
• Quantitative limit theorems and bootstrap approximations for empirical spectral projectors
• Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition
• Lower bounds for invariant statistical models with applications to principal component analysis
• A stochastic perturbation analysis of the QR decomposition and its applications
• Perturbation expansions and error bounds for the truncated singular value decomposition
• Title not available (Why is that?)
• Rejoinder
• Angle-based joint and individual variation explained
• Optimal estimation for lower bound of the packing number
• Lower bound estimation for a family of high-dimensional sparse covariance matrices
• Perturbation upper bounds for singular subspaces with a kind of heteroskedastic noise and its application in clustering
• Optimal Permutation Recovery in Permuted Monotone Matrix Model
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Statistical Inference for High-Dimensional Matrix-Variate Factor Models
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Random perturbation of low rank matrices: improving classical bounds
• Optimal sparse singular value decomposition for high-dimensional high-order data
• A Projected Subgradient Method for the Computation of Adapted Metrics for Dynamical Systems
• Covariance Estimation for Matrix-valued Data
• Heteroskedastic PCA: algorithm, optimality, and applications
• Van Trees inequality, group equivariance, and estimation of principal subspaces
• Singular vector and singular subspace distribution for the matrix denoising model
• Upper bound estimations of misclassification rate in the heteroscedastic clustering model with sub-Gaussian noises
• Inference for heteroskedastic PCA with missing data
• An \({\ell_p}\) theory of PCA and spectral clustering

Uses Software

• PMA

This page was built for publication: Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747733)