Skip to main content

Parsimonious Models and Matrix Rank Minimization

Maryam Fazel


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. The matrix rank minimization problem arises in linear system identification, statistical modeling of random processes, and data dimensionality reduction.

The rank minimization problem is known to be computationally intractable. This talk discusses a convex relaxation based on semidefinite programming, and presents recent results in understanding under what conditions the relaxation is guaranteed to work. We discuss connections with the field of Compressed Sensing, which has demonstrated that sparse signals and images can be recovered from apparently incomplete sets of measurements. We ask what other objects or structures might also be recovered from incomplete, limited measurements, and present results on recovering matrices from partial information. Such problems are generally underdetermined, but when the matrix is known to be low rank or approximately low rank, the search for solutions becomes feasible. Applications arise in machine learning, system identification, and signal processing.


Maryam Fazel is an Assistant Professor in Electrical Engineering at the University of Washington. She received her B.S. degree from Sharif University, Iran, ranking first in the nationwide university entrance exam, and her M.S. and Ph.D. degrees from Stanford University in 1997 and 2002, all in Electrical Engineering. Prior to joining UW, she was a Postdoctoral Researcher and later a Research Scientist in the Control and Dynamical Systems Department at Caltech. Her research interests are in systems and control theory, optimization (in particular convex optimization and approximations), algorithms, and their application to engineering and biological systems.

Maryam Fazel Headshot
Maryam Fazel
University of Washington
EEB 125
2 Dec 2008, 10:30am until 11:30am