Sorry, you need to enable JavaScript to visit this website.

[Slides] Accelerating Iterative Hard Thresholding for Low-rank Matrix Completion via Adaptive Restart

Citation Author(s):
Trung Vu, Raviv Raich
Submitted by:
Trung Vu
Last updated:
10 May 2019 - 4:04pm
Document Type:
Presentation Slides
Document Year:
Trung Vu
Paper Code:


This paper introduces the use of adaptive restart to accelerate iterative hard thresholding (IHT) for low-rank matrix completion. First, we analyze the local convergence of accelerated IHT in the non-convex setting of matrix completion problem (MCP). We prove the linear convergence rate of the accelerated algorithm inside the region near the solution. Our analysis poses a major challenge to parameter selection for accelerated IHT when no prior knowledge of the "local Hessian condition number" is given. To address this issue, we propose a simple adaptive restart algorithm for MCP to recover the optimal rate of convergence at the solution, as motivated in [1]. Our numerical result verifies the theoretical analysis as well as demonstrates the outstanding performance of the proposed algorithm.

0 users have voted: