Study On The Algorithms For Matrix Recovery With Noise Via Convex Optimization

Matrix recovery, also named robust principal component analysis, is the problem of recovering a low-rank matrix from an observed data matrix when the data matrix is corrupted by gross sparse errors. Extensive applications of matrix recovery can be found in diverse areas, such as statistics, background modeling, face recognition, machine learning, video denoising and so on.Moreover, if the observed data matrix has also been corrupted by a dense noise matrix in addition to gross sparse errors, then the problem of recovering a low-rank matrix from such an observed data matrix is called matrix recovery with noise. Recently, it has been shown that the problem can be solved by a convex program, named stable principal component pursuit.In this dissertation, we study the stable principal component pursuit problem and propose some new algorithms to solving it, the following are the main results.(i) We review the concept and properties of the singular value thresholding shrinkage operator and then present a more simple and shorter proof of its non-expansiveness based on the min-max theory and projection theory in convex optimization.(ii) By using the iterative thresholding technique, we propose an iterative thresholding algorithm for matrix recovery with noise and prove that it is linear convergent. Furthermore, based on the dual theory and by combining the Nesterov approach, the Nemirovski’s technique and the adaptive line search scheme, we obtain two variants of the iterative thresholding algorithm.(iii) We propose a fixed point iterative algorithm and prove convergence of it. The new algorithm is inspired by the fixed point iterative algorithm for matrix rank minimization.(iv) Finally, we test our proposed algorithms for some randomly generated problems and report the numerical results comparing with the accelerated proximal gradient(APG) algorithm. Numerical results show that the running time of the proposed algorithms are less than APG for some randomly generated test problems and the fixed point iterative algorithm is the best one.