Accelerated reweighted nuclear norm minimization algorithm for low rank matrix recovery

•Propose an accelerated reweighted nuclear norm minimization algorithm to recover a low rank matrix.•Provide a new analysis for reweighted nuclear norm minimization algorithm.•Provide convergence analysis.•Numerical results show that our algorithm requires distinctly fewer iterations and less computational time than the original one.

In this paper we propose an accelerated reweighted nuclear norm minimization algorithm to recover a low rank matrix. Our approach differs from other iterative reweighted algorithms, as we design an accelerated procedure which makes the objective function descend further at every iteration. The proposed algorithm is the accelerated version of a state-of-the-art algorithm. We provide a new analysis of the original algorithm to derive our own accelerated version, and prove that our algorithm is guaranteed to converge to a stationary point of the reweighted nuclear norm minimization problem. Numerical results show that our algorithm requires distinctly fewer iterations and less computational time than the original one to achieve the same (or very close) accuracy, in some problem instances even require only about 50% computational time of the original one, and is also notably faster than several other state-of-the-art algorithms.