- 1 -
中国科技论文在线
Bilinear Lancros components for fast dimensionality
reduction and features extraction
Ren Chuanxian, Dai Daoqing
(Department of Mathematics, Sun Yat-Sen University, GuangZhou 510275)
Foundations: NSF of China (10771220, 90920007); the Ministry of Education of China (SRFDP-20070558043)
Brief author introduction:任传贤，（1984-），安徽阜阳，男，博士研究生。研究方向为模式识别与机器学
习
Correspondance author: 戴道清，（1963-），湖南桃源，男，教授，博导。主要研究方向为模式识别、小
波分析、生物信息学。发表论文 100多篇
Abstract: Generalized low rank approximation of matrix (GLRAM) method has received successful
application in pattern recognition and machine learning. We use bidirectional Lanczos components to
approximate the projective vectors obtained from eigenvalue decomposition in the GLRAM method,
where every data points keep the form of two dimensional matrix, instead of one dimensional vectors,
thus the time-consuming eigenvalue decomposition procedure is avoided. The method gradually
reduces the Frobenius norm based reconstruction error criterion, and lead to the approximation
converged to the accurate solution in a success of iterations. Experimental results on face recognition
and image classification show that our proposed new method is very efficient and effective.
Keywords:Patternrecognition;BilinearLancros Analysis;Dimensionality reduction;Features extraction;
Fast algorithm
0 Introduction
The problem of dimensionality reduction and feature extraction has recently received broad
attention in areas such as pattern recognition and machine learning, which aims to obtain more
compact representations of the data with limited loss of information, and it essentially belongs to
low-rank approximation of matrices. Traditional methods for dimensionality reduction and feature
extraction are based on the so-called vector space model, where each sample data is modeled as a
long vector and the whole data set is modeled as a large matrix [1,3,4]. The representation of data
by vectors in Euclidean space allows one to compute the similarity between data points, based on
the Euclidean distance or some other similarity metric [5].
Two-dimensional principal component analysis (2DPCA) [1-2] has been proven to be an
efficient tool for pattern recognition and image analysis. Encouraging experimental results have
been reported and discussed in the literature. PCA [4,6,7] is a bilinear method for
dimensionality reduction, which aims to simultaneously find the optimal projection subspaces in
the row and column directions of images without the matrix-to-vector transformation. That is, it
first constructs the so-called image covariance matrices from rows and columns of images and
then computes their eigenvectors as the projection vectors. Since the size of the image covariance
matrix is equal to the width and height of images, respectively, which is quite small compared
with the size of the covariance matrix used in PCA.
Nevertheless, PCA has to be performed in batch mode, it means that all the training
data has to be ready before we calculate the projection matrices. When the learning algorithm is
supposed to operate in a dynamical settings, that all the training data is not given in advance, and
new training samples may arrive at any time, and they have to be processed in an online manner.
Through matricizations of a -order tensor [9-11], PCA is successfully transferred to the
SVD of corresponding unfolded matrices in [4]. Experimental results on face recognition show
that the IBDPCA algorithm gives an efficient and effective approximation to the PCA
- 2 -
中国科技论文在线
method.
Ye [5] proposes a generalized low-rank approximation algorithm (GLRAM) directly on a
collection of matrices. Like PCA, GLRAM is shown to have the computational efficiency
in dimensionality reduction and feature extraction. An optimization problem which aims to
minimize the reconstruction (approximation) error is formulated and then an iterative procedure is
presented in [5]. Liang et al. [11-12] present theoretical analysis and some applications in face
images and handwriting character recognition. Equivalence between several non-iterative
algorithm is proven in [13]. Wang et al. [14] show that these matrices based 2-D algorithms are
equivalent to special cases of image block based feature extraction, ., partition each image into
several blocks and perform standard linear method on the aggregate of all image blocks. Moreover,
the method is extended to the higher-order tensor decomposition cases [15-18] and gives some
practical applications in pattern recognition and computer vision area.
However, all of the methods mentioned above compute the projection vectors by singular
value decomposition (SVD) or eigenvalue decomposition (EVD). For an matrix, the
corresponding computational complexity of a full SVD is while the
complexity of an EVD problem is . As a result, when computational efficiency is
critical, relatively high complexity will generate negative impact on real time applications.
In many data analysis applications, a matrix is multiplied by a vector and we wish to
perform this matrix-vector (mat-vec) product accurately in the space spanned by a few of the
major singular vectors of the matrix. Chen et al. [19] uses the Lanczos algorithm to compute a
sequence of vectors which progressively approximate . The new method is easy-to-update
recurrence formulas and low-cost relative to the direct SVD, and the approximating sequences
rapidly converge to in the major singular directions of , achieving the same goal as that of
the truncated SVD which preserves the major singular components. The effectiveness of this
approach is demonstrated on a few sample applications requiring dimension reduction.
The main differences between our BLC algorithm and Chen et al.'s method are compared and
listed here:
(1) The problem investigated in [19] is approximation of mat-vec product for preserving
the quality of the product in the major singular vector directions of matrix. Although Chen et al.
consider left projection approximation and right projection approximation respectively, they are
still based on vector space model, and it belongs to linear method.
(2) BLC aims to compute bidirectional transformations, which directly use two systems of
Lanczos components with certain orders, to substitute the eigenvectors of two matrices for fast
computation. Especially, our method focuses on the dimensionality reduction of a collections of
matrices instead of vectors and has its explicit objective function, thus it is a bilinear method.
Contributions
In this paper, we present a novel approach to alleviate the expensive EVD computation for
generalized low-rank approximation of matrix. The novelty lies in a new computational tool called
Lanczos algorithm. In the novel procedure, each datum is represented as a 2-D matrix, instead of a
vector, and the collection of data is represented as a collection of matrices or a -order tensor
[9,20], instead of a single data matrix. We formulate the problem of low rank approximations as
an optimization problem as [5] does, which approximates a collection of matrices with matrices of
lower rank. Then we derive an iterative algorithm, which resorting to Lanczos algorithm for
efficient computation and effective approximation. The obtained bilinear transformation is
particularly appropriate for data in matrix form, and often leads to lower computation cost in
- 3 -
中国科技论文在线
comparison to (bidirectional) EVD. To evaluate the efficiency and approximation performance of
the proposed algorithm, we have conducted extensive experiments for image classification and
face recognition on five well-known image data sets: ORL, FERET, PIE, COIL-20 and USPS,
where USPS consists of images of handwritten digits, COIL-20 is a database of gray-scale images
of 20 images, and the other three are face image datasets. Results show that when certain number
of Lanczos components are selected, our new method is competitive with GLRAM for
classification, while it has a much lower computation cost.
Therefore, the main advantages of our new approach including:
(1) The target of dimension reduction or data compression is 2-D matrices or -order
tensor, instead of 1-D vectors, which is able to preserving the intrinsic locality structure and leads
to better classification performance.
(2) We use bilinear Lanczos components to substitute the traditional eigenvectors or principal
components, and our approach can effectively reduce the computational cost so that the new
algorithm can be applied in the practical communities such as handwriting digit classification and
face recognition.
(3) In addition, a new concept called bilinear separability and a theoretical clue for selecting
suitable dimensionality parameters without losing classification information are also discussed in
this paper, which will give us new insight of bilinear transform and bilinear Lanczos components.
Organization of the paper
The rest of this paper is organized as follows. We give the problem formulation and a brief
review of Lanczos method in Section 1, and then propose the main algorithm of bilinear Lanczos
components and its complexity analysis. In Section 2 the parameter selection problem is studied,
. how much bilinear Lanczos components will be selected in the practical applications. A
performance study including misclassification rate and time consuming is provided in Section 3.
Conclusions and directions for future work can be found in Section 4.
1 Efficient low-rank approximations via bilinear Lanczos compon
ents
Generalized low-rank approximations of matrices: problem formulation
and applications
In this section, we study the problem of generalized low rank approximations of -order
tensor, which aims to approximate a collection of matrices with lower rank. A key difference
between this generalized problem and traditional low rank approximation problem is the data
representation model applied. Recall that the vector space model is applied for the traditional low
rank approximations, the vector space model leads to a simple and closed form solution by
computing the EVD of the data matrix. However, the EVD computation restricts its applicability
to matrices of small size. Instead, we apply a different data representation model, under which
each datum is represented as a matrix and the collection of data is represented as a collection of
matrices.
Let be the given n sample data in the training set, where h and c denote the
number of rows and columns respectively for each . We aim to compute two projection
matrices and with orthonormal columns, and n compressed matrices
such that closely approximates . Here, and are two
pre-specified parameters. Mathematically, the optimization problem can be formulated as [5]
- 4 -
中国科技论文在线
(1)
where denotes the Frobenius norm for a matrix.
The matrices and in the above approximations act as the bilinear transformations on
the data in matrix form. It is worth noting that the 's are not required to be diagonal throughout
this paper. Fig. 1 gives a vivid demonstration for the linear(a) and bilinear(b) dimensionality
reduction methods, where bilinear method is able to keep the intrinsic structure of the two
dimensional data.
Fig. 1 Demonstration of (a) linear and (b) bilinear dimensionality reduction.
The symmetric Lanczos algorithm
In this section, we investigate the Lanczos algorithm as a means to compute a sequence of
projection vectors which is faster than that of EVD based method.
Given a symmetric matrix and an initial unit vector , the Lanczos algorithm
builds an orthonormal basis of the order-k Krylov subspace [21-26]
where span denotes the spanned space or the set of all possible linear combinations of given
elements.
The Lanczos vectors ( ), computed by the algorithm satisfy the three-term
recurrence
with . The coefficients and are computed so as to ensure that
and . In exact arithmetic, it turns out that is orthogonal to
, so the vectors , form an orthonormal basis of the Krylov
subspace . An outline of the procedure is illustrated in Algorithm 1. The time cost of
the procedure is .
- 5 -
中国科技论文在线
Algorithm 1: The Lancros procedure.
Let , then an important equality which results from the algor
ithm is
Obviously, matrix is tridiagonal. An eigenvalue of is called a Ritz value, and if
is an associated eigenvector, is the associated Ritz vector. As increases, more and more
Ritz values and vectors will converge toward eigenvalues and eigenvectors of .
However, the theoretical orthogonality of the computed Lanczos vectors s is quickly lost in
practical applications. This loss of orthogonality is triggered by the convergence of one or more
eigenvectors [23]. There has been much research devoted to reinstating orthogonality. The
simplest approach is to reorthogonalize each new vector against each of the previous basis vectors.
This amounts to adding the following line of pseudo-code immediately after line 5 of Algorithm 1:
This additional full reorthogonalization step increases the computational cost of the Lanczos
procedure, but the advantages are that all the s are guaranteed to be numerically orthogonal, and
any subsequent process relying on the orthogonality is more rigorous [21]. It is important to add
here that there are other more cost effective reorthogonalization procedures known. The
best-known practical alternative to full reorthogonalization is partial reorthogonalization which
consists of taking a reorthogonalization step only when needed [25,26].
In this paper, we explore the bilinear Lanczos components as substitution of the singular
vectors for saving the expensive cost, and choose the full reorthogonalization technique as the
standard procedure. Specially, we will compute bi-directional Lanczos vectors, instead of
computing the singular vectors or eigenvectors, for simultaneous low-rank approximations of
matrices. Therefore, when computational efficiency is critical, this technique may be a favorable
alternative to the best rank-$k$ approximation.
- 6 -
中国科技论文在线
The bilinear Lanczos components algorithm
In this section, we first provide some propositions which are very useful for developing our
new method and then give the main algorithm of BLC.
Proposition 1 ([5]) Let , and be the optimal solution to the minimization
problem in Eq. (1), then for every .
Proposition 2 ([5]) Let , and be the optimal solution to the minimization
problem in Eq. (1), then and solve the following optimization problem:
Proposition 3 ([5]) Let , and be the optimal solution to the minimization
problem in Eq. (1), then
1) For a given , consists of the eigenvectors of the matrix
corresponding to the largest eigenvalues.
2) For a given , consists of the eigenvectors of the matrix
corresponding to the largest eigenvalues.
As we have pointed above, when the matrices for compressing is very large, the high
dimensionality will make the implementation of bi-directional EVD very time consuming.
Therefore, in this section, we resort to the Lanczos method to solve the approximate solution with
low computational complexity.
Specifically, let is the iteration steps, and be the initialized matrix of . Within the
-th cycle of the bilinear Lanczos components algorithm, we use to compute matrix
which plays the role of in Lanczos algorithm, then enter the sub-procedure of Algorithm 1
to get the left Lanczos components of .
Similarly, in the next step, we fix as known and compute the matrix
then resort to the Lanczos algorithm to construct another Krylov space and get corresponding
right Lanczos components
of matrix . Thus we obtain a group bilinear Lanczos components in one cycle.
It should be noted that, the reorthogonalization technique has been applied in our BLC
algorithm to guarantee the orthogonality of Lanczos components, please see lines 3-e) and 4-e) in
the Algorithm 2 for details.
The alternant optimization procedures are implemented repeatedly to get left and right
components until the iteration step or other convergence criterion is achieved. Finally, the
ultimately updated bilinear Lanczos components are set to matrix and , respectively, which
will be used to get compressed matrices for dimensionality
reduction or feature extraction.
The complete pseudo-code of the iterative procedure is given in Algorithm 2:
- 7 -
中国科技论文在线
Algorithm 2: The bilinear Lancros components algorithm for dimensionality reduction.
Complexity analysis
Obviously, the most expensive steps in BLC algorithm include the computation of the
matrices , and the corresponding Lanczos components.
It takes time for computing and time for
computing . The time used for computing the Lanczos components are and
, respectively. Thus the total time complexity of BLC algorithm is
.
On the other hand, since two eigenvalue decomposition problem of size and are
included in the GLRAM method, it will spend time
complexity to compute the projection matrices, where and correspond to the
complexity of EVD of matrices and , respectively.
- 8 -
中国科技论文在线
As far as the storage memory is concerned, it is easy to verify that the space complexity used
for BLC and GLRAM are since the computation of matrices and can be
sequentially proceeded by reading matrices in an incremental fashion.
Tab. 1 shows the time and space complexities of BLC and GLRAM methods. It is clear that
our BLC approach has much smaller cost in time complexity than that of GLRAM, especially for
large and .
Tab. 1 Time and space complexities of BLC and GLRAM methods
Methods Time complexity Storage request
BLC
GLRAM
2 Parameter selection
In the following section, we will explore an important topic on how much Lanczos
components should be selected in the practical applications with critical computational time
request.
Let be a bilinear transformation from the input space to the low-dimensional space:
where , . Suppose , , then by the transformation ,
we only need to consider the sample in the low-dimensional space , which achieves the
dimensionality reduction task. But with a general bilinear transformation, the classification
performance may be significantly decreased, so how to choose a suitable transformation is critical.
Firstly, we present the definition of bilinear separability.
Definition Let be a training sample set, which belongs to two classes
and . It is called bilinear separability, if there is a decision boundary
, . and ,
where and are constant vectors, is a constant scalar.
The following theorem discusses the invariant bilinear separability for transformations
and . That is, if sample data are bilinear separable in the image space, then the transformed
features are also bilinear separable.
Theorem 1 Let be a training sample set which belongs to two classes
and , and are leading eigenvectors correspond to nonzero eigenvalues of matrices
and , respectively, with rank and . If
the samples are bilinearly separable in the input space, then are bilinearly
separable in the low-dimensional space, either.
Proof Because and are matrices with and orthonormal columns, we have
where and are identities. By expanding , we construct the
-dimensional orthogonal matrix , where . Then we have
which implies . Therefore, it is not
difficult to get
Similarly, by expanding , we construct the -dimensional orthogonal matrix
, where . Then which implies
- 9 -
中国科技论文在线
.
On the other hand, because the samples are bilinearly separable, there exists a decision
boundary , . and , where
and are constant vectors, is a constant scalar.
Since , , and for any , we obtain
Let , , From
and , we have and
. Therefore, is also bilinearly separable in the feature space.
Because multi-class problem can be converted into a set of two-class problems, if the data are
bilinearly separable in multi-class in , the compressed data after the transformations and
are also bilinearly separable in . This theorem shows that, if suitable bilinear
transformations are chosen for dimensionality reduction, they will not lose important classification
information.
Usually, the matrices are full-rank since the facial images are effected by
illuminations, poses, and expressions. For face recognition, if and are bilinear Lanczos
components of matrices , only the first left and right Lanczos components have
principal impact on the classification performance, because the remainders are relatively so small
that can be ignored for dimensionality reduction, . where is the
leading diagonal part of matrix . So we have
Meanwhile, the continuity of decision function guarantees the output sign can be locally
kept. Therefore, using a smaller value for truncated Lanczos components will not generate
too much negative impact on samples' separability.
- 10 -
中国科技论文在线
Fig. 2 Classification rates of four databases with different dimensionality parameters: (a) ORL database; (b)
FERET database; (c) CMU-PIE database; (d) COIL-20 database.
For instance, Fig. 2 presents the correct classification rates on four database, ORL, FERET,
CMU-PIE, and COIL-20. From simple computation, it is easy to know that both matrices
and on each database are full-rank. However, subfigures (a), (b) and
(d) shows that when the dimensionality parameter rising from a small initial value to a larger one
( respectively), the classification rate rises to a peak value, then
when more features are included, the classification rate begin to decrease. Although the result in (c)
shows the performance rising all the while as dimensionality increasing, it is very stable and has a
flat tendency. Thus, these experimental results jointly validate the interesting and meaningful
result in Theorem 1 that a small dimensionality value is approximately sufficient for efficient
feature extraction and data classification.
As a result, this theorem gives a theoretical clue on how to select suitable parameters for
feature extraction and classification. In fact, it can be easily extended to multi-linear cases for
high-order
tensors, by changing the corresponding matrix product into mode product in the tensor space,
but it goes beyond our scope of this paper since we only focus on the 2-D images.
3 Experimental results and analysis
To evaluate the classification performance and training time consuming of bilinear Lanczos
components for 2-D images, we systematically compare it with GLRAM method (The Matlab
code is publicly available on on the ORL
database [28], FERET database [29], CMU-PIE database [30], USPS handwriting digit database
and COIL-20 database. We believe the results are helpful to support our novel viewpoint that BLC
algorithm has competitive classification ability with EVD based dimensionality reduction methods
for face recognition and other image classification problem, but using less computational time.
Database description and preprocessing
- 11 -
中国科技论文在线
Fig. 3 Example images of three databases: (a) one individual with ORL database; (b) two individuals with FERET
database; (c) one individual with CMU-PIE database.
The ORL database contains 400 images of 40 individuals. These images were captured at
different times and have different variations including expression (open or closed eyes, smiling or
non-smiling) and facial details (glasses or no glasses). The images were taken with a tolerance for
tilting and rotation of the face up to . We present example images of one individual in the Fig.
3(a).
The FERET facial image database is a result of the FERET program, which was sponsored
by the US Department of Defense through the DARPA Program [30]. The images are selected
from four different sets, namely Fa, Fb, Fc, and duplicate, which bear with more differences in
lighting, facial expressions, and facial details. It has become a standard database for testing and
evaluating state-of-the-art face recognition algorithms. Some example images are shown in Fig.
3(b).
The CMU PIE (Pose, Illumination, and Expression) database contains in total 41368 images
of 68 subjects with 500+ images for each. The face images were captured by 13 synchronized
cameras and 21 flashes, under varying pose, illumination, and expression [31]. For each subject,
we manually select 43 images from five near frontal poses (C05, C07, C09, C27, C29) under
different illuminations and expressions. Some example images from one subject are presented in
Fig. 3(c).
Fig. 4 Example of handwriting digit 0-4 from USPS database.
USPS is an image database consisting of 9298 handwritten digits of 0 through 9 [31-32]. We
use a subset of USPS. This subset contains 600 images for each digit, for a total of 6000 images.
The image size is . Some images from digit 0 to 4 are shown in Fig. 4.
- 12 -
中国科技论文在线
Fig. 5 Example images of COIL-20 database.
COIL-20 is a database of gray-scale images of 20 objects. The objects were placed on a
motorized turntable against a black background. The turntable was rotated through to vary
the object poses with respect to a fixed camera, as shown in Fig. 5. Images of the objects were
taken at pose intervals of , which corresponds to 72 images per object. For our experiments, we
have resized each of the original 1440 images down to pixels.
The important statistics of these image databases are summarized in Table 2.
Tab. 2 Statistics for image databases
Database Num. of classes Image num. of each class Total num. of images
ORL 40 10 400
FERET 72 6 432
CMU-PIE 68 43 2924
USPS 10 600 6000
COIL-20 20 72 1440
In the experiments, all facial images are aligned at the centers of the eyes and mouth.
Histogram equalization is applied to the facial images for photometric normalization, and the
images are thenconverted to the intensity images that contain values in the range (black) to
(white). After feature extraction, the nearest neighbor(NN) classifier with Euclidean distance is
used for final classification.
It is also worth noting that we use an unified notation throughout the following
figures for easy visualization and comparison.
Face recognition
ORL database
We form the training set by a random subset of six different facial expressions/poses per
subject and use the remaining as a test set. We experiment with the dimensionality of the
reduced space from 6 to 20 with step 2. For each value of , we compute the average error rate
across 30 random realizations of the training set. Fig. 6(a) illustrates the results. Here, BLC and
GLRAM exhibit a similar behavior: Their error rates initially decrease with and then become
stable when more features are extracted. However, notice also that the training time used for the
two methods are shown in Fig. 6(b). It is easy to observing that the time spent on GLRAM
algorithm is much than our BLC approach cost. Especially, when more features extracted by
GLRAM are used for recognition, it needs much time for training, while our BLC spends
relatively stable time for different dimensions.
- 13 -
中国科技论文在线
Fig. 6 Misclassification rate (a) and training time (b) of BLC and GLRAM methods on the ORL database, where
abscissa denotes reduced dimensionality ranging from 6 to 20 in each subfigure.
FERET database
Fig. 7 Misclassification rate (a) and training time (b) of BLC and GLRAM methods on the FERET database, where
abscissa denotes reduced dimensionality ranging from 6 to 20 in each subfigure.
We form the training set by a random subset of four different facial images per subject and
use the remaining two as a test set. We plot the error rate across 30 random realizations of the
training/test set for different values of between 6 and 20 with step 2. The results are illustrated
in Fig. 7(a). Once again, we observe that BLC and GLRAM exhibit similar recognition
performance across all values of . In addition, notice from Fig. Fig. 7(b) that BLC still has a
small time complexity than that of GLRAM. For the GLRAM method, when more features are
used for recognition, the misclassification rate will become smaller. However, as the
dimensionality rising, corresponding training time will cost much, either.
CMU-PIE database
- 14 -
中国科技论文在线
Fig. 8 Misclassification rate (a) and training time (b) of BLC and GLRAM methods on the CMU-PIE database,
where abscissa denotes reduced dimensionality ranging from 6 to 20 in each subfigure.
We form the training set by a random subset of 23 different facial images per subject and use
the remaining ones as a test set. We experiment with the dimensionality of the reduced space
from 6 to 20 with Step 2. Fig. 8(a) illustrates the results. Here, BLC and GLRAM also exhibit a
similar recognition performance. Particularly, when is small, GLRAM can outperform than
BLC method, but when becomes larger, the recognition ability of BLC is competitive even
better than that of GLRAM approach. Notice also that the training time used for GLRAM method
still much than that of BLC, and present a rising tendency as dimensionality increases which can
be easily seen in Fig. 8(b).
USPS digit classification
In this section, we form the training set by a random subset of 400 different samples per class
and use the remaining 200 samples as a test set. To reduce the variation of recognition results, we
implement the procedure 30 times and then report the average misclassification rate and average
training time, respectively.
We experiment with the dimensionality of the reduced space from 4 to 12 with step 2. Fig.
9(a) illustrates the classification results. Here, BLC and GLRAM also exhibit a similar recognition
performance. Specifically, when the dimension , BLC presents 27% error rate, and when
increases to 6, the error rate quickly reduces to 9%. As rises to 8 or even more, our BLC
obtains very similar results with that of GLRAM. On the other hand, we compare the training time
in the Fig. 9(b). It is easy to see that GLRAM method still consumes too much time than that of
our BLC approach.
Fig. 9 Misclassification rate (a) and training time (b) of BLC and GLRAM methods on the USPS handwriting digit
database, where abscissa denotes reduced dimensionality ranging from 4 to 12 in each subfigure.
- 15 -
中国科技论文在线
COIL-20 database
For the COIL-20 image database, we randomly select half images for training and estimating
the misclassification error rate, and use the other half omitted subset for testing.
We experiment with the dimensionality of the reduced space from 2 to 20 with step 2 and
present the classification results in Fig. 10(a). We can see that, when the dimension , BLC
presents less than 40% misclassification rate, and when increases to 4, the error rate quickly
reduces to 2%. As rises to more, our BLC obtains very similar results with that of GLRAM. On
the other hand, we plot the training time in the Fig. 10(b). Obviously, the time used in BLC
method is very stable and hovers at each dimensionality, nevertheless, GLRAM uses at
least when 2 features are extracted.
Fig. 10 Misclassification rate (a) and training time (b) of BLC and GLRAM methods on the COIL-20 database,
where abscissa denotes reduced dimensionality ranging from 2 to 20 in each subfigure.
Comparison with other state-of-the-art methods
To show the real applicability of our BLC method for dimensionality reduction, this section
will present the comparison results with other state-of-the-art methods, such as PCA [6],
MMC [3], and SPP [33], where PCA and MMC are two-dimensional methods,
and bidirectional projections are computed from the 2D training samples. Specifically, two scatter
matrices called column covariance matrix and row covariance matrix are constructed in the
PCA method, then it followed by the eigenvalue decomposition to obtain the projections.
The extracted features based on MMC is robust, stable and efficient. SPP aims to preserve
the sparse constructive relationship of the data, which is achieved by minimizing a
-regularization related objective function, and it implies the latest approach for dimensionality
reduction.
It is worth noting that SPP is based on 1D vectors so that the -minimization procedure is
very time-consuming. Meanwhile, because how many features should be preserved is also difficult
for SPP, we only summarize the best average recognition accuracies and corresponding training
time on the CMU-PIE and COIL-20 databases.
- 16 -
中国科技论文在线
Tab. 3 Experimental results of the state-of-the-art methods on CMU-PIE database
Methods GLRAM PCA MMC BLC SPP
15 samples
accuracy(%) ± ± ± ± ±
dimensions 20*20 18*18 20*20 20*20 235
Training time(s)
23 samples
accuracy(%) ± ± ± ± ±
dimensions 20*20 12*12 16*16 20*20 210
Training time(s)
Tab. 4 Experimental results of the state-of-the-art methods on COIL-20 database
Methods GLRAM PCA MMC BLC SPP
30 samples
accuracy(%) ± ± ± ± ±
dimensions 8*8 10*10 12*12 12*12 90
Training time(s)
36 samples
accuracy(%) ± ± ± ± ±
dimensions 8*8 8*8 16*16 14*14 80
Training time(s)
Tab. 3 reports the recognition results on CMU-PIE database. As we can see, when 15
samples in each class are randomly selected for training, MMC obtains the best accuracy,
and it is closely followed by SPP, GLRAM, BLC, and PCA methods. When the training
size is increased to 23, all the methods present very good accuracies beyond 99%, except that
GLRAM achieves %. To our pleasantly surprise, BLC approach costs the least training time
to computing projections, for 15 samples and for 23 samples, while SPP costs as
much as and respectively.
The results on COIL-20 database are shown in Tab. 4. It is obvious that all the 2D methods
obtain similar performances, but SPP presents the lowest accuracies. As we have mentioned above,
SPP still costs too much training time for computing the projections since there is a
-minimization procedure included. Due to the fast approximation of the BLC algorithm, it costs
less time than other 2D methods, only use for 30 samples and for 36 samples,
respectively.
4 Conclusions and Future Work
Fast computation of low-rank approximations for matrices is a common problem in pattern
recognition and machine learning community. We consider a novel approach that uses bilinear
Lanczos components to approximate generalized low-rank approximation of matrices in this paper.
Specially, we derive a sequentially iterative procedure via Lanczos algorithm for the optimization
problem in the Krylov space, which thus presents an efficient approach for the objective criterion.
Our Lanczos based approach achieves the goal by using a small number of bilinear Lanczos
components, instead of explicitly computing singular values/vectors of the matrix as EVD based
method does. The main advantage of BLC is its low cost while comes without sacrificing accuracy.
The proposed technique can be applied as a replacement to the bidirectional truncated EVD
technique whenever the problem can be formulated as a low-rank approximation of matrices such
as dimensionality reduction and feature extraction. Meanwhile, a theoretical clue about how much
components should be selected without losing classification information is also discussed in this
paper.
Extensive experiments on several image databases are implemented to evaluate the efficiency
- 17 -
中国科技论文在线
and effectiveness of the proposed algorithm. Results show that our new approach has a
competitive classification performance with the state-of-the-art methods while it has a much lower
training cost. How to extend our new approach to higher order tensor decomposition for image
classification and video processing is our future works.
References
[1] J. Yang, . Yang, From image vector to matrix: as traight forward image projection technique—IMPCA vs.
PCA[J], Pattern Recognition 35(9) (2002) 1997–1999.
[2] J. Yang, D. Zhang, A. Frangi, J. Yang, Two-dimensional PCA: a new approach to appearance-based face
representation and recognition [J], IEEE Transactions on Pattern Analysis and Machine Intelligence 26(1)
(2004) 131–137.
[3] . Yang, . Dai, Two-dimensional maximum margin feature extraction for face recognition [J], IEEE
Transactions on System, Man and Cybernetics, Part B 39(4) (2009) 1002–1012.
[4] . Ren, . Dai, Incremental learning of bidirectional principal components for face recognition [J],
Pattern Recognition 43 (2010) 318–330.
[5] J. Ye, Generalized low rank approximations of matrices, [J] Machine Learning 61 (2005) 167–191.
[6] D. Zhang, .Zhou, PCA: 2-directional 2-dimensional PCA for efficient face representation and
recognition [J], Neurocomputing 69(1–3) (2005) 224–231.
[7] W. M. Zuo, D. Zhang, J. Yang, . Wang, BDPCA Plus LDA: a novel fast feature extraction technique for
face recognition [J], IEEE Transactions on System, Man and Cybernetics, Part-B 36(4) (2006) 946–953.
[8] . Lathauwer, . Moor, J. Vandewalle, A multi-linear singular value decomposition [J], SIAM Journal on
Matrix Analysis and Applications 21(4) (2000) 1253–1278.
[9] L. Omberg, . Golub, O. Alter, A tensor higher-order singular value decomposition for integrative analysis
of DNA micro-array data from different studies [J], Proceedings of the National Academy of Sciences of the
United States of America 104(47) (2007)18371–18376.
[10] E. Acar, , Unsupervised multi-way data analysis: a literature survey [J], IEEE Transactions on
Knowledge and Data Engineering 21(1) (2009) 6–20.
[11] Z. Liang, P. Shi, Analytical algorithm for generalized low-rank approximations of matrices [J], Pattern
Recognition 38(11) (2005)2213–2216.
[12] Z. Liang, D. Zhang, P. Shi, The theoretical analysis of GLRAM and its applications [J], Pattern Recognition
40(3) (2007) 1032–1041.
[13] I. Kohei, U. Kiichi, Equivalence of non-iterative algorithms for simultaneous low rank approximations of
matrices [C], in Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern
Recognition, vol. 1,–159.
[14] L. Wang, X. Wang, . Feng, On image matrix based feature extraction algorithms [J], IEEE Transactions on
System, Man and Cybernetics, Part-B 36(1) (2006) 194–197.
[15] . Abdallah, . Ben, P. Bhattacharya, MPEG video watermarking using tensor singular value
decomposition [C] ,in 4th International Conference on Image Analysis and Recognition, vol. 4633, Montreal,
Canada, 2007, pp. 772–783.
[16] . Basser, S. Pajevic, Spectral decomposition of a 4th-order covariance tensor: applications to diffusion
tensor MRI [J], Signal Processing 87 (2) (2007) 220–236.
[17] . Yan, D. Xu, Q. Yang, et al., Multi-linear discriminant analysis for face recognition [J], IEEE
Transactions on Image Processing 16 (1) (2007) 212–220.
[18] H. Wang, S. Chen, Z. Hu, W. Zheng, Locality-preserved maximum information projection [J], IEEE
Transactions on Neural Networks 19 (4) (2008) 571–585.
[19] J. Chen, Y. Saad, Lanczos vectors versus singular vectors for effective dimension reduction [J], IEEE
Transactions on Knowledge and Data Engineering 21 (8) (2009) 1091–1103.
[20] H. Kiers, Towards a standardized notation and terminology in multi-way analysis [J], Journal of
Chemometrics 14 (3) (2000) 105–122.
[21] I. Mortet, Rational Lanczos approximations to the matrix square root and related functions [J], Numerical
Linear Algebra with Applications 16 (6) (2009) 431–445.
[22] A. Poghosyan, Asymptotic behavior of the Krylov–Lanczos interpolation [J], Analysis and Applications 7 (2)
(2009) 199–211.
[23] . Parlett, The Symmetric Eigenvalue Problem [M], Society for Industrial and Applied Mathematics,
Prentice-Hall, 1998.
[24] . Simon, Analysis of the symmetric Lanczos algorithm with reorthogona- lization methods [J], Linear
Algebra and its Applications 61 (1984) 101–131.
[25] . Martin, Lanczos-type solvers for nonsymmetric linear systems of equations [J], Acta Numerica1 997(6)
(2008) 271–397.
[26] K. Browne, S. Qiao, . Wei, A Lanczos bidiagonalization algorithm for Hankel matrices [J], Linear
Algebra and its Applications 430(5–6) (2009) 1531–1543.
[27] Y. Wang, L. Lu, Preconditioned Lanczos method for generalized Toeplitz eigenvalue problems [J], Journal of
Computational and Applied Mathematics 226 (1) (2009) 66–76.
- 18 -
中国科技论文在线
[28] Cambridge and &T (Olivetti) Research Laboratories, The ORL Face Database [OL],Available:
.
[29] . Philips, H. Moon, . Rizvi, . Rauss, The FERET evaluation methodology for face recognition
algorithms [J], IEEE Transactions on Pattern Analysis and Machine Intelligence22(10) (2000) 1090–1104.
[30] T. Sim, S. Baker, , The CMU pose, illumination, and expression database [J], IEEE Transactions on
Pattern Analysis and Machine Intelligence25 (12) (2003) 1615–1618.
[31] . Liu, K. Nakashima, H. Sako, H. Fujisawa, Handwritten digit recognition: benchmarking of
state-of-the-art techniques [J], Pattern Recognition 36(2003) 2271–2285.
[32] . Liu, K. Nakashima, H. Sako, H. Fujisawa, Handwritten digit recognition: investigation of normalization
and feature extraction techniques [J], Pattern Recognition 37(2004) 265–279.
[33] . Qiao, . Chen, . Tan, Sparsity preserving projections with applications to face recognition [J],
Pattern Recognition 43(2010) 331–341.
基于双线性Lancros成分的快速降维与特征
提取
任传贤，戴道清
（中山大学数学与计算科学学院，广州 510275）
摘要：矩阵的广义低阶逼近(GLRAM)方法，已经在模式识别和机器学习领域取得了广泛的应
用。该方法通过迭代优化进一步寻求图像在行与列空间中的最佳投影方向。我们提出使用双
向 Lanczos 成分逼近由特征值分解得到的投影向量，每一个样本点都以二维矩阵的形式存
在，而不需要将其转化为一维向量形式，从而避免复杂度较高的特征值分解。该方法逐步减
小基于 Frobenius 范数优化问题的重构误差，并且导致逼近性能在连续的迭代过程中不断提
高。另外，关于参数选择，我们也将给出理论线索以寻求合适的投影个数。在人脸识别与图
像分类问题上的实验结果表明，双向 Lanczos 成分方法仅仅使用较少的 Lanczos 向量来实现
降维和特征提取，因而是十分高效的，不仅得到了高于其他主要方法的识别率，而且在计算
时间上有了明显的改进。
关键词：模式识别；双线性 Lancros 分析；降维；特征提取；快速算法
中图分类号：
