Research On Constrained Low Rank Representation Algorithm And Its Applications

In recent years,with the rapid development in computer and Internet technology,people can easily access massive amounts of data.The data is high-dimensional,complicated,and usually contains large amounts of noise and redundant information.How to achieve the low-dimensional representation and explore the underlying structure of high-dimensional data is a very challenging problem.As an important research topic in pattern recognition,machine learning and computer vision,low rank representation(LRR)can effectively capture the low-dimensional subspace structure of high-dimensional data and reveal the structural characteristic of data noise.Due to its effectiveness and practicability,low rank representation has been widely applied in subspace clustering,semi-supervised learning,and visual tracking,etc.The main idea of LRR is to represent the data matrix as a linear combination of the bases in a given dictionary matrix and let the rank of the coefficient matrix of the linear combination to be the lowest by solving the rank minimization problem.Constrained low rank representation algoritllm can further reveal the structural information of the data by designing different constraints on the coefficient matrix,which is the focus of current research.From the perspective of definition,development process and the specific application direction,exisiting constrained LRR methods can be divided into three classes:basic constraint LRR,sparse constraint LRR and manifold constraint LRR.Due to the data in different application scenes is complex,the low rank structure information is inaccurate,the other structural information is not fully utilized and the interference of data noise is uncertain,the ability to reveal the essential structure of data of the methods belonging to the three classes should be improved,and the results of the quantitative performance evaluation of these methods need to be enhanced.To achieve this goal,this paper proposes several novel constrained LRR methods based on studying many state-of-the-art LRR methods.Generally,the main contributions of this thesis are as follows:(1)A robust low rank representation algorithm based on weighted Schatten-p norm and Lq norm(RLRR)is proposed for subspace clustering.In order to better approximate the rank function and describe different noises,RLRR achieves low rank property via the new formulation with weighted Schatten-p norm and Lq norm.Specifically,the nuclear norm is generalized to be the Schatten-p norm and different weights are assigned to the singular values,and thus it can approximate the rank function more accurately.In addition,Lq norm is further incorporated into RLRR to model different noises and improve the robustness.An efficient algorithm based on the inexact augmented Lagrange multiplier method is designed for the formulated problem.Compared with several state-of-the-art subspace clustering methods,the robustness of the proposed method is better and the clustering performance is enhanced.The average clustering error rates on Extend Yale B dataset under illumination variation,Gauss noise and block occlusion are lower than those of SPN,which are 2.42%,5.10%and 4.30%lower respectively.(2)A fast low rank representation algorithm based on L2,p norm(FLRR)is proposed for subspace clustering.LRR requires to calculate multiple singular value decomposition in calculation process,which leads to low computational efficiency.Therefore,we propose an improved algorithm to not only ensure the accuracy and robustness,but also improve the computational efficiency.Speciflcally,the nuclear norm and L2,1 norm in LRR are generalized to be the Schatten-p norm and L2,q norm,respectively.The new model is more general and robust than LRR.Then,we decompose the data matrix by QR decomposition and convert the new model into a small-scale L2,p norm minimization problem,which requires no SVD and thus has low computational cost.Experimental results on synthetic dataset,public image dataset and motion segmentation dataset demonstrate the superiority of the proposed method in terms of clustering error rate and running time.Especially,the running time of FLRR is faster than that of LRR 2?4 times on the public image dataset.(3)A semi-supervised low rank representation algorithm based on smooth rank approximation and weighted sparse constraint(SSLRR)is proposed for semi-supervised learning.SSLRR improves the low rank and sparse term in the nonnegative low rank sparse graph respectively,so that it can capture both the global subspace structure and locally linear structure exactly.When building the objective function,the logarithm function instead of the nuclear norm is used to approximate the rank function smoothly.Meanwhile,the shape interaction information and the label information of labeled samples are used to build the weighted sparsity constraint term.The objective function is solved by a linearized alternating direction method with adaptive penalty and the graph construction can be restructured.Finally?a semi-supervised classification framework based on local and global consistency is used to finish the learning task.When the number of label samples is 10%,the classification accuracy of SSLRR on ORL,Extend Yale B,PIE and USPS datasets can reach 82.94%,93.50%,83.97%and 92.99%respectively,and more than 12 state-of-the-art semi-supervised learning algorithms based on low rank representation and classical graph,which verify the validity of SSLRR.(4)A visual tracking algorithm based on low rank representation and sparse manifold constraint(LRSMT)is proposed.In order to find the global and local structure information of the particles in the visual tracking algorithm based on particle filter,LRSMT represents particles by dictionary templates,and adds low rank,sparse and manifold constraints on the representation coefficient.Specifically,we utilize an elastic net regularizer over singular values of coefficient matrix to capture the low rank structures of particles,and build a Laplacian graph to capture the manifold structure of particles.Meanwhile,we prune and select candidate particles by exploiting temporal consistency,and dynamically update the dictionary template to further improve the performance of LRSMT.Finally,we use the LADMAP method to optimize the algorithm in the particle filter framework.Compared with 14 state-of-the-art tracking methods in the 50 challenging video sequences of the OTB target tracking dataset qualitatively and quantitatively,the AUC value and the accuracy index of LRSMT are 53.8%and 71.7%respectively,which are higher than those of the other comparison methods.It shows that the tracking performance of the proposed algorithm is better.To sum up,the first work of this paper studies the basic low rank constraint of the constrained LRR algorithm.By accurately capturing the low rank structure information of the data and processing the different noise,we can improve the robustness of the subspace clustering algorithm.The second work not only ensures the robustness,but also improves the efficiency of the algorithm.The third work discusses the low rank and sparse constraints of the algorithm and improves the performance of semi-supervised learning by using the global subspace structure inf'ormation and local linear structure information.The fourth work discusses the application of algorithm in visual tracking by considering the low rank,sparsity and manifold constraints,which improves the tracking results of the traditional algorithms.Considering the complexity of the model,the four works present a progressive relationship,from simple to complex.Considering the practicability of the model,the first three works are focused on the algorithm research,while the fourth work is focused on the practical application.Thus,this paper realizes the transition from theory to application.