Benjamin Recht – Page 2 – Optimization Online

A Simpler Approach to Matrix Completion

Published: 2009/10/04, Updated: 2009/10/22

Convex Optimization, Data-Mining, Statistics compressed sensing, convex optimization, low-rank matrices, matrix completion, nuclear norm minimization, operator chernoff bound, random matrices

This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular … Read more

Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Published: 2007/06/28

Maryam Fazel

Benjamin Recht

Pablo A. Parrilo

Convex and Nonsmooth Optimization, Semi-definite Programming, Statistics compressed sensing, random matrices, rank minimization, semidefinite programming

The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, … Read more