Abstract

A simple method for updating the eigenvectors and eigenvalues of a covariance matrix when a new input sample is added is presented. This proposed method will be a solution for both rank-one modification problems of a symmetric matrix and adaptive principal component analysis.

© 2006 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. G. H. Golub, SIAM Rev. 15, 318 (1973).
    [Crossref]
  2. J. R. Bunch, C. P. Nielsen, and D. C. Sorensen, Numer. Math. 31, 31 (1978).
    [Crossref]
  3. W. N. Gansterer, R. C. Ward, and R. P. Muller, ACM Trans. Math. Softw. 28, 45 (2002).
    [Crossref]
  4. M. Gu and S. C. Eisenstat, 'A stable and fast algorithm for updating the singular value decomposition,' Tech. Rep. YALEU/DCS/RR-966 (Yale University, 1994).
  5. P. M. Hall, A. D. Marshall, and R. R. Martin, IEEE Trans. Pattern Anal. Mach. Intell. 22, 1042 (2000).
    [Crossref]
  6. X. Liu and T. Chen, in Proceedings of the International Conference on Acoustics Speech and Signal Processing (IEEE, 2002), pp. 3389-3392.
  7. D. Erdogmus, Y. N. Rao, H. Peddaneni, A. Hegde, and J. C. Principe, J. Appl. Signal Processing 13, 2034 (2004).
    [Crossref]
  8. Y. Li, Pattern Recognition 37, 1509 (2004).
    [Crossref]
  9. M. Turk and A. Pentland, J. Cogn. Neurosci. 3, 71 (1991).
    [Crossref]
  10. W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, 2002).

2004 (2)

D. Erdogmus, Y. N. Rao, H. Peddaneni, A. Hegde, and J. C. Principe, J. Appl. Signal Processing 13, 2034 (2004).
[Crossref]

Y. Li, Pattern Recognition 37, 1509 (2004).
[Crossref]

2002 (1)

W. N. Gansterer, R. C. Ward, and R. P. Muller, ACM Trans. Math. Softw. 28, 45 (2002).
[Crossref]

2000 (1)

P. M. Hall, A. D. Marshall, and R. R. Martin, IEEE Trans. Pattern Anal. Mach. Intell. 22, 1042 (2000).
[Crossref]

1991 (1)

M. Turk and A. Pentland, J. Cogn. Neurosci. 3, 71 (1991).
[Crossref]

1978 (1)

J. R. Bunch, C. P. Nielsen, and D. C. Sorensen, Numer. Math. 31, 31 (1978).
[Crossref]

1973 (1)

G. H. Golub, SIAM Rev. 15, 318 (1973).
[Crossref]

Bunch, J. R.

J. R. Bunch, C. P. Nielsen, and D. C. Sorensen, Numer. Math. 31, 31 (1978).
[Crossref]

Chen, T.

X. Liu and T. Chen, in Proceedings of the International Conference on Acoustics Speech and Signal Processing (IEEE, 2002), pp. 3389-3392.

Eisenstat, S. C.

M. Gu and S. C. Eisenstat, 'A stable and fast algorithm for updating the singular value decomposition,' Tech. Rep. YALEU/DCS/RR-966 (Yale University, 1994).

Erdogmus, D.

D. Erdogmus, Y. N. Rao, H. Peddaneni, A. Hegde, and J. C. Principe, J. Appl. Signal Processing 13, 2034 (2004).
[Crossref]

Flannery, B. P.

W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, 2002).

Gansterer, W. N.

W. N. Gansterer, R. C. Ward, and R. P. Muller, ACM Trans. Math. Softw. 28, 45 (2002).
[Crossref]

Golub, G. H.

G. H. Golub, SIAM Rev. 15, 318 (1973).
[Crossref]

Gu, M.

M. Gu and S. C. Eisenstat, 'A stable and fast algorithm for updating the singular value decomposition,' Tech. Rep. YALEU/DCS/RR-966 (Yale University, 1994).

Hall, P. M.

P. M. Hall, A. D. Marshall, and R. R. Martin, IEEE Trans. Pattern Anal. Mach. Intell. 22, 1042 (2000).
[Crossref]

Hegde, A.

D. Erdogmus, Y. N. Rao, H. Peddaneni, A. Hegde, and J. C. Principe, J. Appl. Signal Processing 13, 2034 (2004).
[Crossref]

Li, Y.

Y. Li, Pattern Recognition 37, 1509 (2004).
[Crossref]

Liu, X.

X. Liu and T. Chen, in Proceedings of the International Conference on Acoustics Speech and Signal Processing (IEEE, 2002), pp. 3389-3392.

Marshall, A. D.

P. M. Hall, A. D. Marshall, and R. R. Martin, IEEE Trans. Pattern Anal. Mach. Intell. 22, 1042 (2000).
[Crossref]

Martin, R. R.

P. M. Hall, A. D. Marshall, and R. R. Martin, IEEE Trans. Pattern Anal. Mach. Intell. 22, 1042 (2000).
[Crossref]

Muller, R. P.

W. N. Gansterer, R. C. Ward, and R. P. Muller, ACM Trans. Math. Softw. 28, 45 (2002).
[Crossref]

Nielsen, C. P.

J. R. Bunch, C. P. Nielsen, and D. C. Sorensen, Numer. Math. 31, 31 (1978).
[Crossref]

Peddaneni, H.

