Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
arXiv:2002.07624
Abstract
Driven by a wide range of applications, many principal subspace estimation problems have been studied individually under different structural constraints. This paper presents a unified framework for the statistical analysis of a general structured principal subspace estimation problem which includes as special cases non-negative PCA/SVD, sparse PCA/SVD, subspace constrained PCA/SVD, and spectral clustering. General minimax lower and upper bounds are established to characterize the interplay between the information-geometric complexity of the structural set for the principal subspaces, the signal-to-noise ratio (SNR), and the dimensionality. The results yield interesting phase transition phenomena concerning the rates of convergence as a function of the SNRs and the fundamental limit for consistent estimation. Applying the general results to the specific settings yields the minimax rates of convergence for those problems, including the previous unknown optimal rates for non-negative PCA/SVD, sparse SVD and subspace constrained PCA/SVD.
References in corpus (16)
- Generalized power method for sparse principal component analysis
- 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
- Sparse principal component analysis and iterative thresholding
- Sparse PCA: Optimal rates and adaptive estimation
- Optimal Solutions for Sparse Principal Component Analysis
- Truncated Power Method for Sparse Eigenvalue Problems
- Nonconvex phase synchronization
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Minimax risk of matrix denoising by singular value thresholding
- A direct formulation for sparse PCA using semidefinite programming
- Phase Transitions in Semidefinite Relaxations
- Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
- Empirical entropy, minimax regret and minimax risk
- Geometric Inference for General High-Dimensional Linear Inverse Problems
- A Sparse SVD Method for High-dimensional Data
- Singular vector and singular subspace distribution for the matrix denoising model