Pattern Recognition 42 (2009) 105 -- 114
Contents lists available at ScienceDirect
Pattern Recognition
journal homepage: www.elsevier.com/locate/pr
Extracting the optimal dimensionality for local tensor discriminant analysis
Feiping Nie
∗
, Shiming Xiang, Yangqiu Song, Changshui Zhang
Tsinghua National Laboratory for Information Science and Technology (TNList), Department of Automation, Tsinghua University, Beijing 100084, China
ARTICLE INFO ABSTRACT
Article history:
Received 2 November 2007
Received in revised form 3 March 2008
Accepted 5 March 2008
Keywords:
Optimal dimensionality
Local scatter
Tensor discriminant analysis
Alternating optimization
Supervised dimensionality reduction with tensor representation has attracted great interest in recent
years. It has been successfully applied to problems with tensor data, such as image and video recognition
tasks. However, in the tensor-based methods, how to select the suitable dimensions is a very important
problem. Since the number of possible dimension combinations exponentially increases with respect to
the order of tensor, m anually selecting the suitable dimensions becomes an impossible task in the case
of high-order tensor. In this paper, we aim at solving this important problem and propose an algorithm
to extract the optimal dimensionality for local tensor discriminant analysis. Experimental results on a toy
example and real-world data validate the effectiveness of the proposed method.
© 2008 Elsevier Ltd. All rights reserved.
1. Introduction
Dimensionality reduction is an important issue when facing high-
dimensional data, and supervised dimensionality reduction methods
have been proven to be more suitable for classification tasks than
those unsupervised methods. Linear discriminant analysis (LDA) is
one of the most popular supervised methods and has been widely
applied in many high-dimensional classification tasks.
Traditional LDA treats data as vectors, while in many real-world
applications, data are represented by tensor form. For example, im-
ages can be seen as second-order tensors and videos can be seen as
third-order tensors. Treating the tensor data as vectors will result
in two obvious disadvantages. First, the underlying spatial structure
in tensor data is destroyed. Second, the dimension of the vectors is
extremely high, which usually results in the small sample size (SSS)
problem [1] and heavy computation burden. Although many ap-
proaches have been proposed to solve the SSS problem [2--4], these
variants usually discard a subspace such that some important dis-
criminative information may be lost. Comparative study on these
approaches to attack the SSS problem can be found in Refs. [5,6].
Recently, a number of algorithms of discriminant analysis with
tensor representation have been proposed and attracted great in-
terest [7--11]. Tensor-based discriminant analysis directly treats the
data as tensor, and thus effectively avoids the problems derived from
treating data as vectors.
∗
Corresponding author. Tel.: +86 10 627 96 872; fax:+86 10 627 86 911.
E-mail addresses: feipingnie@gmail.com (F. Nie),
zcs@mail.tsinghua.edu.cn (C. Zhang).
0031-3203/$ - see front matter
© 2008 Elsevier Ltd. All rights reserved.
doi:10.1016/j.patcog.2008.03.012
However, there are some drawbacks in the tensor-based d iscrim-
inant analysis. As it is a direct extension of LDA, the limitation of
Gaussian assumption in LDA still exists. It may fail to find the opti-
mal discriminative projections if the class distribution is more com-
plex than Gaussian. Many algorithms have been proposed recently
to overcome this drawback in LDA [12--16]. The main idea in these
methods is to construct the local scatter matrices to replace the tra-
ditional scatter matrices, and the limitation of Gaussian distribution
in LDA can be effectively removed by using these local scatter ma-
trices.
For the dimension reduction algorithm, how to select the suit-
able dimensions is a very important problem. In the vector-based
methods, several algorithms have been proposed recently to solve
this problem [17,18]. However, for the tensor-based methods, this
problem becomes more important. The reason is that the number of
possible dimension combinations will exponentially increase with
respect to the order of tensor, manually selecting the suitable di-
mensions becomes an impossible task in the case of high-order ten-
sor. Therefore, automatically estimating the optimal dimensions for
tensor discriminant analysis is more desired in real applications.
In this paper, we combine the benefits of local scatters and tensor
representation and propose the local tensor discriminant analysis for
supervised dimensionality reduction. The algorithm effectively over-
comes the limitation of Gaussian assumption and the SSS problem.
Meanwhile, the optimal dimensions are automatically extracted by
algorithm itself to maximize the optimal value of a well-defined cri-
terion.
The rest of this paper is organized as follows: We introduce some
operators in tensor algebra in Section 2, and then define a criterion
for the proposed algorithm in Section 3. In Section 4 we propose
an optimization method to maximize this criterion. A theoretical