Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries
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.
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
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}
}
EUVIMED