Nonconvex Deterministic Matrix Completion by Projected Gradient Descent Methods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914639658352640 |
|---|---|
| author | Xu, Hang Li, Song Lin, Junhong |
| author_facet | Xu, Hang Li, Song Lin, Junhong |
| contents | We study deterministic matrix completion problem, i.e., recovering a low-rank matrix from a few observed entries where the sampling set is chosen as the edge set of a Ramanujan graph. We first investigate projected gradient descent (PGD) applied to a Burer-Monteiro least-squares problem and show that it converges linearly to the incoherent ground-truth with respect to the condition number \k{appa} of ground-truth under a benign initialization and large samples. We next apply the scaled variant of PGD to deal with the ill-conditioned case when \k{appa} is large, and we show the algorithm converges at a linear rate independent of the condition number \k{appa} under similar conditions. Finally, we provide numerical experiments to corroborate our results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06592 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Nonconvex Deterministic Matrix Completion by Projected Gradient Descent Methods Xu, Hang Li, Song Lin, Junhong Optimization and Control Information Theory 90C26, 94A12 G.m We study deterministic matrix completion problem, i.e., recovering a low-rank matrix from a few observed entries where the sampling set is chosen as the edge set of a Ramanujan graph. We first investigate projected gradient descent (PGD) applied to a Burer-Monteiro least-squares problem and show that it converges linearly to the incoherent ground-truth with respect to the condition number \k{appa} of ground-truth under a benign initialization and large samples. We next apply the scaled variant of PGD to deal with the ill-conditioned case when \k{appa} is large, and we show the algorithm converges at a linear rate independent of the condition number \k{appa} under similar conditions. Finally, we provide numerical experiments to corroborate our results. |
| title | Nonconvex Deterministic Matrix Completion by Projected Gradient Descent Methods |
| topic | Optimization and Control Information Theory 90C26, 94A12 G.m |
| url | https://arxiv.org/abs/2401.06592 |