D. Erdogmus, Y. N. Rao, H. Peddaneni, A. Hegde, and J. C. Principe, J. Appl. Signal Processing 13, 2034 (2004).
[Crossref]

Pentland, A.

M. Turk and A. Pentland, J. Cogn. Neurosci. 3, 71 (1991).
[Crossref]

Press, W. H.

W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, 2002).

Principe, J. C.

D. Erdogmus, Y. N. Rao, H. Peddaneni, A. Hegde, and J. C. Principe, J. Appl. Signal Processing 13, 2034 (2004).
[Crossref]

Rao, Y. N.

D. Erdogmus, Y. N. Rao, H. Peddaneni, A. Hegde, and J. C. Principe, J. Appl. Signal Processing 13, 2034 (2004).
[Crossref]

Sorensen, D. C.

J. R. Bunch, C. P. Nielsen, and D. C. Sorensen, Numer. Math. 31, 31 (1978).
[Crossref]

Teukolsky, S. A.

W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, 2002).

Turk, M.

M. Turk and A. Pentland, J. Cogn. Neurosci. 3, 71 (1991).
[Crossref]

Vetterling, W. T.

W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, 2002).

Ward, R. C.

W. N. Gansterer, R. C. Ward, and R. P. Muller, ACM Trans. Math. Softw. 28, 45 (2002).
[Crossref]

ACM Trans. Math. Softw. (1)

W. N. Gansterer, R. C. Ward, and R. P. Muller, ACM Trans. Math. Softw. 28, 45 (2002).
[Crossref]

IEEE Trans. Pattern Anal. Mach. Intell. (1)

P. M. Hall, A. D. Marshall, and R. R. Martin, IEEE Trans. Pattern Anal. Mach. Intell. 22, 1042 (2000).
[Crossref]

J. Appl. Signal Processing (1)

D. Erdogmus, Y. N. Rao, H. Peddaneni, A. Hegde, and J. C. Principe, J. Appl. Signal Processing 13, 2034 (2004).
[Crossref]

J. Cogn. Neurosci. (1)

M. Turk and A. Pentland, J. Cogn. Neurosci. 3, 71 (1991).
[Crossref]

Numer. Math. (1)

J. R. Bunch, C. P. Nielsen, and D. C. Sorensen, Numer. Math. 31, 31 (1978).
[Crossref]

Pattern Recognition (1)

Y. Li, Pattern Recognition 37, 1509 (2004).
[Crossref]

SIAM Rev. (1)

G. H. Golub, SIAM Rev. 15, 318 (1973).
[Crossref]

Other (3)

M. Gu and S. C. Eisenstat, 'A stable and fast algorithm for updating the singular value decomposition,' Tech. Rep. YALEU/DCS/RR-966 (Yale University, 1994).

X. Liu and T. Chen, in Proceedings of the International Conference on Acoustics Speech and Signal Processing (IEEE, 2002), pp. 3389-3392.

W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, 2002).

Cited By

OSA participates in Crossref's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Equations (28)

Equations on this page are rendered with MathJax. Learn more.

A p = 1 p i = 1 p s i s i t = D D t ,
A p + 1 = 1 p + 1 i = 1 p + 1 s i s i t = p p + 1 A p + 1 p + 1 s p + 1 s p + 1 t q 1 p + 1 s p + 1 H p p + 1 A p = p p + 1 D D t = H + q q t .
( H + q q t ) y = μ y .
H y μ y + q q y = 0 ,
( H μ I ) y + q q y = 0 .
1 + q t ( H + μ I ) 1 q = 0 .
( H μ I ) 1 = i 1 ( λ i μ ) x i x i t .
q = i α i x i = α 1 x 1 + α 2 x 2 + + α n x n .
1 + α 1 2 ( λ 1 μ ) + α 2 2 ( λ 2 μ ) + + α n 2 ( λ n μ ) = 0 .
y i = ( H μ i I ) 1 q .
y i = k = 1 n α k ( λ k μ i ) x k .
A p + 1 = p p + 1 A p + 1 p + 1 s p + 1 s p + 1 t q 1 p + 1 s p + 1 E E t p p + 1 A p = p p + 1 D D t = [ E q ] × [ E q ] t .
[ E t E E t q q t E q t q ] [ w ̂ η ] = μ w = μ [ w ̂ η ] , w = [ w ̂ η ] .
E t E w ̂ + η E t q = μ w ̂ ,
q t E w ̂ + η q t q = μ η .
E t E w ̂ μ w ̂ + η E t q = 0 ,
( E t E μ ) w ̂ + η E t q = 0 ,
w ̂ + η ( E t E μ ) 1 E t q = 0 .
q t E w ̂ + η q t E ( E t E μ ) 1 E t q = 0 .
( μ q t q ) + q t E ( E t E μ I ) 1 E t q = 0 .
( E t E μ I ) 1 = i 1 ( λ i μ ) u i u i t .
E t q = i β i u i = β 1 u 1 + β 2 u 2 + + β p u p .
μ q t q + β 1 2 ( λ 1 μ ) + β 2 2 ( λ 2 μ ) + + β p 2 ( λ p μ ) = 0 .
w i = [ w ̂ i η i ] , i = 1 p + 1 ,
w ̂ i = ( E t E μ i I ) 1 E t q ,
η i = q t E w ̂ i μ i q t q .
w ̂ i = k = 1 p β k ( λ k μ i ) u k ,
η i = k = 1 p β k 2 ( λ k μ i ) ( μ i q t q ) , i = 1 p + 1 .

Metrics