Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Finding Minimum-Rank Matrices via Nuclear Norm Minimization

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. 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 (the sum of the singular values) 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. This is joint work with Ben Recht (Caltech) and Maryam Fazel (U. Washington).

Type of Seminar:
Public Seminar
Prof. Pablo A. Parrilo
Massachusetts Institute of Technology
Jan 23, 2008   17:15 /

ETH Zurich, Gloriastrasse 35, Building ETZ, Room E6
Contact Person:

Prof. M. Morari
No downloadable files available.
Biographical Sketch:
Pablo A. Parrilo received an Electronics Engineering undergraduate degree from the University of Buenos Aires, and a Ph.D. in Control and Dynamical Systems from the California Institute of Technology in 1995 and 2000, respectively. He has held short-term visiting appointments at the University of California at Santa Barbara (Physics), Lund Institute of Technology (Automatic Control), and UC Berkeley (Mathematics). From October 2001 through September 2004, he was Assistant Professor of Analysis and Control Systems at the Automatic Control Laboratory of the Swiss Federal Institute of Technology (ETH Zurich). He is currently the Finmeccanica Career Development Associate Professor of Engineering at the Department of Electrical Engineering and Computer Science of the Massachusetts Institute of Technology, where he is also affiliated with the Laboratory for Information and Decision Systems (LIDS) and the Operations Research Center (ORC). Prof. Parrilo is the recipient of the 2005 Donald P. Eckman Award of the American Automatic Control Council, as well as the triennial SIAM Activity Group on Control and Systems Theory (SIAG/CST) Prize. He was also a finalist for the Tucker Prize of the Mathematical Programming Society for the years 2000-2003. He is currently in the Board of Directors of the Foundations of Computational Mathematics (FoCM) society, an Associate Editor of the IEEE Transactions on Automatic Control, and a member of the Editorial Board of the MPS/SIAM Book Series on Optimization. His research interests include optimization methods for engineering applications, control and identification of uncertain complex systems, robustness analysis and synthesis, and the development and application of computational tools based on convex optimization and algorithmic algebra to practically relevant engineering problems.