Weighted Matrix Completion and Recovery with Prior Subspace Information

Dehui Yang, Michael Wakin, Armin Eftekhari

Research output: Contribution to journalArticlepeer-review

38 Citations (Scopus)

Abstract

An incoherent low-rank matrix can be efficiently reconstructed after observing a few of its entries at random, and then, solving a convex program that minimizes the nuclear norm. In many applications, in addition to these entries, potentially valuable prior knowledge about the column and row spaces of the matrix is also available to the practitioner. In this paper, we incorporate this prior knowledge in matrix completion - by minimizing a weighted nuclear norm - and precisely quantify any improvements. In particular, we find in theory that reliable prior knowledge reduces the sample complexity of matrix completion by a logarithmic factor, and the observed improvement in numerical simulations is considerably more magnified. We also present similar results for the closely related problem of matrix recovery from generic linear measurements.

Original languageEnglish
Pages (from-to)4044-4071
Number of pages28
JournalIEEE Transactions on Information Theory
Volume64
Issue number6
DOIs
Publication statusPublished - 16 Mar 2018
Externally publishedYes

Keywords

  • Weighted matrix completion
  • convex optimization
  • nuclear norm minimization

Fingerprint

Dive into the research topics of 'Weighted Matrix Completion and Recovery with Prior Subspace Information'. Together they form a unique fingerprint.

Cite this