Subspace estimation from unbalanced and incomplete data matrices: _2, statistical guarantees

DOI10.1214/20-AOS1986MaRDI QIDQ2039795zbMATH OpenFDO

Authors Changxiao Cai, Gen Li, Yuejie Chi, H. Vincent Poor, Yuxin Chen

Publication date 5 July 2021

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

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

zbMATH Keywords

covariance estimationleave-one-out analysismissing dataprincipal component analysisspectral clusteringspectral methodtensor completion

Mathematics Subject Classification ID

Missing data (62D10) Estimation in multivariate analysis (62H12) Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: This paper is concerned with estimating the column space of an unknown low-rank matrix $$, 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 $el{l}_2$ and $el{l}_{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.

Review text

This paper is concerned with estimating the column space of an unknown low-rank matrix \(A^\ast \in \mathbb R^{d_1\times d_2}\) , given noisy and partial observations of its entries. The authors investigate an efficient spectral method, which operates upon the sample Gram matrix with diagonal deletion. The definition of Gram matrix and the algorithm of spectral method on the diagonal-deleted Gram matrix are given. While this algorithmic idea has been studied before, they 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\). The consequences of general theory for three applications of practical importance are established: (1) tensor completion from noisy data, (2) covariance estimation/principal component analysis with missing data and (3) community recovery in bipartite graphs.

Recommendations

• Asymptotic theory for estimating the singular vectors and values of a partially-observed low rank matrix with noise
• Robust matrix completion
• Minimax sparse principal subspace estimation in high dimensions
• Matrix completion from noisy entries
• Inference and uncertainty quantification for noisy matrix completion

Cites work

• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• A Simple SVD Algorithm for Finding Hidden Partitions
• A spectral heuristic for bisecting random graphs
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Achieving optimal misclassification proportion in stochastic block models
• Adaptive covariance matrix estimation through block thresholding
• An \(\ell_{\infty}\) eigenvector perturbation bound and its application
• Angular synchronization by eigenvectors and semidefinite programming
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Asymptotic theory for estimating the singular vectors and values of a partially-observed low rank matrix with noise
• Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance
• Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
• Clustering partially observed graphs via convex optimization
• Community detection and stochastic block models: recent developments
• Community detection in sparse networks via Grothendieck's inequality
• Community detection thresholds and the weak Ramanujan property
• Consistency of spectral clustering in stochastic block models
• Convexified modularity maximization for degree-corrected stochastic block models
• Covariance Matrix Estimation With Non Uniform and Data Dependent Missing Observations
• Covariance regularization by thresholding
• Delocalization of eigenvectors of random matrices with independent entries
• Entrywise eigenvector analysis of random matrices with low expected rank
• Exact matrix completion via convex optimization
• Exact Recovery in the Stochastic Block Model
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Finite sample approximation results for principal component analysis: A matrix perturbation approach
• Graph partitioning via adaptive spectral techniques
• Guaranteed Matrix Completion via Non-Convex Factorization
• High-dimensional covariance matrix estimation with missing observations
• High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity
• scientific article; zbMATH DE number 6458321 (Why is no real title available?)
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
• Information Recovery From Pairwise Measurements
• Low-rank matrix completion using alternating minimization
• Matrix Completion From a Few Entries
• Matrix completion from noisy entries
• Matrix estimation by universal singular value thresholding
• Minimax rate-optimal estimation of high-dimensional covariance matrices with incomplete data
• Near-optimal bounds for phase synchronization
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• On consistency and sparsity for principal components analysis in high dimensions
• On polynomial time methods for exact low-rank tensor completion
• On sample eigenvalues in a generalized spiked population model
• On semidefinite relaxations for the block model
• On tensor completion via nuclear norm minimization
• On the distribution of the largest eigenvalue in principal components analysis
• Optimal bipartite network clustering
• Optimal estimation and completion of matrices with biclustering structures
• Optimal estimation and rank detection for sparse spiked covariance matrices
• Oracle inequalities for local and global empirical risk minimizers
• Perturbation of linear forms of singular vectors under Gaussian noise
• Perturbation theory for pseudo-inverses
• Phase transitions in semidefinite relaxations
• Random Laplacian matrices and convex relaxations
• Random perturbation of low rank matrices: improving classical bounds
• Reconstruction and estimation in the planted partition model
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Sequential Unfolding SVD for Tensors With Applications in Array Signal Processing
• Signal-plus-noise matrix models: eigenvector deviations and fluctuations
• Sparse and Low-Rank Tensor Estimation via Cubic Sketchings
• Sparse PCA: optimal rates and adaptive estimation
• Sparse principal component analysis and iterative thresholding
• Sparse principal component analysis with missing observations
• Spectral algorithms for tensor completion
• Spectral clustering and the high-dimensional stochastic blockmodel
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• Subspace learning with partial information
• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• Tensor SVD: Statistical and Computational Limits
• Tensor-Based Formulation and Nuclear Norm Regularization for Multienergy Computed Tomography
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The projected power method: an efficient algorithm for joint alignment from pairwise differences
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Unperturbed: spectral analysis beyond Davis-Kahan
• Weighted least squares fitting using ordinary least squares algorithms

Cited in

(57)

• Community detection on mixture multilayer networks via regularized tensor decomposition
• An \({\ell_p}\) theory of PCA and spectral clustering
• Spectral Methods for Data Science: A Statistical Perspective
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Streaming principal component analysis from incomplete data
• Biwhitening Reveals the Rank of a Count Matrix
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Probabilistic-learning-based stochastic surrogate model from small incomplete datasets for nonlinear dynamical systems
• Inference for heteroskedastic PCA with missing data
• Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
• Degree-Heterogeneous Latent Class Analysis for High-Dimensional Discrete Data
• Higher-order entrywise eigenvectors analysis of low-rank random matrices: bias correction, Edgeworth expansion and bootstrap
• Estimating Higher-Order Mixed Memberships via the l2,∞ Tensor Perturbation Bound
• Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA
• Fault diagnosis based on incomplete sensor variables with a hierarchical semi-supervised Gaussian mixture classifier
• Analysis of singular subspaces under random perturbations
• Inference for Low-Rank Models Without Estimating the Rank
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Reply to the discussion of: ``Statistical exploration of the manifold hypothesis
• An overview of asymptotic normality in stochastic blockmodels: cluster analysis and inference
• Statistical inference for low-rank tensors: heteroskedasticity, subgaussianity, and applications
• Detection and estimation of vertexwise latent position shifts across networks
• Imputation algorithms based on the majorization-minimization framework for smoothed composite quantile regression and applications
• Learning block structures in covariance matrices under heteroskedasticity

This page was built for publication: Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees

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