TIME: 1:30-2:20 pm, April 29, 2008

PLACE: CSE 503

SPEAKER: Maryam Fazel
         Dept of Electrical Engineering
         University of Washington

TITLE: Finding Low-rank Matrices via Nuclear Norm Minimization

ABSTRACT:

In many engineering applications, notions such as order or dimension
of a model can be expressed as the rank of an appropriate matrix. To
choose simple models, we seek low-rank matrices. For example, a
low-rank matrix could correspond to a low-degree statistical model for
a random process, or an embedding in a low-dimensional space.

The rank minimization problem is known to be NP-hard. This talk
discusses a convex relaxation, minimizing the nuclear norm of the
matrix. We present recent results on guaranteed recovery of the lowest
rank matrix when the constraints are linear equalities and this linear
mapping satisfies a restricted isometry condition. This is a
generalization of the result by Candes and Tao (2004) from compressed
sensing, from the case of sparse vectors to that of low-rank matrices.