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

Abstract

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.