2021/06/24 by Pini Zilber, Zilber, Pini, Boaz Nadler +1 · 2 citations
Earth and Planetary Sciences · Engineering · Medicine · #15A83 (Primary) 49M15 #65F55 (Secondary) #Advanced MRI Techniques and Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Seismic Imaging and Inversion Techniques #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2106.12933
openalex publication_date 2021/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Low rank matrix recovery problems, including matrix completion and matrix sensing, appear in a broad range of applications. In this work we present GNMR -- an extremely simple iterative algorithm for low rank matrix recovery, based on a Gauss-Newton linearization. On the theoretical front, we derive recovery guarantees for GNMR in both the matrix sensing and matrix completion settings. Some of these results improve upon the best currently known for other methods. A key property of GNMR is that it implicitly keeps the factor matrices approximately balanced throughout its iterations. On the empirical front, we show that for matrix completion with uniform sampling, GNMR performs better than several popular methods, especially when given very few observations close to the information limit.