The Research Of Low Rank Matrix Approximation Based Machine Learning Algorithms

In many machine learning problems, data can be represented in matrix form rather than vector form. Examples range from recommender systems, image/vedio analysis and so on. In these cases, low rank property plays a crucial role to learn the hidden structure of the original data. Therefore, the study of low rank approximation algorithms become more and more popular in the machine learning and related areas. Low rank approximation algorithms can be roughly categorized into two classes:(1) recover the low rank structure from data, which is probably incomplete; (2) improve the ability of machine learning models by the incorporation of low rank information. Although many algorithms have been proposed in both categories, their performance is far from satisfactory in both accuracy and efficiency. In this thesis, we propose a systematic study of low rank approximation problems from theoretical analysis to specific applications, including matrix completion problems, active learning and large scale image classification based on low rank regularization. In summary, the main novel contribution of this dissertation are as follows:1. To accelerate the traditional Singular Value Thresholding (SVT) algorithm for large scale matrix completion problems, in this thesis we propose an Accelerated Singular Value Thresholding (ASVT) algorithm which improves the convergence rate from O(1/N) for SVT to O(1/N2), where N is the number of iterations during optimization. Specifically, the dual problem of the nuclear norm minimization problem is derived and an adaptive line search scheme is introduced to solve this dual problem. Consequently, the optimal solution of the primary problem can be readily obtained from that of the dual problem. We have conducted a series of experiments on a synthetic dataset, a distance matrix dataset and a large movie rating dataset. The experimental results have demonstrated the efficiency and effectiveness of the proposed algorithm.2. To better solve the truncated nuclear norm based matrix completion problems, this thesis firstly reformulate the original truncated nuclear norm minimization problem with multiple constraints, where multiple constraints may slow down the convergence rate of alternating direction method of multipliers (ADMM). And then, we propose to solve the final opti-mization problem based on alternating direction method of multipliers with adaptive penalty (ADMMAP). In each iteration, we control the penalty of the objective function according to a novel update rule to speedup the convergence. Our empirical study shows encouraging results of the proposed algorithm in comparison to the state-of-the-art matrix completion algorithms on both synthetic and real visual datasets.3. To accurately select the most informative points (we called anchor points), this thesis proposes a novel framework named Active Learning via Neighborhood Reconstruction (ALNR) by taking into account the locality information directly during the selection. Unlike traditional active learning methods which reconstruct the target point by the linear combination of all the selected points, in our proposed ALNR, we propose to reconstruct the target point just by the local neighbor anchor points of the target point. Furthermore, the nearer neighbor anchor points should have a greater effect and the selected points distant from the target point should be penalized severely. We further develop an efficient two-stage iterative procedure to solve the final optimization problem. Our empirical study shows encouraging results of the proposed ALNR in comparison to other state-of-the-art active learning algorithms on both synthetic and real visual datasets.4. To better utilize the low rank information for the image classification problems, this thesis consider the problem of multi-class image classification when the classes behaviour has a low rank structure. That is, classes can be embedded into a low dimensional space. Traditional multi-class classification algorithms usually use nuclear norm to approximate the rank of the weight matrix. Considering the limited ability of the nuclear norm for the accurate approximation, we propose a new scalable large scale multi-class classification algorithm by using the recently proposed Truncated Nuclear Norm as a better surrogate of the rank operator of matrices along with multinomial logisitic loss. To solve the non-convex and non-smooth optimization problem, we further develop an efficient iterative procedure. In each iteration, by lifting the non-smooth convex subproblem into an infinite dimensional l\ norm regularized problem, a simple and efficient accelerated coordinate descent algorithm is applied to find the optimal solution. We conduct a series of evaluations on several public large scale image datasets, where the experimental results show the encouraging improvement of classification accuracy of the proposed algorithm in comparison with the state-of-the-art multi-class classification algorithms.