The Power of Convex Relaxation: Near-Optimal Matrix Completion

Emmanuel J. Candès, Terence Tao

Type: Preprint

Publication Date: 2009-01-01

Citations: 34

DOI: https://doi.org/10.48550/arxiv.0903.1476

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View
arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF	The Power of Convex Relaxation: Near-Optimal Matrix Completion	2010	Emmanuel J. Candès Terence Tao
+	Exact Matrix Completion via Convex Optimization	2008	Emmanuel J. Candès Benjamin Recht
+	Matrix completion with column manipulation: Near-optimal sample-robustness-rank tradeoffs	2011	Yudong Chen Huan Xu Constantine Caramanis Sujay Sanghavi
+ PDF	Exact matrix completion via convex optimization	2012	Emmanuel J. Candès Benjamin Recht
+ PDF	Matrix Completion With Noise	2010	Emmanuel J. Candès Yaniv Plan
+	Matrix Completion With Noise	2009	Emmanuel J. Candès Yaniv Plan
+ PDF Chat	Matrix Completion With Column Manipulation: Near-Optimal Sample-Robustness-Rank Tradeoffs	2015	Yudong Chen Huan Xu Constantine Caramanis Sujay Sanghavi
+	Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization	2019	Yuxin Chen Yuejie Chi Jianqing Fan Cong Ma Yuling Yan
+	Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization	2020	Yuxin Chen Yuejie Chi Jianqing Fan Cong Ma Yuling Yan
+	Robust matrix completion	2016	Olga Klopp Karim Lounici Alexandre B. Tsybakov
+	Robust Matrix Completion	2016	Olga Klopp Karim Lounici Alexandre B. Tsybakov
+	Large-Scale Convex Minimization with a Low-Rank Constraint	2011	Shai Shalev‐Shwartz Alon Gonen Ohad Shamir
+	A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion	2020	Quanming Yao Yaqing Wang James T. Kwok
+	Accurate low-rank matrix recovery from a small number of linear measurements	2009	Emmanuel J. Candès Yaniv Plan
+	Matrix Completion and Related Problems via Strong Duality	2017	Maria-Florina Balcan Yingyu Liang David P. Woodruff Hongyang Zhang
+	Low Permutation-rank Matrices: Structural Properties and Noisy Completion	2019	Nihar B. Shah Sivaraman Balakrishnan Martin J. Wainwright
+	Low Permutation-rank Matrices: Structural Properties and Noisy Completion	2017	Nihar B. Shah Sivaraman Balakrishnan Martin J. Wainwright
+	Interpretable Matrix Completion: A Discrete Optimization Approach	2018	Dimitris Bertsimas Michael Lingzhi Li
+	Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions	2023	Dimitris Bertsimas Ryan Cory-Wright Sean Lo Jean Pauphilet
+	Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions	2012	Alekh Agarwal Sahand Negahban Martin J. Wainwright

Works That Cite This (24)

Action	Title	Year	Authors
+	Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling	2020	Carolyn Kim Mohsen Bayati
+ PDF Chat	Scalable tensor factorizations for incomplete data	2010	Evrim Acar Daniel Dunlavy Tamara G. Kolda Morten Mørup
+	Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison	2009	Raghunandan H. Keshavan Andrea Montanari Sewoong Oh
+	Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing	2009	Junfeng Yang Yin Zhang
+ PDF Chat	Matrix completion from a few entries	2009	Raghunandan H. Keshavan Sewoong Oh Andrea Montanari
+	Matrix Completion from a Few Entries	2009	Raghunandan H. Keshavan Andrea Montanari Sewoong Oh
+	Matrix Completion from Noisy Entries	2009	Raghunandan H. Keshavan Andrea Montanari Sewoong Oh
+	Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization	2009	Shiqian Ma Donald Goldfarb Lifeng Chen
+ PDF Chat	A tensor-based method for missing traffic data completion	2013	Huachun Tan Guangdong Feng Jianshuai Feng Wei Wang Yujin Zhang Feng Li
+ PDF Chat	Fast Multiple-Splitting Algorithms for Convex Optimization	2012	Donald Goldfarb Shiqian Ma

Works Cited by This (12)

Action	Title	Year	Authors
+ PDF	The Concentration of Measure Phenomenon	2005	Michel Ledoux
+	Low-rank matrix factorization with attributes	2006	Jacob Abernethy Francis Bach Theodoros Evgeniou Jean‐Philippe Vert
+	Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices	2004	Maryam Fazel H. Hindi Stephen Boyd
+	Decoupling Inequalities for the Tail Probabilities of Multivariate $U$-Statistics	1995	Víctor H. de la Peña Stephen Montgomery-Smith
+ PDF	A remark on global positioning from local distances	2008	Amit Singer
+	On the rank minimization problem over a positive semidefinite linear matrix inequality	1997	Mehran Mesbahi George P. Papavassilopoulos
+	The mathematics of eigenvalue optimization	2003	Adrian S. Lewis
+ PDF Chat	Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information	2006	Emmanuel J. Candès Justin Romberg Terence Tao
+	Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization	2009	Shiqian Ma Donald Goldfarb Lifeng Chen
+	Uniqueness of Low-Rank Matrix Completion by Rigidity Theory	2009	Amit Singer Mihai Cucuringu