A Study On Sparse And Low-rank Machine Learning Problems

The rapid development of Internet technology has started the era of big data.Sparse learning and low-rank learning methods are important large-scale machine learning approaches,which have been widely used in many fields,such as computer vision,recommendation system,and bioinfor-matics.In this thesis,we conduct researches on selected topics of sparse and low-rank learning for Internet big-data,and the main contributions of this thesis are as follows:1.We propose an accelerated multi-class sparse SVM model based on screening.The training of multi-class sparse SVM is a challenging problem,especially when the the dataset scale and the number of classes is large.Based on the doubly sparsity of the multi-class sparse SVM model and our previous work on binary SVM,we proposed an accelerated training algorithm.Our proposed screening rules are static,compound,and safe:we only need to invoke the screening rules once before solving the model,then we can identify most of the feature and sample variables that are unrelated to the optima.This reduces the scale of opti-mization problem dramatically and leads to speedup of training without sacrificing prediction accuracy.We evaluate our method on synthetic datasets and real application datasets and the results indicate that our method can achieve 1-2 orders of magnitude speedup for the training procedure.2.We propose an online robust principal component analysis method based on truncated nu-clear norm regularization.Traditional robust PCA approaches suffer from heavy memory consumption and cannot process streaming data.We propose a novel online robust PCA ap-proach by utilizing truncated nuclear norm as accurate and robust non-convex surrogate of rank function.We discover the factorized formulation of truncated nuclear norm and thus can decompose the objective function as a summation of sample-wise cost.We then de-sign an alternating optimization framework to learn the principal subspace in online manner.The experimental results show that our method can learn accurate low-dimensional subspace estimation from streaming data.3.We propose a single pass sparse principal components subspace learning algorithm via sym-metric rank one projection.By combining low-rankness and sparsity,sparse principal com-ponent analysis can achieve low dimension subspace with good interpretability.We explore the problem of sparse PCA with an extremely compressed measurement,symmetric rank-one projection.In this case,we only have access to amplitude measurements of the rank-one projection of data samples,and thus it is a rather challenging problem.We propose a single pass sparse principal subspace learning method that can learn sparse principal subspace af-ter a single pass of the data in mini-batch manner.Our theoretical analysis shows that our algorithm converges to global optima,under certain assumptions.