Sparsity preserving projections with applications to face recognition

Dimensionality reduction methods (DRs) have commonly been used as a principled way to understand the high-dimensional data such as face images. In this paper, we propose a new unsupervised DR method called sparsity preserving projections (SPP). Unlike many existing techniques such as local preserving projection (LPP) and neighborhood preserving embedding (NPE), where local neighborhood information is preserved during the DR procedure, SPP aims to preserve the sparse reconstructive relationship of the data, which is achieved by minimizing a L1 regularization-related objective function. The obtained projections are invariant to rotations, rescalings and translations of the data, and more importantly, they contain natural discriminating information even if no class labels are provided. Moreover, SPP chooses its neighborhood automatically and hence can be more conveniently used in practice compared to LPP and NPE. The feasibility and effectiveness of the proposed method is verified on three popular face databases (Yale, AR and Extended Yale B) with promising results.     

Exponential locality preserving projections for small sample size problem

Locality preserving projections (LPP) is a widely used manifold reduced dimensionality technique. However, it suffers from two problems: (1) small sample size problem and (2) the performance is sensitive to the neighborhood size k. In order to address these problems, we propose an exponential locality preserving projections (ELPP) by introducing the matrix exponential in this paper. ELPP avoids the singular of the matrices and obtains more valuable information for LPP. The experiments are conducted on three public face databases, ORL, Yale and Georgia Tech. The results show that the performances of ELPP is better than those of LPP and the state-of-the-art LPP Improved1.     

Enhanced locality preserving projections using robust path based similarity

Curse of dimensionality is a bothering problem in high dimensional data analysis. To enhance the performances of classification or clustering on these data, their dimensionalities should be reduced beforehand. Locality Preserving Projections (LPP) is a widely used linear dimensionality reduction method. It seeks a subspace in which the neighborhood graph structure of samples is preserved. However, like most dimensionality reduction methods based on graph embedding, LPP is sensitive to noise and outliers, and its effectiveness depends on choosing suitable parameters for constructing the neighborhood graph. Unfortunately, it is difficult to choose effective parameters for LPP. To address these problems, we propose an Enhanced LPP (ELPP) using a similarity metric based on robust path and a Semi-supervised ELPP (SELPP) with pairwise constraints. In comparison with original LPP, our methods are not only robust to noise and outliers, but also less sensitive to parameters selection. Besides, SELPP makes use of pairwise constraints more efficiently than other comparing methods. Experimental results on real world face databases confirm their effectiveness.     

稀疏判别分析

针对流形嵌入降维方法中在高维空间构建近邻图无益于后续工作,以及不容易给近邻大小和热核参数赋合适值的问题,提出一种稀疏判别分析算法（SEDA）。首先使用稀疏表示构建稀疏图保持数据的全局信息和几何结构,以克服流形嵌入方法的不足;其次,将稀疏保持作为正则化项使用Fisher判别准则,能够得到最优的投影。在一组高维数据集上的实验结果表明,SEDA是非常有效的半监督降维方法。     

无参数局部保持投影及人脸识别

局部保持投影(LPP)通过构造近邻图来保持样本的局部结构,在构图过程中,LPP面临复杂的参数选择问题.为解决此问题,提出无参数局部保持投影(PLPP)算法.首先设计一种无参数的构图方法,能够动态地获取样本的近邻点并配置相应的边权.其次,利用该构图方法,PLPP通过寻求最佳投影矩阵,用于保持样本在低维空间的局部结构.由于PLPP在构图过程中并未设置任何参数且采用余弦距离设置边权,因此PLPP计算更加方便快捷且对离群样本更具鲁棒性.另外,为进一步提升PLPP的识别性能,在PLPP的基础上通过加入样本的类别信息,提出监督的无参数局部保持投影算法(SPLPP).最后,在ORL、FERET及AR人脸库上的实验验证了PLPP与SPLPP的有效性.     

基于改进的局部保持投影高光谱图像分类研究*

