Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees

Abstract

This paper is concerned with estimating the column space of an unknown low-rank matrix ${\mathbf{A}}^{\star }\in {\mathbb{R}}^{d_1\times d_2}$, given noisy and partial observations of its entries. There is no shortage of scenarios where the observations -- while being too noisy to support faithful recovery of the entire matrix -- still convey sufficient information to enable reliable estimation of the column space of interest. This is particularly evident and crucial for the highly unbalanced case where the column dimension $d_2$ far exceeds the row dimension $d_1$, which is the focal point of the current paper. We investigate an efficient spectral method, which operates upon the sample Gram matrix with diagonal deletion. While this algorithmic idea has been studied before, we establish new statistical guarantees for this method in terms of both ${\ell }_2$ and ${\ell }_{2,\infty }$ estimation accuracy, which improve upon prior results if $d_2$ is substantially larger than $d_1$. To illustrate the effectiveness of our findings, we derive matching minimax lower bounds with respect to the noise levels, and develop consequences of our general theory for three applications of practical importance: (1) tensor completion from noisy data, (2) covariance estimation / principal component analysis with missing data, and (3) community recovery in bipartite graphs. Our theory leads to improved performance guarantees for all three cases.

arXiv commentAccepted to Annals of Statistics

References in corpus (36)

• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Matrix estimation by Universal Singular Value Thresholding
• Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Efficiently inferring community structure in bipartite networks
• Limit theorems for sample eigenvalues in a generalized spiked population model
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Provable Tensor Factorization with Missing Data
• Adaptive covariance matrix estimation through block thresholding
• Phase Transitions in Semidefinite Relaxations
• Near-optimal bounds for phase synchronization
• Clustering Partially Observed Graphs via Convex Optimization
• A statistical model for tensor PCA
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• On Robustness of Principal Component Regression
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Community Recovery in Graphs with Locality
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Estimating Mixed Memberships with Sharp Eigenvector Deviations
• Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries
• Robust high dimensional factor models with applications to statistical machine learning
• Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's
• Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
• Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Optimal Bipartite Network Clustering
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning

Cited by in corpus (3)

• Biwhitening Reveals the Rank of a Count Matrix
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• An ${\ell }_p$ theory of PCA and spectral clustering