Study On The Algorithms For Matrix Reconstruction Problem Via Convex Optimization

Matrix reconstruction has found extensive applications in diverse areas, such as statistics, image processing, recommendation system, machine learning, video denoising and so on. The matrix recon-struction technology based on convex optimization is an important data analysis tool, which is actually a generalization of the compressive sensing technology. Matrix reconstruction problems are mainly two kinds of problems:matrix completion and matrix recovery. Many algorithms have been proposed to solve these problems, but the existing algorithms have many problems in the computation load, iteration rate and the size of matrices. For example, the Singular Value Thresholding(SVT) algorithm has only a global convergence rate of O(1/N), where N is the number of iterations during optimization, which is too slow especially when dealing with large scale matrices. In addition, the Iterative Thresholding(IT) algorithm for Matrix Recovery problem requires a very large number of iterations to converge and it is difficult to choose suitable the step size. In this dissertation, we adopt some technique for speeding up the original algorithm. The main innovations of this dissertation includes:(i) we show that the adaptive line search scheme by Liu Jun et al is the same as the Nemirovski’s approach, and then modify it to obtain an accelerated Nemirovski’s technique algorithm and prove the convergence. Our preliminary computational results are very favorable. Furthermore, we will extend the accelerated Nemirovski’s algorithm to solve the matrix completion problem with linear inequality constraints.(ii) we propose the accelerated IT algorithm based on the accelerated Nemirovski’s technique and prove the convergence, it can achieve the convergence rate O(1/N2). The experimental results have demon-strated the efficiency and effectiveness of the proposed algorithm.