Recovery guarantee of weighted low-rank approximation via alternating minimization
Authors: Yuanzhi Li, Yingyu Liang, Andrej Risteski
ICML 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide provable recovery guarantee of weighted low-rank via a simple alternating minimization algorithm. These provide the first theoretical results for weighted low-rank approximation via alternating minimization with nonbinary deterministic weights, significantly generalizing those for matrix completion, the special case with binary weights, since our assumptions are similar or weaker than those made in existing works. The guarantee is proved by showing that the distance between the intermediate solution and the ground truth is improved at each iteration |
| Researcher Affiliation | Academia | Yuanzhi Li YUANZHIL@CS.PRINCETON.EDU Yingyu Liang YINGYUL@CS.PRINCETON.EDU Andrej Risteski RISTESKI@CS.PRINCETON.EDU Princeton University, 35 Olden St, Princeton, NJ 08540 USA |
| Pseudocode | Yes | Algorithm 1 Main Algorithm (ALT) Input: Noisy observation M, weight matrix W, number of iterations T 1: Initialize Y1 using either Y1 = SVDINITIAL(M, W) or Y1 = RANDINITIAL 2: for t = 1, 2, ..., T do 3: e Xt+1 = argmin X Rn k M XY t W 4: Xt+1 = CLIP( e Xt+1) 5: Xt+1 = QR(Xt+1) 6: e Yt+1 = argmin Y Rn k M Xt+1Y W 7: Yt+1 = CLIP( e Yt+1) 8: Yt+1 = QR(Yt+1) 9: end for Output: f M = XT +1YT |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | This is a theoretical paper and does not involve the use of specific datasets for training. Thus, no information about publicly available datasets is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve dataset splits for training, validation, or testing. Thus, no information on specific dataset splits is provided. |
| Hardware Specification | No | This is a theoretical paper and does not describe any experimental setup involving specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper focusing on mathematical guarantees and algorithms. It does not describe any specific software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | This paper is theoretical and focuses on providing provable guarantees for an algorithm. It defines the algorithm's steps and initialization strategies but does not describe an 'experimental setup' with specific hyperparameters or training configurations for empirical evaluation. |