{
  "id": "0809.1260",
  "version": "v1",
  "published": "2008-09-07T23:54:15.000Z",
  "updated": "2008-09-07T23:54:15.000Z",
  "title": "Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization",
  "authors": [
    "Benjamin Recht",
    "Weiyu Xu",
    "Babak Hassibi"
  ],
  "comment": "21 pages, 3 figures. A short version of this paper will appear at the 47th IEEE Conference on Decision and Control",
  "categories": [
    "math.OC",
    "stat.CO",
    "stat.ML"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-09-07T23:54:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C25",
      "90C59",
      "15A52"
    ],
    "keywords": [
      "nuclear norm heuristic",
      "sufficient condition",
      "popular heuristic algorithm replaces",
      "affine rank minimization problem",
      "minimum rank solution"
    ],
    "tags": [
      "conference paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0809.1260R"
    }
  }
}