{
  "id": "1503.02596",
  "version": "v1",
  "published": "2015-03-09T18:12:58.000Z",
  "updated": "2015-03-09T18:12:58.000Z",
  "title": "A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion",
  "authors": [
    "Daniel L. Pimentel-Alarcón",
    "Nigel Boston",
    "Robert D. Nowak"
  ],
  "comment": "17 pages",
  "categories": [
    "stat.ML",
    "cs.LG",
    "math.AG"
  ],
  "abstract": "Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. An incomplete $d \\times N$ matrix is $\\textit{finitely completable}$ if there are at most finitely many rank-$r$ matrices that agree with all its observed entries. Finite completability is the tipping point in LRMC, as a few additional samples of a finitely completable matrix guarantee its $\\textit{unique}$ completability. The main contribution of this paper is a full characterization of finitely completable observation sets. We use this characterization to derive sufficient deterministic sampling conditions for unique completability. We also show that under uniform random sampling schemes, these conditions are satisfied with high probability if at least $\\mathscr{O}(\\max\\{r,\\log d \\})$ entries per column are observed.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-03-09T18:12:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "low-rank matrix completion",
      "deterministic sampling patterns",
      "characterization",
      "derive sufficient deterministic sampling conditions",
      "completability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150302596P"
    }
  }
}