The Power of Convex Relaxation: Near-Optimal Matrix Completion

DOI10.1109/TIT.2010.2044061zbMath1366.15021WikidataQ63694333 ScholiaQ63694333MaRDI QIDQ5281478

Emmanuel J. Candès, Terence C. Tao

Publication date: 27 July 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.2010.2044061

Mathematics Subject Classification ID

60B20: Random matrices (probabilistic aspects)

90C22: Semidefinite programming

90C46: Optimality conditions and duality in mathematical programming

94A12: Signal theory (characterization, reconstruction, filtering, etc.)

15A83: Matrix completion problems

Related Items

Introduction, Unnamed Item, Unnamed Item, Sensitivity Analysis for Mirror-Stratifiable Convex Functions, Sparsity Constrained Estimation in Image Processing and Computer Vision, A General Theory of Singular Values with Applications to Signal Denoising, A Nonmonotone Alternating Updating Method for a Class of Matrix Factorization Problems, Quadratic Growth Conditions for Convex Matrix Optimization Problems Associated with Spectral Functions, Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1., Stable low-rank matrix recovery via null space properties, Approximate Global Minimizers to Pairwise Interaction Problems via Convex Relaxation, On the equivalence between low-rank matrix completion and tensor rank, Regularization and the small-ball method II: complexity dependent error rates, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, ELASTIC-NET REGULARIZATION FOR LOW-RANK MATRIX RECOVERY, Unnamed Item, Structured random measurements in signal processing, Unnamed Item, Unnamed Item, Complex symmetric completions of partial operator matrices, Incremental CP Tensor Decomposition by Alternating Minimization Method, Tensor Methods for Nonlinear Matrix Completion, Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries, Unnamed Item, Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization, Multilinear Compressive Sensing and an Application to Convolutional Linear Networks, Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion, ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching, Convergence bounds for empirical nonlinear least-squares, Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss, WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions, FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank–Wolfe Algorithms and Conditional Gradients, Iterative Collaborative Filtering for Sparse Matrix Estimation, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, GNMR: A Provable One-Line Algorithm for Low Rank Matrix Recovery, A universal rank approximation method for matrix completion, Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising, Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization, Efficient and feasible state tomography of quantum many-body systems, Algebraic Methods for Tensor Data, Matrix Denoising for Weighted Loss Functions and Heterogeneous Signals, On the Simplicity and Conditioning of Low Rank Semidefinite Programs, Spectral Operators of Matrices: Semismoothness and Characterizations of the Generalized Jacobian, Minimization of the difference of Nuclear and Frobenius norms for noisy low rank matrix recovery, Multiple imputation for continuous variables using a Bayesian principal component analysis, Matrix completion via minimizing an approximate rank, An alternating minimization method for robust principal component analysis, Low Permutation-rank Matrices: Structural Properties and Noisy Completion, Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery, The Geometry of Rank-One Tensor Completion, Importance sampling in signal processing applications, Desingularization of Bounded-Rank Matrix Sets, Large Margin Low Rank Tensor Analysis, Proximal Distance Algorithms: Theory and Examples, An Efficient Gauss--Newton Algorithm for Symmetric Low-Rank Product Matrix Approximations, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Singular, nonsingular, and bounded rank completions of ACI-matrices, Regularised PCA to denoise and visualise data, Phase Retrieval via Matrix Completion, Bayesian computation: a summary of the current state, and samples backwards and forwards, Numerical solution of an inverse random source problem for the time fractional diffusion equation via PhaseLift, Weighted lp − l1 minimization methods for block sparse recovery and rank minimization, Approximate matrix completion based on cavity method, Matrix Completion Methods for Causal Panel Data Models, Spectral gap in random bipartite biregular graphs and applications, Tensor completion by multi-rank via unitary transformation, Tensor completion with noisy side information, Decomposition of Variation of Mixed Variables by a Latent Mixed Gaussian Copula Model, Block-sparse recovery and rank minimization using a weighted \(l_p-l_q\) model, Black-box optimization on hyper-rectangle using recursive modified pattern search and application to ROC-based classification problem, Hierarchical clustering and matrix completion for the reconstruction of world input-output tables, Matrix completion with column outliers and sparse noise, Comparison of matrix norm sparsification, Detection thresholds in very sparse matrix completion, Fully-connected tensor network decomposition for robust tensor completion problem, An accelerated tensorial double proximal gradient method for total variation regularization problem, Bayesian uncertainty quantification for low-rank matrix completion, Universal Features for High-Dimensional Learning and Inference, Covariate-assisted matrix completion with multiple structural breaks, Robust matrix estimations meet Frank-Wolfe algorithm, Algorithmic Regularization in Model-Free Overparametrized Asymmetric Matrix Factorization, N-mode minimal tensor extrapolation methods, Geometric Methods on Low-Rank Matrix and Tensor Manifolds, Dynamic Assortment Personalization in High Dimensions, Minimizing Sum of Truncated Convex Functions and Its Applications, Imputation of Mixed Data With Multilevel Singular Value Decomposition, Low Rank Tensor Manifold Learning, Self-calibration and biconvex compressive sensing, Tensor Completion in Hierarchical Tensor Representations, An adaptation for iterative structured matrix completion, On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint, On the robustness of minimum norm interpolators and regularized empirical risk minimizers, Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion, Proof methods for robust low-rank matrix recovery, Low-CP-rank tensor completion via practical regularization, A smoothing proximal gradient algorithm for matrix rank minimization problem, Heteroskedastic PCA: algorithm, optimality, and applications, Low tubal rank tensor recovery using the Bürer-Monteiro factorisation approach. Application to optical coherence tomography, Adaptive estimation in multivariate response regression with hidden variables, A new double-regularized regression using Liu and Lasso regularization, Tight risk bound for high dimensional time series completion, Noisy tensor completion via the sum-of-squares hierarchy, Phase retrieval of complex and vector-valued functions, Augmented Lagrangian methods for convex matrix optimization problems, Matrix completion methods for the total electron content video reconstruction, Complex best \(r\)-term approximations almost always exist in finite dimensions, Guarantees of Riemannian optimization for low rank matrix completion, Optimal prediction in the linearly transformed spiked model, Exponential weights in multivariate regression and a low-rankness favoring prior, Manifold regularized matrix completion for multi-label learning with ADMM, An alternating minimization method for matrix completion problems, Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution, Robust PCA using nonconvex rank approximation and sparse regularizer, Synchronization problems in computer vision with closed-form solutions, Matrix completion with nonconvex regularization: spectral operators and scalable algorithms, Mean estimation with sub-Gaussian rates in polynomial time, Entrywise eigenvector analysis of random matrices with low expected rank, Concentration of tempered posteriors and of their variational approximations, Two relaxation methods for rank minimization problems, Characterization of sampling patterns for low-tt-rank tensor retrieval, Matrix completion for matrices with low-rank displacement, Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation, Normal approximation and confidence region of singular subspaces, Convergence of projected Landweber iteration for matrix rank minimization, Robust linear optimization under matrix completion, Homotopy method for matrix rank minimization based on the matrix hard thresholding method, Recovering low-rank and sparse matrix based on the truncated nuclear norm, Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach, Tensor completion based on triple tubal nuclear norm, Pairwise constraint propagation via low-rank matrix recovery, Impossibility of dimension reduction in the nuclear norm, Lasso meets horseshoe: a survey, A non-convex tensor rank approximation for tensor completion, Fundamental conditions on the sampling pattern for union of low-rank subspaces retrieval, Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers, Matrix completion for cost reduction in finite element simulations under hybrid uncertainties, Non-intrusive tensor reconstruction for high-dimensional random PDEs, Structured matrix estimation and completion, Nonparametric estimation of low rank matrix valued function, Two directional Laplacian pyramids with application to data imputation, Typical and generic ranks in matrix completion, Stable als approximation in the TT-format for rank-adaptive tensor completion, A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids, Analysis of singular value thresholding algorithm for matrix completion, ROP: matrix recovery via rank-one projections, Matrix estimation by universal singular value thresholding, A Bayesian approach for noisy matrix completion: optimal rate under general sampling distribution, A mean value algorithm for Toeplitz matrix completion, Optimization on the hierarchical Tucker manifold - applications to tensor completion, Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching, Variational analysis of the Ky Fan \(k\)-norm, Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery, \(S_{1/2}\) regularization methods and fixed point algorithms for affine rank minimization problems, Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction, Parallel stochastic gradient algorithms for large-scale matrix completion, Alternating proximal gradient method for convex minimization, Low rank tensor recovery via iterative hard thresholding, Entropy numbers of embeddings of Schatten classes, Spectral operators of matrices, A singular value \(p\)-shrinkage thresholding algorithm for low rank matrix recovery, Nuclear norm system identification with missing inputs and outputs, RIPless compressed sensing from anisotropic measurements, Asymptotic equivalence of quantum state tomography and noisy matrix completion, Noisy low-rank matrix completion with general sampling distribution, Efficient algorithms for robust and stable principal component pursuit problems, An introduction to a class of matrix cone programming, Collaborative filtering with information-rich and~information-sparse entities, High dimensional covariance matrix estimation using multi-factor models from incomplete information, Relaxed leverage sampling for low-rank matrix completion, Proximal Markov chain Monte Carlo algorithms, An approximation method of CP rank for third-order tensor completion, Nonsmooth rank-one matrix factorization landscape, Proximal linearization methods for Schatten \(p\)-quasi-norm minimization, Compressed sensing of low-rank plus sparse matrices, On the parameterized complexity of clustering problems for incomplete data, A proximal multiplier method for separable convex minimization, Estimation in High Dimensions: A Geometric Perspective, Low Complexity Regularization of Linear Inverse Problems, Matrix completion and tensor rank, Guarantees of Riemannian Optimization for Low Rank Matrix Recovery, Riemannian Optimization for High-Dimensional Tensor Completion, Efficient Matrix Sensing Using Rank-1 Gaussian Measurements, Low Rank Estimation of Similarities on Graphs, Deterministic algorithms for matrix completion, Seismic data reconstruction via weighted nuclear-norm minimization, A nonconvex approach to low-rank matrix completion using convex optimization, Phase transitions in semidefinite relaxations, An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion, Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization, Image cartoon-texture decomposition by a generalized non-convex low-rank minimization method, A singular value shrinkage thresholding algorithm for folded concave penalized low-rank matrix optimization problems, A two-phase rank-based algorithm for low-rank matrix completion, Euclidean Representation of Low-Rank Matrices and Its Geometric Properties, Further results on tensor nuclear norms, Imputed quantile tensor regression for near-sited spatial-temporal data, Rank-1 Matrix Differential Equations for Structured Eigenvalue Optimization., Concentration of measure bounds for matrix-variate data with missing values, Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals, Variational Bayesian inference for CP tensor completion with subspace information, Link Prediction for Egocentrically Sampled Networks, Low-rank matrix estimation via nonconvex optimization methods in multi-response errors-in-variables regression, Large factor model estimation by nuclear norm plus \(\ell_1\) norm penalization, A Zero-imputation Approach in Recommendation Systems with Data Missing Heterogeneously, The decimation scheme for symmetric matrix factorization, A data-adaptive dimension reduction for functional data via penalized low-rank approximation, Nonnegative Low Rank Matrix Completion by Riemannian Optimalization Methods, Precision matrix estimation under the horseshoe-like prior-penalty dual, Recent Theoretical Advances in Non-Convex Optimization, Numerical comparisons between Bayesian and frequentist low-rank matrix completion: estimation accuracy and uncertainty quantification, An alternating direction method with continuation for nonconvex low rank minimization, A novel robust principal component analysis method for image and video processing., Optimal large-scale quantum state tomography with Pauli measurements, A quadratically convergent algorithm for structured low-rank approximation, On the nuclear norm and the singular value decomposition of tensors, Matrix completion via max-norm constrained optimization, A rank-corrected procedure for matrix completion with fixed basis coefficients, Estimation of low rank density matrices: bounds in Schatten norms and other distances, The non-convex sparse problem with nonnegative constraint for signal reconstruction, On tensor completion via nuclear norm minimization, A graphical approach to the analysis of matrix completion, Improved recovery guarantees for phase retrieval from coded diffraction patterns, Low rank matrix recovery from rank one measurements, Low rank estimation of smooth kernels on graphs, The bounds of restricted isometry constants for low rank matrices recovery, Exact low-rank matrix completion from sparsely corrupted entries via adaptive outlier pursuit, Fast alternating linearization methods for minimizing the sum of two convex functions, High-dimensional covariance matrix estimation with missing observations, Exact minimum rank approximation via Schatten \(p\)-norm minimization, Low-rank tensor completion by Riemannian optimization, Remote sensing via \(\ell_1\)-minimization, Selecting the number of components in principal component analysis using cross-validation approximations, Von Neumann entropy penalization and low-rank matrix estimation, The space decomposition theory for a class of eigenvalue optimizations, First-order optimality condition of basis pursuit denoise problem, A new approximation of the matrix rank function and its application to matrix rank minimization, A modified augmented Lagrange multiplier algorithm for Toeplitz matrix completion, Finding a low-rank basis in a matrix subspace, MIMCA: multiple imputation for categorical variables with multiple correspondence analysis, Degrees of freedom in low rank matrix estimation, Convergence of fixed-point continuation algorithms for matrix rank minimization, Fixed point and Bregman iterative methods for matrix rank minimization, Estimation of high-dimensional low-rank matrices, Optimal selection of reduced rank estimators of high-dimensional matrices, Some empirical advances in matrix completion, A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm, Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, A new algorithm for positive semidefinite matrix completion, Max-norm optimization for robust matrix recovery, Robust matrix completion, An alternating direction algorithm for matrix completion with nonnegative factors, Explicit frames for deterministic phase retrieval via PhaseLift, Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction, Learning non-parametric basis independent models from point queries via low-rank methods, Rank minimization with applications to image noise removal, High resolution 3D imaging in MIMO radar with sparse array, Matrix completion by singular value thresholding: sharp bounds, Low rank matrix completion by alternating steepest descent methods, Multivariate GARCH estimation via a Bregman-proximal trust-region method, A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm, 1-bit matrix completion: PAC-Bayesian analysis of a variational approximation, Global optimality condition and fixed point continuation algorithm for non-Lipschitz \(\ell_p\) regularized matrix minimization, Stable analysis of compressive principal component pursuit, Matrix completion discriminant analysis, Low Tucker rank tensor recovery via ADMM based on exact and inexact iteratively reweighted algorithms, Random perturbation of low rank matrices: improving classical bounds, Affine matrix rank minimization problem via non-convex fraction function penalty, Adaptive confidence sets for matrix completion, A new nonconvex approach to low-rank matrix completion with application to image inpainting, Matrix factorization for evolution data, Linear total variation approximate regularized nuclear norm optimization for matrix completion, Cross: efficient low-rank tensor completion, Level-set methods for convex optimization, Low-rank matrix recovery using Gabidulin codes in characteristic zero, Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics, Tensor completion using total variation and low-rank matrix factorization, Low-rank matrix completion using nuclear norm minimization and facial reduction, Block tensor train decomposition for missing data estimation, Templates for convex cone problems with applications to sparse signal recovery, Flexible low-rank statistical modeling with missing data and side information, Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization, On the exponentially weighted aggregate with the Laplace prior, TILT: transform invariant low-rank textures, Compressed sensing and matrix completion with constant proportion of corruptions, A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality, Tensor factorization using auxiliary information, Accelerated linearized Bregman method, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Second order accurate distributed eigenvector computation for extremely large matrices, Phase retrieval from Fourier measurements with masks, On the subdifferential of symmetric convex functions of the spectrum for symmetric and orthogonally decomposable tensors, On polynomial time methods for exact low-rank tensor completion, Matrix factorization for multivariate time series analysis, A general self-adaptive relaxed-PPA method for convex programming with linear constraints, Estimation of the parameters of a weighted nuclear norm model and its application in image denoising, Inference on tissue transplantation experiments, Riemannian gradient descent methods for graph-regularized matrix completion, Low-rank matrix completion in a general non-orthogonal basis, Ranking recovery from limited pairwise comparisons using low-rank matrix completion, A selective overview of deep learning, New applications of matrix methods, Inductive matrix completion with feature selection, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, Low-rank factorization for rank minimization with nonconvex regularizers, Tensor theta norms and low rank recovery, Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data, A new method based on the manifold-alternative approximating for low-rank matrix completion, Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence, Tensor Q-rank: new data dependent definition of tensor rank