Conference proceeding
Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization
2008 47th IEEE Conference on Decision and Control, pp.3065-3070
09/07/2008
DOI: 10.1109/CDC.2008.4739332
Abstract
Minimizing the rank of a matrix subject to constraints is a challenging
problem that arises in many applications in control theory, machine learning,
and discrete geometry. 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
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.
Details
- Title: Subtitle
- Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization
- Creators
- Benjamin Recht - California Institute of TechnologyWeiyu Xu - California Institute of TechnologyBabak Hassibi - California Institute of Technology
- Resource Type
- Conference proceeding
- Publication Details
- 2008 47th IEEE Conference on Decision and Control, pp.3065-3070
- DOI
- 10.1109/CDC.2008.4739332
- eISBN
- 9781424431243; 1424431247
- ISSN
- 0191-2216
- Language
- English
- Date published
- 09/07/2008
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197165502771
Metrics
15 Record Views