Graph optimization for dimensionality reduction with sparsity constraints
Limei Zhang
a,b
, Songcan Chen
a,
n
, Lishan Qiao
b
a
Department of Computer Science and Engineering, Nanjing University of Aeronautics & Astronautics, 210016 Nanjing, PR China
b
Department of Mathematics Science, Liaocheng University, 252000 Liaocheng, PR China
article info
Article history:
Received 1 February 2011
Received in revised form
30 July 2011
Accepted 13 August 2011
Available online 23 August 2011
Keywords:
Dimensionality reduction
Graph construction
Sparse representation
Face recognition
abstract
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 Con-
straints (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 framew ork, resulting in an automatically updated graph.
Moreover, by applying an l
1
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 prop osed
method.
& 2011 Elsevier Ltd. All rights reserved.
1. Introduction
It is well known that dimensionality reducti on (DR) has generally
been used as a principled way to understand the high-dimensional
data such as image, text and video sequence. Recently, graph-based
DR methods become more and more popular in pattern recognition
and machine learning fields, due to the fact that graph is a powerful
tool to catch the structure information hidden in objects or data. In
fact, recent research [1] claimedthatmostexistingDRmethodscan
fall into a graph embedding framework. The representatives have
ISOMAP [2],LLE[3], Laplacian eigenmap [4] and locality preserving
projections (LPP) [5], just to name a few. Under such a framework,
one first constructs a graph from data in terms of some prior
knowledge available, and then based on the constructed graph learns
a projection matrix, which transforms the original high-dimension
data into a lower dimensional space. Among them, graph construc-
tion is crucial since the performanc es of these algorithms depe nd
heavily on how well the graph models the original data structure.
As a consequence, the methods for graph construction have
been widely studied in recent years, although building a high-
quality graph is still an open problem [6]. In general, most of the
graph construction processes can be decomposed into two steps.
Firstly, one constructs an adjacency graph by considering the
samples as nodes and linking some of them with edges according
to given rules such as k-nearest neighbors,
e
-ball neighborhood
and b-matching [4,5,7]. Secondly, a weight is assigned for each
edge. The often-used weight assignment ways include Heat
Kernel [4], Inverse Euclidean Distance [8] and Local Linear
Reconstruction [3], etc. All these graph construction methods
are quite flexible and can in principle be used for any graph-based
learning algorithms including DR, spectral clustering and semi-
supervised learning [1,7,9,10]. However, as pointed out in [10],
there is potential need that graph should be appropriate for the
subsequent learning task.
To establish an ‘‘appropriate’’ graph, Zhang et al. recently
presented an algorithm called Graph-optimized Locality Preser-
ving Projections (GoLPP) [11] for DR task, which optimizes graph
and projections simultaneously in one single objective function.
To the best of our knowledge, this is the first attempt to perform
graph optimization during a specific DR process, rather than
pre-define graph before DR as done in most of graph-based
algorithms [1]. Despite GoLPP obtains empirical superiority to
traditional LPP on some datasets, the graph resulted from GoLPP
usually loses traditional sparsity even though a sparse initial
graph is given in its iterative optimization.
To address this problem, in this paper, we propose a novel
strategy to conduct Graph Optimization for Dimensionality Reduc-
tion with Sparsity Constraints (GODRSC). The proposed method not
only shares the advantages of GoLPP with automatically adjustable
graph, but also has some additional desirable characteristics:
1) The sparsity of graph is held by replacing the entropy regular-
izer in GoLPP with an l
1
norm minimization. As pointed out in
[7], sparsification is important to graph since it can bring
higher efficiency, better accuracy and robustness to noise.
2) Interestingly, with adjustable graph, GODRSC essentially pro-
vides an extension to the sparsity preserving projections (SPP)
[12], a recently developed DR algorithm based on sparse
Contents lists available at SciVerse ScienceDirect
journal homepage: www.elsevier.com/locate/pr
Pattern Recognition
0031-3203/$ - see front matter & 2011 Elsevier Ltd. All rights reserved.
doi:10.1016/j.patcog.2011.08.015
n
Corresponding author. Tel.: þ86 25 84896481x12221; fax: þ 86 25 84892400.
E-mail address: s.chen@nuaa.edu.cn (S. Chen).
Pattern Recognition 45 (2012) 1205–1210