A Caltech Library Service

Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization

Recht, Benjamin and Xu, Weiyu and Hassibi, Babak (2008) Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization. In: 47th IEEE Conference on Decision and Control. CDC 2008. IEEE , Piscataway, NJ, pp. 3065-3070. ISBN 978-1-4244-3123-6.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Minimizing the rank of a matrix subject to constraints is a challenging is a challenging problem that arises in many control applications including controller design, realization theory and model reduction. This class of optimization problems, known as rank minimization, is NP-HARD, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic algorithm replaces the rank function with the nuclear norm—equal to the sum of the singular values—of the decision variable. In this paper, we provide a necessary and sufficient condition that quantifies when this heuristic successfully finds the minimum rank solution of a linear constraint set. We further show that most of the problems of interest in control can be formulated as rank minimization subject to such linear constraints. We additionally provide a probability distribution over instances of the affine rank minimization problem such that instances sampled from this distribution satisfy our conditions for success with overwhelming probability provided the number of constraints is appropriately large. Finally, we give empirical evidence that these probabilistic bounds provide accurate predictions of the heuristic’s performance in non-asymptotic scenarios.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2008 IEEE.
Record Number:CaltechAUTHORS:20150130-074855649
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54236
Deposited By: Shirley Slattery
Deposited On:30 Jan 2015 23:02
Last Modified:10 Nov 2021 20:30

Repository Staff Only: item control page