172
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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. In this paper, 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 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.

          Related collections

          Most cited references28

          • Record: found
          • Abstract: not found
          • Article: not found

          Compressed sensing

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Decoding by Linear Programming

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Sparse Approximate Solutions to Linear Systems

                Bookmark

                Author and article information

                Journal
                28 June 2007
                Article
                10.1137/070697835
                0706.4138
                471f4c85-bf33-43f9-816d-6117754ffaa6
                History
                Custom metadata
                90C25, 90C59, 15A52
                SIAM Review, Volume 52, Issue 3, pp. 471-501 (2010)
                math.OC math.ST stat.TH

                Comments

                Comment on this article