Local and Global Linear Convergence of General Low-rank Matrix Recovery Problems

arXiv2104.13348MaRDI QIDQ6366277FDOQ6366277

Yingjie Bi, Javad Lavaei, Haixiang Zhang

Publication date: 27 April 2021

Abstract: We study the convergence rate of gradient-based local search methods for solving low-rank matrix recovery problems with general objectives in both symmetric and asymmetric cases, under the assumption of the restricted isometry property. First, we develop a new technique to verify the Polyak-Lojasiewicz inequality in a neighborhood of the global minimizers, which leads to a local linear convergence region for the gradient descent method. Second, based on the local convergence result and a sharp strict saddle property proven in this paper, we present two new conditions that guarantee the global linear convergence of the perturbed gradient descent method. The developed local and global convergence results provide much stronger theoretical guarantees than the existing results. As a by-product, this work significantly improves the existing bounds on the RIP constant required to guarantee the non-existence of spurious solutions.

This page was built for publication: Local and Global Linear Convergence of General Low-rank Matrix Recovery Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6366277)