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 (only showing first 100 items - show all)

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

This page was built for publication: The Power of Convex Relaxation: Near-Optimal Matrix Completion