Research And Application Of Matrix Completion Algorithms

Matrix completion has found super extensive applications in data analysis,recommendation systems,image completion,Video noise reduction and machine learning.Matrix completion problem is generally solved by constructing two mathematical models : the kernel norm minimization function and the least squares approximation function.Most of algorithms used to solve this problem are based on the nuclear norm minimization model,such as singular value threshold truncation algorithm(SVT),Accelerated Proximal Gradient Algorithms(APG),and Augmented Lagrange Multiplier(ALM),etc.While these methods all have disadvantages of High computational complexity,slow iterative speed and long-time wasting and large storage space demanding.It's hard to solve the large scalar data settings analysis tasks.In this dissertation,we devoted to design an easy orthogonal random projection algorithm for these shortages.Randomization could lead to simpler matrix computation and shorter convergence time.And it can also obtain a better algorithm with more interpretable,regularized and robust output.Randomized algorithms are better than traditional numerical methods in modern computing architecture.The main innovations of this dissertation includes:(i)It shows that the classical singular value decomposition method and matrix completion approaches based on convex optimization solvers have difficulties and disadvantages mentioned before in computation process.And then designed an orthogonal random projection methods to solve this problems.It turned out that our new methods have a better convergence rate than others.(ii)We also applied this algorithm to the applications of image denoising restoration problem.Compared with other methods based on convex optimization,we have been proved its better performance.