Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
Authors: Christian Kümmerle, Juliane Sigl
JMLR 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We propose a new iteratively reweighted least squares (IRLS) algorithm for the recovery of a matrix X P Cd1ˆd2 of rank r ! minpd1, d2q from incomplete linear observations, solving a sequence of low complexity linear problems. The easily implementable algorithm, which we call harmonic mean iteratively reweighted least squares (HM-IRLS), optimizes a non-convex Schatten-p quasi-norm penalization to promote low-rankness and carries three major strengths, in particular for the matrix completion setting. First, we observe a remarkable global convergence behavior of the algorithm s iterates to the low-rank matrix for relevant, interesting cases, for which any other state-of-the-art optimization approach fails the recovery. Secondly, HM-IRLS exhibits an empirical recovery probability close to 1 even for a number of measurements very close to the theoretical lower bound rpd1 d2 rq, i.e., already for significantly fewer linear observations than any other tractable approach in the literature. Thirdly, HM-IRLS exhibits a locally superlinear rate of convergence (of order 2 p) if the linear observations fulfill a suitable null space property. While for the first two properties we have so far only strong empirical evidence, we prove the third property as our main theoretical result. [...] Numerical experiments and comparisons to state-of-the-art methods for low-rank matrix recovery are carried out in Section 5. |
| Researcher Affiliation | Academia | Christian K ummerle EMAIL Department of Mathematics Technische Universit at M unchen Boltzmannstr. 3, 85748 Garching/Munich, Germany Juliane Sigl EMAIL Department of Mathematics Technische Universit at M unchen Boltzmannstr. 3, 85748 Garching/Munich, Germany |
| Pseudocode | Yes | Algorithm 1 Harmonic Mean IRLS for low-rank matrix recovery (HM-IRLS) Input: A linear map Φ : Md1ˆd2 Ñ Cm, image Y Φp X0q of the ground truth matrix X0 P Md1ˆd2, rank estimate rr, non-convexity parameter 0 ă p ď 1. Output: Sequence p Xpnqqn0 n 1 Ă Md1ˆd2. Initialize n 0, ϵp0q 1 and Ă W p0q Id1d2 P Md1d2ˆd1d2. repeat Xpn 1q arg min Φp Xq Y }Xvec}2 ℓ2pĂ W pnqq ppĂ Wpnqq 1 Φ pΦ ppĂ Wpnqq 1 Φ q 1p Y q , (13) ϵpn 1q min ϵpnq, σrr 1p Xpn 1qq , (14) Ă W pn 1q 2 Upn 1qpsΣpn 1q d1 q2 p Upn 1q V pn 1qpsΣpn 1q d2 q2 p V pn 1q ı 1 , (15) where Upn 1q P Ud1 and V pn 1q P Ud2 are matrices containing the left and right singular vectors of Xpn 1q in its columns, and the sΣpn 1q dt are defined for t P t1, 2u according to (11). n n 1, until stopping criterion is met. Set n0 n. |
| Open Source Code | Yes | An implementation of HM-IRLS for matrix completion including code reproducing many conducted experiments is available at https://github.com/ckuemmerle/hm_irls. |
| Open Datasets | No | In the experiments, we sample pd1 ˆ d2q dimensional ground truth matrices X0 of rank r such that X0 UΣV , where U P Rd1ˆr and V P Rd2ˆr are independent matrices with i.i.d. standard Gaussian entries and Σ P Rrˆr is a diagonal matrix with i.i.d. standard Gaussian diagonal entries, independent from U and V . |
| Dataset Splits | No | The paper describes generating synthetic data for experiments and how measurements are sampled from this generated data (e.g., 'sampling m tρdfu entries of X0 uniformly'). However, it does not provide details on fixed train/test/validation splits for a pre-existing dataset. |
| Hardware Specification | No | The numerical experiments are conducted on Linux and Mac systems with MATLAB R2017b. [...] For the matrix completion case, this allows us to recover low-rank matrices up to, e.g., d1 d2 3000 on a single machine given very few entries with HM-IRLS. |
| Software Dependencies | Yes | The numerical experiments are conducted on Linux and Mac systems with MATLAB R2017b. |
| Experiment Setup | Yes | In the experiments, we sample pd1 ˆ d2q dimensional ground truth matrices X0 of rank r such that X0 UΣV , where U P Rd1ˆr and V P Rd2ˆr are independent matrices with i.i.d. standard Gaussian entries and Σ P Rrˆr is a diagonal matrix with i.i.d. standard Gaussian diagonal entries, independent from U and V . We choose d1 d2 40, r 10 and distinguish easy, hard and very hard problems corresponding to oversampling factors ρ of 2.0, 1.2 and 1.0, respectively. The algorithms are provided with the ground truth rank r and are stopped whenever the relative change of Frobenius norm }Xpnq Xpn 1q}F {}Xpn 1q}F drops below the threshold of 10 10 or a maximal iteration of iterations nmax is reached. |