An accelerated alternating directional method with non-monotone technique for matrix recovery

Abstract

Low-rank and sparse structures have been frequently exploited in matrix recovery and robust PCA problems. In this paper, we develop an alternating directional method and its variant equipped with the non-monotone search procedure for solving a non-convex optimization model of low-rank and sparse matrix recovery problems, where the concerned matrix with incomplete data is separable into a low-rank part and a sparse part. The main idea is to use the alternating minimization method for the low-rank matrix part, and to use the non-monotone line search technique for the sparse matrix part to iteratively update, respectively. To some extent, the non-monotone strategy relaxes the single-step descent into a multi-step descent and then greatly improves the performance of the alternating directional method. Theoretically, we prove the global convergence of the two proposed algorithms under some mild conditions. Finally, the comparison of numerical experiments shows that the alternate directional method with non-monotone technique is more effective than the original monotone method and the previous method. The efficiency and effectiveness of the proposed algorithms are demonstrated by solving some instances of random incomplete matrix recovery problems and some problems of the background modeling in video processing.

Keywords

• matrix recovery
• alternating directional methods
• non-monotone search
• low-rank sparse structure