Algorithms For Low-rank Matrix And Tensor Completion Problems

The most important research aspect in matrix completion is to recover an unknown matrix with low-rank or approximately low-rank from constraints of its sample entries. A natural generalization of matrix completion is tensor completion. This thesis focuses on the model and the corresponding algorithm for the matrix completion problem and tensor completion problem. The major contributions of this thesis are as follow:1. We propose a new unconstraint model for matrix completion problem based on nuclear norm and indicator function and design a proximal point algorithm (PPA-IF) to solve it. The advantage of the model is that there is no regularization parameter and it unifies two constrained optimization problems (noiseless and noisy matrix completion problems). Then the convergence of our algorithm is established strictly. The numerical results suggest that significant improvement can be achieved by our algorithm compared to the other reported methods.2. The nuclear norm is the best convex approximation of the rank function over the set of matrices with spectral norm less than or equal to one, however there is a great difference between the two function. To reconcile this imbalance, we proposed a series of nonconvex models and the corresponding algorithms.(1) Firstly, we use a smoothed function-Hyperbolic Tangent function to approximate the rank function, and then using gradient projection method (HTA) to minimize it. We report numerical results for solving randomly generated matrix completion problems and image recovery problems. Numerical results show that accuracy of HTA is higher than others and the requisite number of sampling to recover a matrix is typically reduced.(2) In order to decrease the gap between the nuclear norm and the rank function, we add weight vector in the nuclear norm and build a model of minimizing weighted nuclear norm. Based on the majorization-minimization approach, we propose a weighted soft-thresholding algorithm which is used to solve the model of minimizing weighted nuclear norm. Focusing on the matrices generated randomly and image recovery problems, our proposed algorithm experimentally shows a significant improvement with respect to the accuracy and running time in comparison with the existing matrix completion algorithms.(3) We give a new non-convex function-exponential type function to instead of rank function. We make some numerical comparison between our algorithms and the state-of-the-art method on randomly generated matrices, Jester data and image recovery problems, the results suggest that our method is more effective and promising.(4) We propose a unified nonconvex model framework, by which many nonconvex models and some previously mentioned models can be obtained as special cases of the general framework. Then we use Difference of Convex functions (DC) programming and DC Algorithms (DCA) to solve the model. The experiment results suggest that our methods are more effective and promising. 3. We improve the hard thresholding algorithm. Most algorithms about hard thresholding use the negative gradient direction of the object function as search direction. But the main drawback of choosing the negative gradient direction is making the sequence of the iterations be subject to zigzags. Inspired by semi-iterative method, we present the semi-iterative hard thresholding algorithm. Compared to other iterative shrinkage algorithms, the performances of our proposed algorithm show a clear improvment in computation time.4. We introduce the weighted nuclear norm for tensor and develop majorization-minimization weighted soft thresholding algorithm to solve tensor completion problems. In addition, we apply the semi-iterative method to the iterative hard thresholding algorithm for tensor completion problem and improve the descent direction. The experiment results demonstrate the effectiveness of the improved algorithm.