تقرير
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 |
الوصف غير متاح. |