{
  "id": "1507.03566",
  "version": "v1",
  "published": "2015-07-13T19:45:28.000Z",
  "updated": "2015-07-13T19:45:28.000Z",
  "title": "Low-rank Solutions of Linear Matrix Equations via Procrustes Flow",
  "authors": [
    "Stephen Tu",
    "Ross Boczar",
    "Mahdi Soltanolkotabi",
    "Benjamin Recht"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "In this paper we study the problem of recovering an low-rank positive semidefinite matrix from linear measurements. Our algorithm, which we call Procrustes Flow, starts from an initial estimate obtained by a thresholding scheme followed by gradient descent on a non-convex objective. We show that as long as the measurements obey a standard restricted isometry property, our algorithm converges to the unknown matrix at a geometric rate. In the case of Gaussian measurements, such convergence occurs for a $n \\times n$ matrix of rank $r$ when the number of measurements exceeds a constant times $nr$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-07-13T19:45:28.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear matrix equations",
      "procrustes flow",
      "low-rank solutions",
      "standard restricted isometry property",
      "low-rank positive semidefinite matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150703566T"
    }
  }
}