针对高光谱图像分类中基于流形的降维方法进行了研究。提出一种改进的局部保持投影（LPP）方法即MLPP方法。该方法利用标签信息避免了传统LPP在邻接图构建中很难确定的邻域大小的选择问题,同时采用更能反映高维数据间相关性的统计特征量相关系数来衡量数据之间的相似程度。设计的权重矩阵既保持类内数据的几何结构,又最大化类间距离。而且MLPP不依赖任何参数和先验知识。在两个高光谱图像上的实验结果表明MLPP增加了不同光谱特征地物之间的可分性,在提高分类性能上明显优于其他传统的降维方法。     

基于协作表示和模糊渐进最大边界嵌入的特征抽取方法

针对图嵌入方法在构造邻域关系图的过程中,简单地将样本数据划入某一类的做法并不妥当的问题,提出了模糊渐进的隶属度表示方法。该方法借助模糊数学的思想,通过模糊渐进的隶属度,将样本归属于不同类别。针对图嵌入方法中分类器效率偏低的问题,引入了协作表示分类方法,该分类方法大幅度提高了算法的计算效率。基于这两点,提出了基于协作表示和模糊渐进最大边界嵌入的特征抽取算法。在ORL、AR人脸数据库上,以及USPS数字手写体数据库上的实验表明,该算法优于主成分分析(PCA)、线性鉴别分析(LDA)、局部保留投影(LPP)和边界Fisher分析(MFA)。     

Dimensionality reduction with adaptive graph

Graph-based dimensionality reduction (DR) methods have been applied successfully in many practical problems, such as face recognition, where graphs play a crucial role in modeling the data distribution or structure. However, the ideal graph is, in practice, difficult to discover. Usually, one needs to construct graph empirically according to various motivations, priors, or assumptions; this is independent of the subsequent DR mapping calculation. Different from the previous works, in this paper, we attempt to learn a graph closely linked with the DR process, and propose an algorithm called dimensionality reduction with adaptive graph (DRAG), whose idea is to, during seeking projection matrix, simultaneously learn a graph in the neighborhood of a prespecified one. Moreover, the pre-specified graph is treated as a noisy observation of the ideal one, and the square Frobenius divergence is used to measure their difference in the objective function. As a result, we achieve an elegant graph update formula which naturally fuses the original and transformed data information. In particular, the optimal graph is shown to be a weighted sum of the pre-defined graph in the original space and a new graph depending on transformed space. Empirical results on several face datasets demonstrate the effectiveness of the proposed algorithm.     

Graph optimization for dimensionality reduction with sparsity constraints

Graph-based dimensionality reduction (DR) methods play an increasingly important role in many machine learning and pattern recognition applications. In this paper, we propose a novel graph-based learning scheme to conduct Graph Optimization for Dimensionality Reduction with Sparsity Constraints (GODRSC). Different from most of graph-based DR methods where graphs are generally constructed in advance, GODRSC aims to simultaneously seek a graph and a projection matrix preserving such a graph in one unified framework, resulting in an automatically updated graph. Moreover, by applying an l₁ regularizer, a sparse graph is achieved, which models the “locality” structure of data and contains natural discriminating information. Finally, extensive experiments on several publicly available UCI and face databases verify the feasibility and effectiveness of the proposed method.     

Nonlinear process monitoring based on kernel global–local preserving projections

A new nonlinear dimensionality reduction method called kernel global–local preserving projections (KGLPP) is developed and applied for fault detection. KGLPP has the advantage of preserving global and local data structures simultaneously. The kernel principal component analysis (KPCA), which only preserves the global Euclidean structure of data, and the kernel locality preserving projections (KLPP), which only preserves the local neighborhood structure of data, are unified in the KGLPP framework. KPCA and KLPP can be easily derived from KGLPP by choosing some particular values of parameters. As a result, KGLPP is more powerful than KPCA and KLPP in capturing useful data characteristics. A KGLPP-based monitoring method is proposed for nonlinear processes. T² and SPE statistics are constructed in the feature space for fault detection. Case studies in a nonlinear system and in the Tennessee Eastman process demonstrate that the KGLPP-based method significantly outperforms KPCA, KLPP and GLPP-based methods, in terms of higher fault detection rates and better fault sensitivity.     

Robust hashing for multi-view data: Jointly learning low-rank kernelized similarity consensus and hash functions

