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)

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 ⋮ Heteroskedastic PCA: algorithm, optimality, and applications

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