A Simpler Approach to Matrix Completion

Abstract

This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.

13 pages. Fixed typos. Added references

References in corpus (1)

• Quantum state tomography via compressed sensing

Cited by in corpus (221)

• Matrix Completion Methods for Causal Panel Data Models
• An overview of low-rank matrix recovery from incomplete observations
• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Estimation of high-dimensional low-rank matrices
• Guaranteed Matrix Completion via Non-convex Factorization
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• A quantum-inspired classical algorithm for recommendation systems
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Incoherence-Optimal Matrix Completion
• Matrix Completion has No Spurious Local Minimum
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Matrix Completion on Graphs
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Noisy low-rank matrix completion with general sampling distribution
• On statistics, computation and scalability
• Adaptive Sampling of RF Fingerprints for Fine-grained Indoor Localization
• Large-Scale Convex Minimization with a Low-Rank Constraint
• ROP: Matrix recovery via rank-one projections
• Matrix Completion via Max-Norm Constrained Optimization
• Matrix concentration inequalities via the method of exchangeable pairs
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• Universal Matrix Completion
• Guaranteed clustering and biclustering via semidefinite programming
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Poisson Matrix Recovery and Completion
• Note on sampling without replacing from a finite collection of matrices
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Fast matrix completion without the condition number
• High-Rank Matrix Completion and Subspace Clustering with Missing Data
• Provable Meta-Learning of Linear Representations
• Universal low-rank matrix recovery from Pauli measurements
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Accelerated Structured Alternating Projections for Robust Spectrally Sparse Signal Recovery
• Noisy Matrix Completion under Sparse Factor Models
• Computational Limits for Matrix Completion
• Exact Joint Sparse Frequency Recovery via Optimization Methods
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• A Note on Element-wise Matrix Sparsification via a Matrix-valued Bernstein Inequality
• Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation
• Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems
• Matrix Completion with Noisy Entries and Outliers
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• CUR Algorithm for Partially Observed Matrices
• Exponential Family Matrix Completion under Structural Constraints
• Compressed Sensing off the Grid
• Optimal large-scale quantum state tomography with Pauli measurements
• On the Power of Adaptivity in Matrix Completion and Approximation
• Matrix completion with deterministic pattern - a geometric perspective
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Tensor Completion Algorithms in Big Data Analytics
• Rank Minimization over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations
• On Robustness of Principal Component Regression
• Asymptotic equivalence of quantum state tomography and noisy matrix completion
• Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data
• Low Rank Approximation and Regression in Input Sparsity Time
• Completing Any Low-rank Matrix, Provably
• Subadditivity of Matrix phi-Entropy and Concentration of Random Matrices
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Nearly-optimal Robust Matrix Completion
• Matrix Completion Under Monotonic Single Index Models
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• Calibration Using Matrix Completion with Application to Ultrasound Tomography
• Blind Deconvolution using Convex Programming
• A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
• Low-rank Matrix Recovery from Errors and Erasures
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Calibrated Elastic Regularization in Matrix Completion
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Recovery guarantee of weighted low-rank approximation via alternating minimization
• Orthogonal Inductive Matrix Completion
• Exact Tensor Completion from Sparsely Corrupted Observations via Convex Optimization
• The condition number of Riemannian approximation problems
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• Value function approximation via low-rank models
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• A General Framework of Dual Certificate Analysis for Structured Sparse Recovery Problems
• A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data
• Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Exact tensor completion using t-SVD
• Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• A Note on Randomized Element-wise Matrix Sparsification
• Parameterized Algorithms for the Matrix Completion Problem
• Tensor train completion: local recovery guarantees via Riemannian optimization
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Matrix Completion from $O(n)$ Samples in Linear Time
• Robust Tensor Completion Using Transformed Tensor SVD
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
• An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
• Unified View of Matrix Completion under General Structural Constraints
• On Tensor Completion via Nuclear Norm Minimization
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• On Low-rank Trace Regression under General Sampling Distribution
• Deterministic tensor completion with hypergraph expanders
• Low-Rank Matrix Recovery from Row-and-Column Affine Measurements
• Leveraging Diversity and Sparsity in Blind Deconvolution
• Convolutional Geometric Matrix Completion
• Streaming, Memory Limited Matrix Completion with Noise
• Relax, no need to round: integrality of clustering formulations
• Collaborative Filtering with Label Consistent Restricted Boltzmann Machine
• Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method
• Prediction with Unpredictable Feature Evolution
• Maximum entropy low-rank matrix recovery
• Matrix Completion and Related Problems via Strong Duality
• Learning Treatment Effects in Panels with General Intervention Patterns
• A Simple Unified Framework for High Dimensional Bandit Problems
• Theoretical Analysis of Sparse Subspace Clustering with Missing Entries
• Empirical Bayes Matrix Completion
• Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs
• Accelerating Permutation Testing in Voxel-wise Analysis through Subspace Tracking: A new plugin for SnPM
• Sparse Linear Regression With Missing Data
• PCA from noisy, linearly reduced data: the diagonal case
• Cross: Efficient Low-rank Tensor Completion
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• Optimal tuning-free convex relaxation for noisy matrix completion
• Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
• From controlled to undisciplined data: estimating causal effects in the era of data science using a potential outcome framework
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion
• Optimal spectral norm rates for noisy low-rank matrix completion
• Haplotype Assembly: An Information Theoretic View
• Preference Completion from Partial Rankings
• Stochastic Gradient Descent for Linear Systems with Missing Data
• Information-Guided Sampling for Low-Rank Matrix Completion
• The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems
• Note: low-rank tensor train completion with side information based on Riemannian optimization
• Stable rank one matrix completion is solved by two rounds of semidefinite programming relaxation
• Matrix Completion from Non-Uniformly Sampled Entries
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Space Lower Bounds for Itemset Frequency Sketches
• Compressed Sensing Tomography for qudits in Hilbert spaces of non-power-of-two dimensions
• Identifying Influential Entries in a Matrix
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• From Blind deconvolution to Blind Super-Resolution through convex programming
• Strongly Convex Programming for Exact Matrix Completion and Robust Principal Component Analysis
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Spectral State Compression of Markov Processes
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Outlier Detection and Data Clustering via Innovation Search
• Distributed Low-rank Subspace Segmentation
• Matrix Completion via Nonconvex Regularization: Convergence of the Proximal Gradient Algorithm
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Tuning Free Rank-Sparse Bayesian Matrix and Tensor Completion with Global-Local Priors
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Poisson Matrix Completion
• Binary Matrix Completion Using Unobserved Entries
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• Sample Complexity of Power System State Estimation using Matrix Completion
• On the simplicity and conditioning of low rank semidefinite programs
• A Super-Resolution Framework for Tensor Decomposition
• Provable Adaptation across Multiway Domains via Representation Learning
• On Low Rank Directed Acyclic Graphs and Causal Structure Learning
• Finding a low-rank basis in a matrix subspace
• Low-rank Matrix Completion in a General Non-orthogonal Basis
• Consistent Collective Matrix Completion under Joint Low Rank Structure
• On Weighted Low-Rank Approximation
• Concentration for matrix martingales in continuous time and microscopic activity of social networks
• A Quadratically Convergent Algorithm for Structured Low-Rank Approximation
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• Local Convergence of an Algorithm for Subspace Identification from Partial Data
• Active Matrix Factorization for Surveys
• Active Algorithms For Preference Learning Problems with Multiple Populations
• Asymptotic Log-Det Rank Minimization via (Alternating) Iteratively Reweighted Least Squares
• Implicit Regularization in Matrix Sensing via Mirror Descent
• Adjusting Leverage Scores by Row Weighting: A Practical Approach to Coherent Matrix Completion
• CUR Algorithm with Incomplete Matrix Observation
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• Fast and Provable Algorithms for Spectrally Sparse Signal Reconstruction via Low-Rank Hankel Matrix Completion
• Dictionary and Image Recovery from Incomplete and Random Measurements
• Similarity Learning via Adaptive Regression and Its Application to Image Retrieval
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
• kappa_SQ: A Matlab package for randomized sampling of matrices with orthonormal columns
• Ranking Recovery from Limited Comparisons using Low-Rank Matrix Completion
• Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion; Some Statistical and Algorithmic Theory for Adaptive-Impute
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
• On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
• Online Algorithms for Factorization-Based Structure from Motion
• Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering
• Bridging and Improving Theoretical and Computational Electric Impedance Tomography via Data Completion
• Collaborative Self-Attention for Recommender Systems
• Rank-Constrained Least-Squares: Prediction and Inference
• On Recovering the Best Rank-r Approximation from Few Entries
• Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers
• Robust Correlation Clustering with Asymmetric Noise
• Efficient Map Prediction via Low-Rank Matrix Completion
• Multi-weight Matrix Completion with Arbitrary Subspace Prior Information
• To lie or not to lie in a subspace
• Riemannian Conjugate Gradient Descent Method for Third-Order Tensor Completion
• Matrix optimization based Euclidean embedding with outliers
• NoisyCUR: An algorithm for two-cost budgeted matrix completion
• Information Theory of Matrix Completion
• Robust Matrix Completion with Mixed Data Types
• Convex Optimization Learning of Faithful Euclidean Distance Representations in Nonlinear Dimensionality Reduction
• A Splitting Augmented Lagrangian Method for Low Multilinear-Rank Tensor Recovery
• Stochastic gradient descent for linear least squares problems with partially observed data
• Deep Latent Factor Model for Collaborative Filtering
• Binary matrix completion with nonconvex regularizers
• Noisy Tensor Completion for Tensors with a Sparse Canonical Polyadic Factor
• Low-rank matrix recovery via iteratively reweighted least squares minimization
• Learning Parameters for Weighted Matrix Completion via Empirical Estimation
• Clipped Matrix Completion: A Remedy for Ceiling Effects
• Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
• Collaborative Filtering with Information-Rich and Information-Sparse Entities