The Methods Of Solving Low-Rank Matrix Completion Problems Efficiently

In the thesis, we consider the low-rank matrix completion problems:The problem arises in diverse areas such as statistics, image processing, computationalgeometry, signal processing, computer vision, and complexity of model. For instance, thefamous problem of Netfilx Prize. We also show that the maximizing the sparsity of a vectorover a convex set, which has many applications, is a special case of the RMP. Because of itsclosely relation to compressing sense, it has been a hot topic recently years, which is veryimportant in practice. In the thesis, we focus on the methods and its reasons, the contributionsof this thesis are as follows:(1).We all know that the matrix rank minimization problem is NP-hard in general due tothe combinational nature of the function rank(·), We illustrate that when M subject to somecertain conditions,we can complete it. In the thesis, we give the the theorem which show thatto get a computationally tractable approximation to (RMP), we can replace rank(X) by itsconvex envelope, which is known to be the nuclear norm X, This results in the followingnuclear norm minimization problem, which is the tightest convex relaxation to (RMP):(2).The main emphasis is the theoretical basis of these methods: The singular valuethresholding algorithm and fixed point iterative algorithm. The singular value thresholding algorithm is to solve the problem:which is closely related to minimizing the nuclear norm matrix completion problem.Whilethe row by row method is based on the properties of a semidefinite programming.(3).We give a method of rank minimization problem from another angle, in which wedo not minimize the nuclear norm to approximate rank minimization problem,instead weconsider the problem as follows:It can also be more efcient to approximate rank minimization problem, we give themethod accordingly based on alternate direction augmented Lagrangian multiplier method.