Learning hash functions/codes for similarity search over multi-view data is attracting increasing attention, where similar hash codes are assigned to the data objects characterizing consistently neighborhood relationship across views. Traditional methods in this category inherently suffer three limitations: 1) they commonly adopt a two-stage scheme where similarity matrix is first constructed, followed by a subsequent hash function learning; 2) these methods are commonly developed on the assumption that data samples with multiple representations are noise-free,which is not practical in real-life applications; and 3) they often incur cumbersome training model caused by the neighborhood graph construction using all N points in the database (O(N)). In this paper, we motivate the problem of jointly and efficiently training the robust hash functions over data objects with multi-feature representations which may be noise corrupted. To achieve both the robustness and training efficiency, we propose an approach to effectively and efficiently learning low-rank kernelized¹ hash functions shared across views. Specifically, we utilize landmark graphs to construct tractable similarity matrices in multi-views to automatically discover neighborhood structure in the data. To learn robust hash functions, a latent low-rank kernel function is used to construct hash functions in order to accommodate linearly inseparable data. In particular, a latent kernelized similarity matrix is recovered by rank minimization on multiple kernel-based similarity matrices. Extensive experiments on real-world multi-view datasets validate the efficacy of our method in the presence of error corruptions.We use kernelized similarity rather than kernel, as it is not a squared symmetric matrix for data-landmark affinity matrix.     

Cliques with maximum/minimum edge neighborhood and neighborhood density

Given a graph G=(V,E) and a clique C of G, the edge neighborhood of C can be defined as the total number of edges running between C and V?C, being denoted by N(C). The density of the edge neighborhood N(C) can be set as the ratio (|N(C)|/(|C|·|V?C|)).This paper addresses maximum/minimum edge neighborhood and neighborhood density cliques in G. Two versions will be undertaken, by fixing, or not, the size of the cliques.From an optimization point of view these problems do not bring much novelty, as they can be seen as particular or special versions of weighted clique problems. However, from a practical point of view, they concentrate on certain kinds of properties of cliques, rather than their size, revealing clique's engagement in the graph. In fact, a maximum edge neighborhood clique should be strongly embraced in the graph, while a minimum edge neighborhood clique should reveal an almost isolated strong component. In particular, special versions of the new problems allow to distinguish among cliques of the same size, namely among possible tied maximum cliques in the graph.We propose node based formulations for these edge based clique related problems. Using these models, we present computational results and suggest applications where the new problems can bring additional insights.     

Kernel class-wise locality preserving projection

In the recent years, the pattern recognition community paid more attention to a new kind of feature extraction method, the manifold learning methods, which attempt to project the original data into a lower dimensional feature space by preserving the local neighborhood structure. Among them, locality preserving projection (LPP) is one of the most promising feature extraction techniques. However, when LPP is applied to the classification tasks, it shows some limitations, such as the ignorance of the label information. In this paper, we propose a novel local structure based feature extraction method, called class-wise locality preserving projection (CLPP). CLPP utilizes class information to guide the procedure of feature extraction. In CLPP, the local structure of the original data is constructed according to a certain kind of similarity between data points, which takes special consideration of both the local information and the class information. The kernelized (nonlinear) counterpart of this linear feature extractor is also established in the paper. Moreover, a kernel version of CLPP namely Kernel CLPP (KCLPP) is developed through applying the kernel trick to CLPP to increase its performance on nonlinear feature extraction. Experiments on ORL face database and YALE face database are performed to test and evaluate the proposed algorithm.     

<Emphasis Type="Italic">υ</Emphasis>-Support vector machine based on discriminant sparse neighborhood preserving embedding

In this paper, we mainly focus on two issues (1) SVM is very sensitive to noise. (2) The solution of SVM does not take into consideration of the intrinsic structure and the discriminant information of the data. To address these two problems, we first propose an integration model to integrate both the local manifold structure and the local discriminant information into ?₁ graph embedding. Then we add the integration model into the objection function of υ-support vector machine. Therefore, a discriminant sparse neighborhood preserving embedding υ-support vector machine (υ-DSNPESVM) method is proposed. The theoretical analysis demonstrates that υ-DSNPESVM is a reasonable maximum margin classifier and can obtain a very lower generalization error upper bound by minimizing the integration model and the upper bound of margin error. Moreover, in the nonlinear case, we construct the kernel sparse representation-based ?₁ graph for υ-DSNPESVM, which is more conducive to improve the classification accuracy than ?₁ graph constructed in the original space. Experimental results on real datasets show the effectiveness of the proposed υ-DSNPESVM method.     

