- TITLE: Guaranteed Minimum-Rank Solutions of Linear
Matrix Equations via Nuclear Norm Minimization.
- AUTHOR: Benjamin Recht, Maryam Fazel, Pablo A. Parrilo
- ABSTRACT: 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, the general affine rank minimization problem
is NP-hard. In this paper, we show that if a certain restricted
isometry property holds for the linear transformation defining the
constraints, the minimum rank solution can be recovered by solving a
convex optimization problem, namely the minimization of the nuclear
norm over the given affine space. We present several random ensembles
of equations where the restricted isometry property holds with
overwhelming probability. The techniques used in our analysis have
strong parallels in the compressed sensing framework. We discuss how
affine rank minimization generalizes this pre-existing concept and
outline a dictionary relating concepts from cardinality minimization
to those of rank minimization.
- Preprint: pdf file