Decentralized Nonconvex Low-rank Matrix Recovery

For the low-rank matrix recovery problem, algorithms that directly manipulate the low-rank matrix typically require computing the top singular values/vectors of the matrix and thus are computationally expensive. Matrix factorization is a computationally efficient nonconvex approach for low-rank matrix recovery, utilizing an alternating minimization or a gradient descent algorithm, and its theoretical properties have been investigated in recent years. However, the behavior of the factorization-based matrix recovery problem in the decentralized setting is still unknown when data are distributed on multiple nodes. In this paper, we consider the distributed gradient descent algorithm and establish its (local) linear convergence up to the approximation error. Numerical results are also presented to illustrate the convergence of the algorithm over a general network.