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 collaborative filtering, Euclidean embedding, multi-task learning, system identification, and controller design. Although specific instances can often be solved with specialized algorithms, the general affine rank minimization problem is NP-hard.

In this talk, I will show that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum rank solution can be recovered by minimizing the nuclear norm (also know as the Schatten 1 norm or the trace norm) over the given affine space. This norm minimization problem is convex and admits efficient algorithms that can be tailored to the structure of the equality constraints. I will present several random ensembles of equations where the restricted isometry property holds with overwhelming probability.

The techniques used in this analysis have strong parallels in the compressed sensing framework where one seeks to find the vector of smallest cardinality in an affine set. I will discuss how affine rank minimization generalizes this pre-existing concept and outline a dictionary relating concepts from cardinality minimization to those of rank minimization.

(joint work with Maryam Fazel and Pablo Parrilo)