low-rank matrices – Optimization Online

SPECTRA – a Maple library for solving linear matrix inequalities in exact arithmetic

Published: 2016/11/05

Semi-definite Programming computer algebra, linear matrix inequalities, low-rank matrices, polynomial sums of squares, semidefinite programming

This document briefly describes our freely distributed Maple library {\sc spectra}, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required. ArticleDownload View PDF

A Simpler Approach to Matrix Completion

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

Benjamin Recht

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