تقرير
Nonconvex Deterministic Matrix Completion by Projected Gradient Descent Methods
| العنوان: | Nonconvex Deterministic Matrix Completion by Projected Gradient Descent Methods |
|---|---|
| المؤلفون: | Xu, Hang, Li, Song, Lin, Junhong |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control, Computer Science - 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. Comment: 41 pages, 3figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2401.06592 |
| رقم الأكسشن: | edsarx.2401.06592 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |