Matrix estimation by Universal Singular Value Thresholding

Abstract

Consider the problem of estimating the entries of a large matrix, when the observed entries are noisy versions of a small random fraction of the original entries. This problem has received widespread attention in recent times, especially after the pioneering works of Emmanuel Candès and collaborators. This paper introduces a simple estimation procedure, called Universal Singular Value Thresholding (USVT), that works for any matrix that has "a little bit of structure." Surprisingly, this simple estimator achieves the minimax error rate up to a constant factor. The method is applied to solve problems related to low rank matrix estimation, blockmodels, distance matrix completion, latent space models, positive definite matrix completion, graphon estimation and generalized Bradley--Terry models for pairwise comparison.

Published in at http://dx.doi.org/10.1214/14-AOS1272 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (8)

• Graph limits and exchangeable random graphs
• Pseudo-likelihood methods for community detection in large sparse networks
• OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
• The method of moments and degree distributions for network models
• Nonparametric graphon estimation
• On replica symmetry of large deviations in random graphs
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Co-clustering separately exchangeable network data

Cited by in corpus (172)

• Matrix Completion Methods for Causal Panel Data Models
• Pseudo-likelihood methods for community detection in large sparse networks
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Rate-optimal graphon estimation
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
• On Adaptive Attacks to Adversarial Example Defenses
• Network histograms and universality of blockmodel approximation
• Nonparametric graphon estimation
• A goodness-of-fit test for stochastic block models
• Statistical inference on random dot product graphs: a survey
• On the Dimensionality of Word Embedding
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
• Enhanced Low-Rank Matrix Approximation
• Sparse exchangeable graphs and their limits via graphon processes
• On a 'Two Truths' Phenomenon in Spectral Graph Clustering
• Asymptotic performance of PCA for high-dimensional heteroscedastic data
• ME-Net: Towards Effective Adversarial Robustness with Matrix Estimation
• Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
• High-dimensional estimation with geometric constraints
• Universally consistent vertex classification for latent positions graphs
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Adversarial Examples in Modern Machine Learning: A Review
• Co-clustering separately exchangeable network data
• A Consistent Histogram Estimator for Exchangeable Graph Models
• Private Graphon Estimation for Sparse Graphs
• Convex recovery from interferometric measurements
• Learning tensors from partial binary measurements
• 1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• Optimal Change Point Detection and Localization in Sparse Dynamic Networks
• Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
• Estimation of subgraph density in noisy networks
• The Optimal Hard Threshold for Singular Values is 4/sqrt(3)
• Graphon Filters: Graph Signal Processing in the Limit
• Guaranteed recovery of quantum processes from few measurements
• Community Detection via Random and Adaptive Sampling
• ScreeNOT: Exact MSE-Optimal Singular Value Thresholding in Correlated Noise
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• Spectral Clustering for Multiple Sparse Networks: I
• Semiparametric spectral modeling of the Drosophila connectome
• Variational Bayes model averaging for graphon functions and motif frequencies inference in W-graph models
• Change-point detection in dynamic networks via graphon estimation
• On Robustness of Principal Component Regression
• Estimating network edge probabilities by neighborhood smoothing
• A Note on Exploratory Item Factor Analysis by Singular Value Decomposition
• Biwhitening Reveals the Rank of a Count Matrix
• Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics
• Network Topology Mapping from Partial Virtual Coordinates and Graph Geodesics
• Matrix Completion Under Monotonic Single Index Models
• Network cross-validation by edge sampling
• Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
• Harnessing Structures for Value-Based Planning and Reinforcement Learning
• 1-Bit Matrix Completion under Exact Low-Rank Constraint
• On Low-Rank Hankel Matrix Denoising
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model
• On matrix estimation under monotonicity constraints
• Network Representation Using Graph Root Distributions
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Decentralized Data-Enabled Predictive Control for Power System Oscillation Damping
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Low-rank matrix completion and denoising under Poisson noise
• Random Graph Asymptotics for Treatment Effect Estimation under Network Interference
• Federated Optimization of Smooth Loss Functions
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• A review on minimax rates in change point detection and localisation
• On sparsity, power-law and clustering properties of graphex processes
• General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
• Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks
• Streaming, Memory Limited Algorithms for Community Detection
• Automated Spectral Kernel Learning
• Change point localization in dependent dynamic nonparametric random dot product graphs
• On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations
• Joint Network Topology Inference via a Shared Graphon Model
• Hierarchical community detection by recursive partitioning
• Link prediction for egocentrically sampled networks
• Optimal network online change point localisation
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Multi-sample Estimation of Bacterial Composition Matrix in Metagenomics Data
• An iterative step-function estimator for graphons
• Why are Big Data Matrices Approximately Low Rank?
• Adapting to Unknown Noise Distribution in Matrix Denoising
• Reducing Crowdsourcing to Graphon Estimation, Statistically
• Goodness of fit of logistic models for random graphs
• Denoised Internal Models: a Brain-Inspired Autoencoder against Adversarial Attacks
• Random perturbation of low rank matrices: Improving classical bounds
• Optimal Bayesian estimation in stochastic block models
• Towards a Theoretical Analysis of PCA for Heteroscedastic Data
• Concentration properties of fractional posterior in 1-bit matrix completion
• Causal Imputation via Synthetic Interventions
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Latent Distance Estimation for Random Geometric Graphs
• Dynamic Network Prediction
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Connectome Smoothing via Low-rank Approximations
• Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• From which world is your graph?
• Linear regression and its inference on noisy network-linked data
• Synthetic Control, Synthetic Interventions, and COVID-19 spread: Exploring the impact of lockdown measures and herd immunity
• Using Maximum Entry-Wise Deviation to Test the Goodness-of-Fit for Stochastic Block Models
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• Estimating Graph Dimension with Cross-validated Eigenvalues
• Informative core identification in complex networks
• Priors on exchangeable directed graphs
• High dimensional regression and matrix estimation without tuning parameters
• Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
• HGOE: Hybrid External and Internal Graph Outlier Exposure for Graph Out-of-Distribution Detection
• Robust Synthetic Control
• Synthetic Interventions
• Reconstruction of Line-Embeddings of Graphons
• Optimal Bayesian Estimation for Random Dot Product Graphs
• Representation Learning and Recovery in the ReLU Model
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• What to Expect When You Are Expecting on the Grassmannian
• Sharper Bounds for Regularized Data Fitting
• Spectral State Compression of Markov Processes
• Projective, Sparse, and Learnable Latent Position Network Models
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons
• Algebraic-Combinatorial Methods for Low-Rank Matrix Completion with Application to Athletic Performance Prediction
• Binary Matrix Completion Using Unobserved Entries
• Adaptive Estimation of Noise Variance and Matrix Estimation via USVT Algorithm
• Empirical Bayes PCA in high dimensions
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• Minimax Hypothesis Testing for the Bradley-Terry-Luce Model
• Learning Graphons via Structured Gromov-Wasserstein Barycenters
• Optimal singular value shrinkage for operator norm loss
• Adaptive Shrinkage of singular values
• Graphon Estimation from Partially Observed Network Data
• Nonparametric regression for multiple heterogeneous networks
• Estimation of the Epidemic Branching Factor in Noisy Contact Networks
• Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion; Some Statistical and Algorithmic Theory for Adaptive-Impute
• Strength of Connections in a Random Graph: Definition, Characterization, and Estimation
• Entropic Optimal Transport in Random Graphs
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• A Fast Data Driven Shrinkage of Singular Values for Arbitrary Rank Signal Matrix Denoising
• mRSC: Multi-dimensional Robust Synthetic Control
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising
• On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure
• Spectral goodness-of-fit tests for complete and partial network data
• Causal Inference with Corrupted Data: Measurement Error, Missing Values, Discretization, and Differential Privacy
• Rejoinder on: Minimal penalties and the slope heuristics: a survey
• Central Limit Theorems for Classical Multidimensional Scaling
• Hawkes Processes on Graphons
• Two-sample Testing on Latent Distance Graphs With Unknown Link Functions
• A model selection approach for clustering a multinomial sequence with non-negative factorization
• Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice
• Phase Transition in the Recovery of Rank One Matrices Corrupted by Gaussian Noise
• Distributed Cartesian Power Graph Segmentation for Graphon Estimation
• Techniques for clustering interaction data as a collection of graphs
• Zorro: A Model Agnostic System to Price Consumer Data
• Network estimation via graphon with node features
• Network effects in default clustering for large systems
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion
• Variational Inference for Stochastic Block Models from Sampled Data
• Trading off Accuracy for Speedup: Multiplier Bootstraps for Subgraph Counts
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting Glioblastoma gene modules
• Achievability and Impossibility of Exact Pairwise Ranking
• Optimal Estimation of Schatten Norms of a rectangular Matrix
• Misclassification excess risk bounds for 1-bit matrix completion
• Unified Statistical Theory of Spectral Graph Analysis
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Deconvolution with Unknown Error Distribution Interpreted as Blind Isotonic Regression
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering
• Learning Graphon Autoencoders for Generative Graph Modeling
• Training Graph Neural Networks by Graphon Estimation
• A Semidefinite Program for Structured Blockmodels