EUVIMEDEUVIMED entdecken
Open Access

Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries

Jonathan Bauch, Boaz Nadler, Pini Zilber

SIAM Journal on Mathematics of Data Science · 2021-01 · 3 (1) · 439-465

DOI: 10.1137/20m1315294 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Mathematics of Data Science, online erschienen am 29.03.2021. Verfasst von Jonathan Bauch und 2 weiteren Autor:innen. Beteiligte Einrichtung: Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, 76100 Israel. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 51 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: NIGMS NIH HHS, National Institutes of Health, PAZY Foundation.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present a new, simple, and computationally efficient iterative method for low rank matrix completion. Our method is inspired by the class of factorization-type iterative algorithms, but substantially differs from them in the way the problem is cast. Precisely, given a target rank $r$, instead of optimizing on the manifold of rank $r$ matrices, we allow our interim estimated matrix to have a specific overparametrized rank $2r$ structure. Our algorithm, denoted R2RILS, for rank $2r$ iterative least squares, thus has low memory requirements, and at each iteration it solves a computationally cheap sparse least squares problem. We motivate our algorithm by its theoretical analysis for the simplified case of a rank 1 matrix. Empirically, R2RILS is able to recover ill-conditioned low rank matrices from very few observations---near the information limit---and it is stable to additive noise.

Schlagwörter

Stichwörter der Autor:innen

15A8365F55R2RILS algorithmlow ranklow rank matricesmatrix completion

Autor:innen und Institutionen

  • Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, 76100 Israel.

Förderung

  • NIGMS NIH HHS
  • National Institutes of Health
  • PAZY Foundation

Zitieren

APA

Bauch, J., Nadler, B., & Zilber, P. (2021). Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries. SIAM Journal on Mathematics of Data Science, 3(1), 439-465. https://doi.org/10.1137/20m1315294

Vancouver

Bauch J, Nadler B, Zilber P. Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries. SIAM Journal on Mathematics of Data Science. 2021;3(1):439-465. doi:10.1137/20m1315294

BibTeX
@article{Bauch2021,
  author = {Bauch, Jonathan and Nadler, Boaz and Zilber, Pini},
  title = {Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries},
  journal = {SIAM Journal on Mathematics of Data Science},
  year = {2021},
  volume = {3},
  number = {1},
  pages = {439--465},
  doi = {10.1137/20m1315294}
}
Kostenlos starten →