Chapter 3 Getting Only a Few Eigenvalues
Sometimes we only want a few of the possible eigenvectors and we
want them rank in order of the size of the magnitudes of the
eigenvalues.
3.1 Facial Recognition Background:
For example, in some facial recognition algorithms,
we don't want to compute all the
eigenvalues and eigenvectors of what is called the covariance matrix.
We will be discussing this in more detail in Chapter 10.
In general, these are the basic steps:
- Collect Images: we have
taken 52 pictures of the people in the class. There
are 4 pictures per person. We got these on a Kodak PhotoCD.
These pictures are then put on a computer as files. Each of these
files is a big (say 800 by 600 ) matrix of information.
Each entry in this matrix can be represented by a number.
So there are 480,000 numbers for each image! Call these
matrix images Ai
- Convert each matrix into a long vector. Call these
vectors ai.
- Find the average matrix image (call it S ) and convert it
to a vector s.
- Find the difference vectors di = ai - s.
- The theory then says to find the covariance
matrix
where A is the 480,00 by 52 matrix
| A |
= |
[d1 | d2 | ··· | d52] |
This makes the matrix A AT 480,000 by 480,000 -- quite big!
- We will find that theory tells us that the
eigenvectors
and eigenvalues
of the covariance matrix are important for image recognition. But finding
these things for this huge matrix is way too hard! It turns out the
eigenvalues and eigenvectors of the smaller 52 by 52 matrix
AT A are just what we need. There are at most 52 of these
and theory says the eigenvalues are nonnegative and the eigenvectors
are 90 degrees apart. If we call these eigenvectors
then the vectors
turn out to be eigenvectors for the covariance matrix.
These are called eigenfaces
.
- Project each original difference image onto the
subspace determined by a small number of these eigenfaces.
For example, difference image d3 might look like
| d3 |
= |
.22*Av1 + .34*Av2 -.67*Av3 + 46.7*Av4 + Z |
where the first four pieces is the portion of d3 that lies
in the plane determined by the first four eigenfaces and Z
is the part of d3 that lies out of this plane.
So we could associate d3 with a small vector called
a feature vector:
- Pick a small subset of the 52 eigenfaces
we have found, say 10, and find the feature vector for each.
Take the four feature vectors for each person and average them.
This average feature vector is called the class vector for that
face.
- Now take a new picture of a person in the original group
and convert it to a difference vector like usual. Then
find its feature vector. Find the distance from this feature vector
to all the class vectors. If it is sufficiently
close to a class vector, we can say it is the person that class
represents.
Now this is just a start at this big subject of facial
recognition. We can also use artificial neural technology
and other things. This technique is statistically based
and you really need some tools like Matlab to pull it off!
3.2 Matlab Away!
Let's start by looking up the eigs command.
3.2.1 The eigs Command:
>> help eigs
EIGS Find a few eigenvalues and eigenvectors.
EIGS solves the eigenvalue problem A*v = lambda*v or the generalized
eigenvalue problem A*v = lambda*B*v. Only a few selected eigenvalues,
or eigenvalues and eigenvectors, are computed.
[V,D,FLAG] = EIGS(A)
[V,D,FLAG] = EIGS('Afun',N)
The first input argument is either a square matrix (which can be
full or sparse, symmetric or nonsymmetric, real or complex), or a
string containing the name of an M-file which applies a linear
operator to the columns of a given matrix. In the latter case,
the second input argument must be N, the order of the problem.
For example, EIGS('fft',...) is much faster than EIGS(F,...)
where F is the explicit FFT matrix.
The remaining input arguments are optional and can be given in
practically any order:
[V,D,FLAG] = EIGS(A,B,K,SIGMA,OPTIONS)
[V,D,FLAG] = EIGS('Afun',N,B,K,SIGMA,OPTIONS)
where
B A symmetric positive definite matrix the same size as A.
K An integer, the number of eigenvalues desired.
SIGMA A scalar shift or a two letter string.
OPTIONS A structure containing additional parameters.
With one output argument, D is a vector containing K eigenvalues.
With two output arguments, D is a K-by-K diagonal matrix and V is
a matrix with K columns so that A*V = V*D or A*V = B*V*D.
With three output arguments, FLAG indicates whether or not the
eigenvalues converged to the desired tolerance. FLAG = 0 indicated
convergence, FLAG = 1 not. FLAG = 2 indicates that EIGS stagnated
i.e. two consecutive iterates were the same.
If B is not specified, B = eye(size(A)) is used. Note that if B is
specified, then its Cholesky factorization is computed.
If K is not specified, K = MIN(N,6) eigenvalues are computed.
If SIGMA is not specified, the K-th eigenvalues largest in magnitude
are computed. If SIGMA is zero, the K-th eigenvalues smallest in
magnitude are computed. If SIGMA is a real or complex scalar, the
"shift", the K-th eigenvalues nearest SIGMA are computed using
shift-invert. Note that this requires computation of the LU
factorization of A-SIGMA*B. If SIGMA is one of the following strings,
it specifies the desired eigenvalues.
SIGMA Specified eigenvalues
'LM' Largest Magnitude (the default)
'SM' Smallest Magnitude (same as sigma = 0)
'LR' Largest Real part
'SR' Smallest Real part
'BE' Both Ends. Computes k/2 eigenvalues
from each end of the spectrum (one more
from the high end if k is odd.)
The OPTIONS structure specifies certain parameters in the algorithm.
Field name Parameter Default
OPTIONS.tol Convergence tolerance: 1e-10 (symmetric)
norm(A*V-V*D,1) <= tol * norm(A,1) 1e-6 (nonsymm.)
OPTIONS.stagtol Stagnation tolerance: quit when 1e-6
consecutive iterates are the same.
OPTIONS.p Dimension of the Arnoldi basis. 2*k
OPTIONS.maxit Maximum number of iterations. 300
OPTIONS.disp Number of eigenvalues displayed 20
at each iteration. Set to 0 for
no intermediate output.
OPTIONS.issym Positive if Afun is symmetric. 0
OPTIONS.cheb Positive if A is a string, 0
sigma is 'LR','SR', or a shift, and
polynomial acceleration should be
applied.
OPTIONS.v0 Starting vector for the Arnoldi rand(n,1)-.5
factorization
See also EIG, SVDS.
3.2.2 A Simple Example:
>> A = [1 2 3 4 5 6;
2 4 5 6 7 8;
3 5 -1 8 9 1;
4 6 8 1 2 3;
5 7 9 2 3 10;
6 8 1 3 10 18]
A =
1 2 3 4 5 6
2 4 5 6 7 8
3 5 -1 8 9 1
4 6 8 1 2 3
5 7 9 2 3 10
6 8 1 3 10 18
>> [V,D,FLAG] = eigs(A,3)
iter =
1
eigs =
33.7304
-11.9465
9.7191
stopcrit =
5.1891e-16
==========================
iter =
2
eigs =
33.7304
-11.9465
9.7191
stopcrit =
5.3580e-16
==========================
V =
-0.2692 0.1013 0.0695
-0.3976 0.1012 0.2181
-0.2745 0.6822 0.5240
-0.2601 -0.4528 0.4673
-0.4447 -0.5343 0.1377
-0.6547 0.1537 -0.6600
D =
33.7304 0 0
0 -11.9465 0
0 0 9.7191
FLAG =
0
>>
3.2.3 A Covariance Example:
Let's enter a 20 × 3 matrix:
>> A = [.1 .2 .3;
-.1 .3 .45;
.5 2 1.4;
.8 .9 1.1;
1.3 -.7 2.3;
12.3 23.4 0.5;
-.1 -.3 -.5;
.3 .7 1.8;
1.2 34.7 23.7;
2.4 -5.6 7.8;
.7 9.1 20.4;
2.6 3.5 4.6;
1.3 29.3 -11.4;
.03 .56 9.1;
14.5 -23.4 99.1;
0.9 8.5 -4.5;
-11.3 89.3 45.7;
7.2 3.4 5.96;
12.3 45.2 -67.4;
-5.6 0.4 0.7]
A =
0.1000 0.2000 0.3000
-0.1000 0.3000 0.4500
0.5000 2.0000 1.4000
0.8000 0.9000 1.1000
1.3000 -0.7000 2.3000
12.3000 23.4000 0.5000
-0.1000 -0.3000 -0.5000
0.3000 0.7000 1.8000
1.2000 34.7000 23.7000
2.4000 -5.6000 7.8000
0.7000 9.1000 20.4000
2.6000 3.5000 4.6000
1.3000 29.3000 -11.4000
0.0300 0.5600 9.1000
14.5000 -23.4000 99.1000
0.9000 8.5000 -4.5000
-11.3000 89.3000 45.7000
7.2000 3.4000 5.9600
12.3000 45.2000 -67.4000
-5.6000 0.4000 0.7000
Now compute its transpose:
>> B = transpose(A)
B =
Columns 1 through 7
0.1000 -0.1000 0.5000 0.8000 1.3000 12.3000 -0.1000
0.2000 0.3000 2.0000 0.9000 -0.7000 23.4000 -0.3000
0.3000 0.4500 1.4000 1.1000 2.3000 0.5000 -0.5000
Columns 8 through 14
0.3000 1.2000 2.4000 0.7000 2.6000 1.3000 0.0300
0.7000 34.7000 -5.6000 9.1000 3.5000 29.3000 0.5600
1.8000 23.7000 7.8000 20.4000 4.6000 -11.4000 9.1000
Columns 15 through 20
14.5000 0.9000 -11.3000 7.2000 12.3000 -5.6000
-23.4000 8.5000 89.3000 3.4000 45.2000 0.4000
99.1000 -4.5000 45.7000 5.9600 -67.4000 0.7000
Next find the AAT and AT A:
>> C = B*A This is A^T A which is 3 x 3
C =
1.0e+04 *
0.0743 -0.0392 0.0197
-0.0392 1.3392 -0.0635
0.0197 -0.0635 1.7793
>> D = A*B This is A A^T which is 20 x 20
D =
1.0e+04 *
Columns 1 through 7
0.0000 0.0000 0.0001 0.0001 0.0001 0.0006 -0.0000
0.0000 0.0000 0.0001 0.0001 0.0001 0.0006 -0.0000
0.0001 0.0001 0.0006 0.0004 0.0002 0.0054 -0.0001
0.0001 0.0001 0.0004 0.0003 0.0003 0.0031 -0.0001
0.0001 0.0001 0.0002 0.0003 0.0007 0.0001 -0.0001
0.0006 0.0006 0.0054 0.0031 0.0001 0.0699 -0.0008
-0.0000 -0.0000 -0.0001 -0.0001 -0.0001 -0.0008 0.0000
0.0001 0.0001 0.0004 0.0003 0.0004 0.0021 -0.0001
0.0014 0.0021 0.0103 0.0058 0.0032 0.0839 -0.0022
0.0001 0.0002 0.0001 0.0005 0.0025 -0.0098 -0.0002
0.0008 0.0012 0.0047 0.0031 0.0041 0.0232 -0.0013
0.0002 0.0003 0.0015 0.0010 0.0012 0.0116 -0.0004
0.0003 0.0004 0.0043 0.0015 -0.0045 0.0696 -0.0003
0.0003 0.0004 0.0014 0.0011 0.0021 0.0018 -0.0005
0.0026 0.0036 0.0099 0.0100 0.0263 -0.0320 -0.0044
0.0000 0.0000 0.0011 0.0003 -0.0015 0.0208 -0.0000
0.0030 0.0048 0.0237 0.0122 0.0028 0.1973 -0.0049
0.0003 0.0003 0.0019 0.0015 0.0021 0.0171 -0.0005
-0.0010 -0.0018 0.0002 -0.0024 -0.0171 0.1175 0.0019
-0.0000 0.0001 -0.0001 -0.0003 -0.0006 -0.0059 0.0000
Columns 8 through 14
0.0001 0.0014 0.0001 0.0008 0.0002 0.0003 0.0003
0.0001 0.0021 0.0002 0.0012 0.0003 0.0004 0.0004
0.0004 0.0103 0.0001 0.0047 0.0015 0.0043 0.0014
0.0003 0.0058 0.0005 0.0031 0.0010 0.0015 0.0011
0.0004 0.0032 0.0025 0.0041 0.0012 -0.0045 0.0021
0.0021 0.0839 -0.0098 0.0232 0.0116 0.0696 0.0018
-0.0001 -0.0022 -0.0002 -0.0013 -0.0004 -0.0003 -0.0005
0.0004 0.0067 0.0011 0.0043 0.0012 0.0000 0.0017
0.0067 0.1767 -0.0007 0.0800 0.0234 0.0748 0.0235
0.0011 -0.0007 0.0098 0.0110 0.0023 -0.0250 0.0068
0.0043 0.0800 0.0110 0.0499 0.0128 0.0035 0.0191
0.0012 0.0234 0.0023 0.0128 0.0040 0.0053 0.0044
0.0000 0.0748 -0.0250 0.0035 0.0053 0.0990 -0.0087
0.0017 0.0235 0.0068 0.0191 0.0044 -0.0087 0.0083
0.0166 0.1554 0.0939 0.1819 0.0412 -0.1797 0.0889
-0.0002 0.0189 -0.0081 -0.0014 0.0011 0.0302 -0.0036
0.0141 0.4168 -0.0171 0.1737 0.0493 0.2081 0.0466
0.0015 0.0268 0.0045 0.0158 0.0058 0.0041 0.0056
-0.0086 -0.0014 -0.0749 -0.0955 -0.0120 0.2109 -0.0588
-0.0000 0.0024 -0.0010 0.0014 -0.0010 -0.0004 0.0006
Columns 15 through 20
0.0026 0.0000 0.0030 0.0003 -0.0010 -0.0000
0.0036 0.0000 0.0048 0.0003 -0.0018 0.0001
0.0099 0.0011 0.0237 0.0019 0.0002 -0.0001
0.0100 0.0003 0.0122 0.0015 -0.0024 -0.0003
0.0263 -0.0015 0.0028 0.0021 -0.0171 -0.0006
-0.0320 0.0208 0.1973 0.0171 0.1175 -0.0059
-0.0044 -0.0000 -0.0049 -0.0005 0.0019 0.0000
0.0166 -0.0002 0.0141 0.0015 -0.0086 -0.0000
0.1554 0.0189 0.4168 0.0268 -0.0014 0.0024
0.0939 -0.0081 -0.0171 0.0045 -0.0749 -0.0010
0.1819 -0.0014 0.1737 0.0158 -0.0955 0.0014
0.0412 0.0011 0.0493 0.0058 -0.0120 -0.0010
-0.1797 0.0302 0.2081 0.0041 0.2109 -0.0004
0.0889 -0.0036 0.0466 0.0056 -0.0588 0.0006
1.0579 -0.0632 0.2275 0.0615 -0.7559 -0.0021
-0.0632 0.0093 0.0543 0.0009 0.0699 -0.0005
0.2275 0.0543 1.0191 0.0495 0.0817 0.0131
0.0615 0.0009 0.0495 0.0099 -0.0159 -0.0035
-0.7559 0.0699 0.0817 -0.0159 0.6737 -0.0098
-0.0021 -0.0005 0.0131 -0.0035 -0.0098 0.0032
Now divide by the number of samples:
>> E = C/3
E =
1.0e+03 *
0.2478 -0.1306 0.0655
-0.1306 4.4640 -0.2117
0.0655 -0.2117 5.9311
>> F = D/3
F =
1.0e+03 *
Columns 1 through 7
0.0000 0.0001 0.0003 0.0002 0.0002 0.0020 -0.0001
0.0001 0.0001 0.0004 0.0002 0.0002 0.0020 -0.0001
0.0003 0.0004 0.0021 0.0012 0.0008 0.0179 -0.0004
0.0002 0.0002 0.0012 0.0009 0.0010 0.0105 -0.0003
0.0002 0.0002 0.0008 0.0010 0.0025 0.0003 -0.0004
0.0020 0.0020 0.0179 0.0105 0.0003 0.2330 -0.0028
-0.0001 -0.0001 -0.0004 -0.0003 -0.0004 -0.0028 0.0001
0.0002 0.0003 0.0014 0.0010 0.0013 0.0070 -0.0004
0.0047 0.0070 0.0344 0.0194 0.0106 0.2795 -0.0075
0.0005 0.0005 0.0003 0.0018 0.0083 -0.0325 -0.0008
0.0027 0.0039 0.0157 0.0104 0.0138 0.0772 -0.0043
0.0008 0.0010 0.0049 0.0034 0.0038 0.0387 -0.0012
0.0009 0.0012 0.0144 0.0050 -0.0150 0.2320 -0.0011
0.0009 0.0014 0.0046 0.0035 0.0069 0.0060 -0.0016
0.0088 0.0120 0.0331 0.0332 0.0877 -0.1066 -0.0147
0.0001 0.0001 0.0037 0.0011 -0.0050 0.0692 -0.0001
0.0101 0.0162 0.0790 0.0405 0.0093 0.6578 -0.0162
0.0011 0.0010 0.0062 0.0051 0.0069 0.0570 -0.0016
-0.0033 -0.0060 0.0007 -0.0079 -0.0569 0.3918 0.0063
-0.0001 0.0003 -0.0003 -0.0011 -0.0020 -0.0197 0.0000
Columns 8 through 14
0.0002 0.0047 0.0005 0.0027 0.0008 0.0009 0.0009
0.0003 0.0070 0.0005 0.0039 0.0010 0.0012 0.0014
0.0014 0.0344 0.0003 0.0157 0.0049 0.0144 0.0046
0.0010 0.0194 0.0018 0.0104 0.0034 0.0050 0.0035
0.0013 0.0106 0.0083 0.0138 0.0038 -0.0150 0.0069
0.0070 0.2795 -0.0325 0.0772 0.0387 0.2320 0.0060
-0.0004 -0.0075 -0.0008 -0.0043 -0.0012 -0.0011 -0.0016
0.0013 0.0224 0.0036 0.0144 0.0038 0.0001 0.0056
0.0224 0.5891 -0.0022 0.2667 0.0779 0.2494 0.0784
0.0036 -0.0022 0.0327 0.0366 0.0075 -0.0833 0.0226
0.0144 0.2667 0.0366 0.1665 0.0425 0.0117 0.0636
0.0038 0.0779 0.0075 0.0425 0.0134 0.0178 0.0146
0.0001 0.2494 -0.0833 0.0117 0.0178 0.3300 -0.0291
0.0056 0.0784 0.0226 0.0636 0.0146 -0.0291 0.0277
0.0554 0.5180 0.3129 0.6063 0.1372 -0.5988 0.2964
-0.0006 0.0631 -0.0268 -0.0046 0.0038 0.1005 -0.0121
0.0471 1.3894 -0.0569 0.5790 0.1645 0.6936 0.1552
0.0051 0.0893 0.0149 0.0525 0.0193 0.0137 0.0188
-0.0287 -0.0047 -0.2498 -0.3183 -0.0400 0.7029 -0.1959
-0.0000 0.0079 -0.0034 0.0047 -0.0033 -0.0012 0.0021
Columns 15 through 20
0.0088 0.0001 0.0101 0.0011 -0.0033 -0.0001
0.0120 0.0001 0.0162 0.0010 -0.0060 0.0003
0.0331 0.0037 0.0790 0.0062 0.0007 -0.0003
0.0332 0.0011 0.0405 0.0051 -0.0079 -0.0011
0.0877 -0.0050 0.0093 0.0069 -0.0569 -0.0020
-0.1066 0.0692 0.6578 0.0570 0.3918 -0.0197
-0.0147 -0.0001 -0.0162 -0.0016 0.0063 0.0000
0.0554 -0.0006 0.0471 0.0051 -0.0287 -0.0000
0.5180 0.0631 1.3894 0.0893 -0.0047 0.0079
0.3129 -0.0268 -0.0569 0.0149 -0.2498 -0.0034
0.6063 -0.0046 0.5790 0.0525 -0.3183 0.0047
0.1372 0.0038 0.1645 0.0193 -0.0400 -0.0033
-0.5988 0.1005 0.6936 0.0137 0.7029 -0.0012
0.2964 -0.0121 0.1552 0.0188 -0.1959 0.0021
3.5262 -0.2106 0.7585 0.2052 -2.5196 -0.0071
-0.2106 0.0311 0.1811 0.0029 0.2329 -0.0016
0.7585 0.1811 3.3969 0.1649 0.2724 0.0437
0.2052 0.0029 0.1649 0.0330 -0.0532 -0.0116
-2.5196 0.2329 0.2724 -0.0532 2.2457 -0.0327
-0.0071 -0.0016 0.0437 -0.0116 -0.0327 0.0107
Now let's find eigenvectors: first the smaller matrix:
>> [V,D,FLAG] = eigs(E,2)
iter =
1
eigs =
1.0e+03 *
5.9623
4.4375
stopcrit =
2.7926e-16
==========================
iter =
2
eigs =
1.0e+03 *
5.9623
4.4375
stopcrit =
3.4792e-16
==========================
V =
-0.0146 0.0286
0.1411 -0.9895
-0.9899 -0.1415
D =
1.0e+03 *
5.9623 0
0 4.4375
FLAG =
0
Next the larger one, although for our purposes we will never actually
do this.
>> [V2,D2,FLAG2] = eigs(F,6)
iter =
1
eigs =
1.0e+03 *
5.9623
4.4375
0.2431
0.0000
-0.0000
0
stopcrit =
6.6470e-16
==========================
iter =
2
eigs =
1.0e+03 *
5.9623
4.4375
0.2431
0
0
0
stopcrit =
8.9275e-16
==========================
V2 =
-0.0020 -0.0021 -0.0038 -0.2699 -0.8044 0.5091
-0.0030 -0.0031 0.0035 -0.5848 0.0999 -0.2766
-0.0083 -0.0187 -0.0202 0.2561 -0.1012 -0.0770
-0.0073 -0.0089 -0.0302 0.0652 -0.0382 -0.2038
-0.0179 0.0035 -0.0464 -0.0186 -0.0619 0.0182
0.0197 -0.1982 -0.4814 0.0083 -0.0073 -0.0232
0.0034 0.0032 0.0038 0.5134 0.2365 0.5436
-0.0126 -0.0081 -0.0112 -0.4292 0.4950 0.5464
-0.1389 -0.3264 -0.0744 -0.0059 0.0088 0.0073
-0.0639 0.0391 -0.0795 -0.0404 0.0371 0.0362
-0.1415 -0.1029 -0.0283 0.0638 -0.0344 -0.0400
-0.0306 -0.0350 -0.0984 0.1559 -0.0673 -0.0501
0.1152 -0.2370 -0.0855 -0.0492 0.0337 0.0436
-0.0668 -0.0160 0.0018 -0.0801 0.0358 0.0389
-0.7598 0.0827 -0.4722 -0.0094 0.0055 0.0084
0.0422 -0.0672 -0.0446 0.0351 -0.0426 -0.0558
-0.2428 -0.8247 0.3352 -0.0042 0.0030 0.0035
-0.0413 -0.0347 -0.2680 0.0754 -0.0528 -0.0477
0.5452 -0.3019 -0.5320 -0.0047 0.0024 0.0089
-0.0041 -0.0057 0.2071 0.1458 -0.1100 -0.0860
D2 =
1.0e+03 *
5.9623 0 0 0 0 0
0 4.4375 0 0 0 0
0 0 0.2431 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
FLAG2 =
0
>>