基于局部重构与全局保持的半监督维数约减算法

针对基于局部与全局保持的半监督维数约减算法(LGSSDR)对部域参数选择比较敏感以及对部域图边权值设定不够准确的问题,提出一种基于局部重构与全局保持的半监督维数约减算法(工RGPSSDR)。该算法通过最小化局部重构误差来确定部域图的边权值,在保持数据集局部结构的同时能够保持其全局结构。在Extended YaleB和 CMU PIE标准人脸库上的实验结果表明LRGPSSDR算法的分类性能要优于其它半监督维数约减算法。     

A two-dimensional Neighborhood Preserving Projection for appearance-based face recognition

This paper presents a two-dimensional Neighborhood Preserving Projection (2DNPP) for appearance-based face representation and recognition. 2DNPP enables us to directly use a feature input of 2D image matrices rather than 1D vectors. We use the same neighborhood weighting procedure that is involved in NPP to form the nearest neighbor affinity graph. Theoretical analysis of the connection between 2DNPP and other 2D methods is presented as well. We conduct extensive experimental verifications to evaluate the performance of 2DNPP on three face image datasets, i.e. ORL, UMIST, and AR face datasets. The results corroborate that 2DNPP outperforms the standard NPP approach across all experiments with respect to recognition rate and training time. 2DNPP delivers consistently promising results compared with other competing methods such as 2DLPP, 2DLDA, 2DPCA, ONPP, OLPP, LPP, LDA, and PCA.     

一种基于核的监督流形学习算法

针对流形学习算法——局部保持映射存在的参数选择及不能进行非线性特征提取的问题,提出一种基于核的监督流形学习算法.该算法作为局部保持映射算法的改进算法用样本类标识信息指导建立局部最近邻图,并在建立局部最近邻图使用无参数的相似度量.利用核方法来解决局部保持映射算法在处理线性不可分问题上的局限性问题.在两个常用数据库上验证本文算法的可行性和有效性.     

A regression model based on the nearest centroid neighborhood

The renowned k-nearest neighbor decision rule is widely used for classification tasks, where the label of any new sample is estimated based on a similarity criterion defined by an appropriate distance function. It has also been used successfully for regression problems where the purpose is to predict a continuous numeric label. However, some alternative neighborhood definitions, such as the surrounding neighborhood, have considered that the neighbors should fulfill not only the proximity property, but also a spatial location criterion. In this paper, we explore the use of the k-nearest centroid neighbor rule, which is based on the concept of surrounding neighborhood, for regression problems. Two support vector regression models were executed as reference. Experimentation over a wide collection of real-world data sets and using fifteen odd different values of k demonstrates that the regression algorithm based on the surrounding neighborhood significantly outperforms the traditional k-nearest neighborhood method and also a support vector regression model with a RBF kernel.     

Adaptive Graph Embedding Discriminant Projections

Graph embedding based learning method plays an increasingly significant role on dimensionality reduction (DR). However, the selection to neighbor parameters of graph is intractable. In this paper, we present a novel DR method called adaptive graph embedding discriminant projections (AGEDP). Compared with most existing DR methods based on graph embedding, such as marginal Fisher analysis which usually predefines the intraclass and interclass neighbor parameters, AGEDP applies all the homogeneous samples for constructing the intrinsic graph, and simultaneously selects heterogeneous samples within the neighborhood generated by the farthest homogeneous sample for constructing the penalty graph. Therefore, AGEDP not only greatly enhances the intraclass compactness and interclass separability, but also adaptively performs neighbor parameter selection which considers the fact that local manifold structure of each sample is generally different. Experiments on AR and COIL-20 datasets demonstrate the effectiveness of the proposed method for face recognition and object categorization, and especially under the interference of occlusion, noise and poses, it is superior to other graph embedding based methods with three different classifiers: nearest neighbor classifier, sparse representation classifier and linear regression classifier.