The Power of Convex Relaxation: Near-Optimal Matrix Completion

DOI10.1109/TIT.2010.2044061zbMath1366.15021OpenAlexW2134332047WikidataQ63694333 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

Random matrices (probabilistic aspects) (60B20) Semidefinite programming (90C22) Optimality conditions and duality in mathematical programming (90C46) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Matrix completion problems (15A83)

Related Items

Matrix Completion Methods for Causal Panel Data Models, Convergence bounds for empirical nonlinear least-squares, Spectral gap in random bipartite biregular graphs and applications, Low Permutation-rank Matrices: Structural Properties and Noisy Completion, Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery, 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, Low Rank Tensor Manifold Learning, FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank–Wolfe Algorithms and Conditional Gradients, Self-calibration and biconvex compressive sensing, Iterative Collaborative Filtering for Sparse Matrix Estimation, Unnamed Item, Tensor Completion in Hierarchical Tensor Representations, Sensitivity Analysis for Mirror-Stratifiable Convex Functions, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, 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, Unnamed Item, Unnamed Item, GNMR: A Provable One-Line Algorithm for Low Rank Matrix Recovery, A universal rank approximation method for matrix completion, The Geometry of Rank-One Tensor Completion, Quadratic Growth Conditions for Convex Matrix Optimization Problems Associated with Spectral Functions, Tensor completion by multi-rank via unitary transformation, Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising, Tensor completion with noisy side information, Decomposition of Variation of Mixed Variables by a Latent Mixed Gaussian Copula Model, Unnamed Item, 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, Unnamed Item, 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, Importance sampling in signal processing applications, 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, Desingularization of Bounded-Rank Matrix Sets, Large Margin Low Rank Tensor Analysis, Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization, Efficient and feasible state tomography of quantum many-body systems, Geometric Methods on Low-Rank Matrix and Tensor Manifolds, Algebraic Methods for Tensor Data, On the equivalence between low-rank matrix completion and tensor rank, Unnamed Item, Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Matrix Denoising for Weighted Loss Functions and Heterogeneous Signals, On the Simplicity and Conditioning of Low Rank Semidefinite Programs, ELASTIC-NET REGULARIZATION FOR LOW-RANK MATRIX RECOVERY, 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, Introduction, Unnamed Item, Proximal Distance Algorithms: Theory and Examples, 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, 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, Dynamic Assortment Personalization in High Dimensions, Multiple imputation for continuous variables using a Bayesian principal component analysis, Minimizing Sum of Truncated Convex Functions and Its Applications, Imputation of Mixed Data With Multilevel Singular Value Decomposition, Structured random measurements in signal processing, Unnamed Item, Unnamed Item, Matrix completion via minimizing an approximate rank, Regularization and the small-ball method II: complexity dependent error rates, An alternating minimization method for robust principal component analysis, 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, An Efficient Gauss--Newton Algorithm for Symmetric Low-Rank Product Matrix Approximations, Numerical solution of an inverse random source problem for the time fractional diffusion equation via PhaseLift, Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization, Weighted lp − l1 minimization methods for block sparse recovery and rank minimization, Unnamed Item, Approximate matrix completion based on cavity method, 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, A novel robust principal component analysis method for image and video processing., Optimal large-scale quantum state tomography with Pauli measurements, Multivariate GARCH estimation via a Bregman-proximal trust-region method, A quadratically convergent algorithm for structured low-rank approximation, A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm, 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, 1-bit matrix completion: PAC-Bayesian analysis of a variational approximation, The non-convex sparse problem with nonnegative constraint for signal reconstruction, On tensor completion via nuclear norm minimization, Global optimality condition and fixed point continuation algorithm for non-Lipschitz \(\ell_p\) regularized matrix 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, Stable analysis of compressive principal component pursuit, Matrix completion discriminant analysis, 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, Low Tucker rank tensor recovery via ADMM based on exact and inexact iteratively reweighted algorithms, Matrix completion by singular value thresholding: sharp bounds, High-dimensional covariance matrix estimation with missing observations, Exact minimum rank approximation via Schatten \(p\)-norm minimization, TILT: transform invariant low-rank textures, Low-rank tensor completion by Riemannian optimization, Remote sensing via \(\ell_1\)-minimization, Random perturbation of low rank matrices: improving classical bounds, Compressed sensing and matrix completion with constant proportion of corruptions, Affine matrix rank minimization problem via non-convex fraction function penalty, A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality, Tensor factorization using auxiliary information, Accelerated linearized Bregman method, Low rank matrix completion by alternating steepest descent methods, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Selecting the number of components in principal component analysis using cross-validation approximations, Second order accurate distributed eigenvector computation for extremely large matrices, Adaptive confidence sets for matrix completion, A new nonconvex approach to low-rank matrix completion with application to image inpainting, A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm, Von Neumann entropy penalization and low-rank matrix estimation, The space decomposition theory for a class of eigenvalue optimizations, Matrix factorization for evolution data, First-order optimality condition of basis pursuit denoise problem, Linear total variation approximate regularized nuclear norm optimization for matrix completion, Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, Cross: efficient low-rank tensor completion, A new approximation of the matrix rank function and its application to matrix rank minimization, A new algorithm for positive semidefinite matrix completion, Level-set methods for convex optimization, Phase retrieval from Fourier measurements with masks, Low-rank matrix recovery using Gabidulin codes in characteristic zero, A modified augmented Lagrange multiplier algorithm for Toeplitz matrix completion, Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics, Max-norm optimization for robust matrix recovery, Robust matrix completion, Tensor completion using total variation and low-rank matrix factorization, 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, Low-rank matrix completion using nuclear norm minimization and facial reduction, Block tensor train decomposition for missing data estimation, An alternating direction algorithm for matrix completion with nonnegative factors, On the subdifferential of symmetric convex functions of the spectrum for symmetric and orthogonally decomposable tensors, Convergence of fixed-point continuation algorithms for matrix rank minimization, Templates for convex cone problems with applications to sparse signal recovery, Fixed point and Bregman iterative methods for matrix rank minimization, On polynomial time methods for exact low-rank tensor completion, Matrix factorization for multivariate time series analysis, Estimation of high-dimensional low-rank matrices, Optimal selection of reduced rank estimators of high-dimensional matrices, Some empirical advances in matrix completion, 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, Explicit frames for deterministic phase retrieval via PhaseLift, Inference on tissue transplantation experiments, Riemannian gradient descent methods for graph-regularized matrix completion, Low-rank matrix completion in a general non-orthogonal basis, Numerical comparisons between Bayesian and frequentist low-rank matrix completion: estimation accuracy and uncertainty quantification, 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, 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, Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction, Low-rank factorization for rank minimization with nonconvex regularizers, Learning non-parametric basis independent models from point queries via low-rank methods, 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, Rank minimization with applications to image noise removal, High resolution 3D imaging in MIMO radar with sparse array, An alternating direction method with continuation for nonconvex low 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, Heteroskedastic PCA: algorithm, optimality, and applications, Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching, Variational analysis of the Ky Fan \(k\)-norm, Low tubal rank tensor recovery using the Bürer-Monteiro factorisation approach. Application to optical coherence tomography, 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, Adaptive estimation in multivariate response regression with hidden variables, A new double-regularized regression using Liu and Lasso regularization, Relaxed leverage sampling for low-rank matrix completion, Proximal Markov chain Monte Carlo algorithms, 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, Parallel stochastic gradient algorithms for large-scale matrix completion, Deterministic algorithms for matrix completion, Alternating proximal gradient method for convex minimization, Low rank tensor recovery via iterative hard thresholding, Entropy numbers of embeddings of Schatten classes, Matrix completion methods for the total electron content video reconstruction, An approximation method of CP rank for third-order tensor completion, Complex best \(r\)-term approximations almost always exist in finite dimensions, Seismic data reconstruction via weighted nuclear-norm minimization, 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, Spectral operators of matrices, An alternating minimization method for matrix completion problems, Nonsmooth rank-one matrix factorization landscape, A singular value \(p\)-shrinkage thresholding algorithm for low rank matrix recovery, Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution, Proximal linearization methods for Schatten \(p\)-quasi-norm minimization, A nonconvex approach to low-rank matrix completion using convex optimization, 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, Phase transitions in semidefinite relaxations, Two relaxation methods for rank minimization problems, Compressed sensing of low-rank plus sparse matrices, On the parameterized complexity of clustering problems for incomplete data, Characterization of sampling patterns for low-tt-rank tensor retrieval, An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion, Matrix completion for matrices with low-rank displacement, 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, 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, A proximal multiplier method for separable convex minimization, 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, Estimation in High Dimensions: A Geometric Perspective, Low Complexity Regularization of Linear Inverse Problems, Collaborative filtering with information-rich and~information-sparse entities, Tensor completion based on triple tubal nuclear norm, Pairwise constraint propagation via low-rank matrix recovery, High dimensional covariance matrix estimation using multi-factor models from incomplete information, Impossibility of dimension reduction in the nuclear norm, Matrix completion and tensor rank, 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, Guarantees of Riemannian Optimization for Low Rank Matrix Recovery, Matrix completion for cost reduction in finite element simulations under hybrid uncertainties, Riemannian Optimization for High-Dimensional Tensor Completion, Efficient Matrix Sensing Using Rank-1 Gaussian Measurements, An adaptation for iterative structured matrix completion, Low Rank Estimation of Similarities on Graphs, 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, On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint, Stable als approximation in the TT-format for rank-adaptive tensor completion, On the robustness of minimum norm interpolators and regularized empirical risk minimizers, 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, Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion, ROP: matrix recovery via rank-one projections, Matrix estimation by universal singular value thresholding, Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization, A Bayesian approach for noisy matrix completion: optimal rate under general sampling distribution, A mean value algorithm for Toeplitz matrix completion, Proof methods for robust low-rank matrix recovery, Optimization on the hierarchical Tucker manifold - applications to tensor completion, Low-CP-rank tensor completion via practical regularization, A smoothing proximal gradient algorithm for matrix rank minimization problem