Mining useful clusters from high dimensional data have received significant attention of the computer vision and pattern recognition community in the recent years. Linear and nonlinear dimensionality reduction has played an important role to overcome the curse of dimensionality. However, often such methods are accompanied with three different problems: high computational complexity (usually associated with the nuclear norm minimization), nonconvexity (for matrix factorization methods), and susceptibility to gross corruptions in the data. In this paper, we propose a principal component analysis (PCA) based solution that overcomes these three issues and approximates a low-rank recovery method for high dimensional datasets. We target the low-rank recovery by enforcing two types of graph smoothness assumptions, one on the data samples and the other on the features by designing a convex optimization problem. The resulting algorithm is fast, efficient, and scalable for huge datasets with O(n log(n)) computational complexity in the number of data samples. It is also robust to gross corruptions in the dataset as well as to the model parameters. Clustering experiments on 7 benchmark datasets with different types of corruptions and background separation experiments on 3 video datasets show that our proposed model outperforms 10 state-of-the-art dimensionality reduction models. Our theoretical analysis proves that the proposed model is able to recover approximate low-rank representations with a bounded error for clusterable data.
a b s t r a c t Constructing an informative and discriminative graph plays an important role in various pattern recogni- tion tasks such as clustering and classification. Among the existing graph-based learning models, low-rank representation (LRR) is a very competitive one, which has been extensively employed in spectral cluster- ing and semi-supervised learning (SSL). In SSL, the graph is composed of both labeled and unlabeled sam- ples, where the edge weights are calculated based on the LRR coefficients. However, most of existing LRR related approaches fail to consider the geometrical structure of data, which has been shown beneficial for discriminative tasks. In this paper, we propose an enhanced LRR via sparse manifold adaption, termed manifold low-rank representation (MLRR), to learn low-rank data representation. MLRR can explicitly take the data local manifold structure into consideration, which can be identified by the geometric sparsity idea; specifically, the local tangent space of each data point was sought by solving a sparse representation objective. Therefore, the graph to depict the relationship of data points can be built once the manifold information is obtained. We incorporate a regularizer into LRR to make the learned coefficients preserve the geometric constraints revealed in the data space. As a result, MLRR combines both the global informa- tion emphasized by low-rank property and the local information emphasized by the identified manifold structure. Extensive experimental results on semi-supervised classification tasks demonstrate that MLRR is an excellent method in comparison with several state-of-the-art graph construction approaches.  This paper proposes a graph regularized low-rank sparse representation recovery (GLRSRR) method for sparse representation-based robust face recognition, in which both the training and test samples might be corrupted because of illumination variations, pose changes, and occlusions. On the one hand, GLRSRR imposes both the lowest-rank and sparsest constraints on the representation matrix of the training samples, which makes the recovered clean training samples discriminative while maintaining the global structure of data. Simultaneously, GLRSRR explicitly encodes the local structure information of data and the discriminative information of different classes by incorporating a graph regularization term, which further improves the discriminative ability of the recovered clean training samples for sparse representation. As a result, a test sample is compactly represented by more clean training samples from the correct class. On the other hand, since the error matrix obtained by GLRSRR can accurately and intuitively characterize the corruption and occlusion of face image, it can be used as occlusion dictionary for sparse representation. This will bring more accurate representations of the corrupted test samples. The experimental results on several benchmark face image databases manifest the effectiveness and robustness of GLRSRR. A graph regularized low-rank sparse representation recovery method is proposed.The recovered clean training samples have more discriminative ability.The obtained errors can accurately depict corruption and occlusion of face image.A corrupted test sample is encoded by more training samples from the correct class.Our method improves the performance of sparse representation-base classification.  Principal Component Analysis (PCA) is a widely used to learn a low-dimensional representation. In many applications, both vector data X and graph data W are available. Laplacian embedding is widely used for embedding graph data. We propose a graph-Laplacian PCA (gLPCA) to learn a low dimensional representation of X that incorporates graph structures encoded in W. This model has several advantages: (1) It is a data representation model. (2) It has a compact closed-form solution and can be efficiently computed. (3) It is capable to remove corruptions. Extensive experiments on 8 datasets show promising results on image reconstruction and significant improvement on clustering and classification. This paper proposes a new model of low-rank matrix factorization that incorporates manifold regularization to the matrix factorization. Superior to the graph-regularized nonnegative matrix factorization, this new regularization model has globally optimal and closed-form solutions. A direct algorithm (for data with small number of points) and an alternate iterative algorithm with inexact inner iteration (for large scale data) are proposed to solve the new model. A convergence analysis establishes the global convergence of the iterative algorithm. The efficiency and precision of the algorithm are demonstrated numerically through applications to six real-world datasets on clustering and classification. Performance comparison with existing algorithms shows the effectiveness of the proposed method for low-rank factorization in general.   Principal Component Analysis (PCA) is the most widely used tool for linear dimensionality reduction and clustering. Still it is highly sensitive to outliers and does not scale well with respect to the number of data samples. Robust PCA solves the first issue with a sparse penalty term. The second issue can be handled with the matrix factorization model, which is however non-convex. Besides, PCA based clustering can also be enhanced by using a graph of data similarity. In this article, we introduce a new model called 'Robust PCA on Graphs' which incorporates spectral graph regularization into the Robust PCA framework. Our proposed model benefits from 1) the robustness of principal components to occlusions and missing values, 2) enhanced low-rank recovery, 3) improved clustering property due to the graph smoothness assumption on the low-rank matrix, and 4) convexity of the resulting optimization problem. Extensive experiments on 8 benchmark, 3 video and 2 artificial datasets with corruptions clearly reveal that our model outperforms 10 other state-of-the-art models in its clustering and low-rank recovery tasks. This paper presents a novel low-rank matrix factorization method, named MultiHMMF, which incorporates multiple Hypergraph manifold regularization to the low-rank matrix factorization. In order to effectively exploit high order information among the data samples, the Hypergraph is introduced to model the local structure of the intrinsic manifold. Specifically, multiple Hypergraph regularization terms are separately constructed to consider the local invariance; the optimal intrinsic manifold is constructed by linearly combining multiple Hypergraph manifolds. Then, the regularization term is incorporated into a truncated singular value decomposition framework resulting in a unified objective function so that matrix factorization is changed into an optimization problem. Alternating optimization is used to solve the optimization problem, with the result that the low dimensional representation of data space is obtained. The experimental results of image clustering demonstrate that the proposed method outperforms state-of-the-art data representation methods. We propose a novel low rank matrix factorization method.We incorporate multiple Hypergraph manifold regularization to the matrix factorization.We adopt alternating optimization to solve the optimization problem. Manifold regularized sparse coding shows promising performance for various applications. The key issue that must be considered in the application is how to adaptively select the suitable graph hyper-parameters in manifold learning for the sparse coding task. Usually, cross validation is applied, but it does not necessarily scale up and easily leads to overfitting. In this article, multiple graph sparse coding (MGrSc) and multiple Hypergraph sparse coding (MHGrSc) for image representation are proposed. Inspired by the Ensemble Manifold Regularizer, we formulate multiple graph and multiple Hypergraph regularizers to guarantee the smoothness of sparse codes along the geodesics of a data manifold, which is characterized by fusing the multiple previously given graph Laplacians or Hypergraph Laplacians. Then, the proposed regularziers, respectively, are incorporated into the traditional sparse coding framework, which results in two unified objective functions of sparse coding. Alternating optimization is used to optimize the objective functions, and two, novel manifold regularized sparse coding algorithms are presented. The proposed two sparse coding methods learn both the composite manifold and the sparse coding jointly, and it is fully automatic for learning the graph hyper-parameters in the manifold learning. Image clustering tests on real world datasets demonstrated that the proposed sparse coding methods are superior to the state-of-the-art methods.