Principal Components algorithms

[Terence D. Sanger]

Dear Connectionists,

Recently, several people have asked me about the relationship between
Kung&Diamantaras's APEX algorithm and the GHA algorithm I proposed in 1988.
I can summarize my view of algorithms for Principal Components Analysis
(PCA) by grouping them into 3 categories:

1) Algorithms to find the first principal component

2) Algorithms to find a set of vectors which spans the subspace of the
first m principal components

3) Algorithms which find the first m principal components (eigenvectors)
directly

(I can provide a fairly extensive bibliography of these to anyone who is
interested.)  

APEX and GHA (among many others) are in category 3.  Most algorithms in
category 3 make use of an algorithm from category 1 (such as Oja's method)
combined with a deflation procedure which removes components from the input
as they are discovered by the network.  In other words, an algorithm to
find the first principal component will actually find the second one once
the first component is removed.  Continuing this procedure allows all
components to be extracted.  Note that pure "Hebbian" algorithms usually
fall into category 1.

I propose the following hypothesis:
  "All algorithms for PCA which are based on a Hebbian learning rule must
use sequential deflation to extract components beyond the first." 

All category 3 algorithms that I know about conform to the hypothesis.  The
easiest example is GHA, which was specifically designed as a
differential-equation implementation of sequential deflation.  

It turns out that APEX also conforms to the hypothesis, despite the
apparent use of lateral connections instead of deflation.  Some fairly
straightforward mathematics shows that the APEX equations can be rewritten
in such a way that they are almost equivalent to the GHA equations.
(Instructions for obtaining a Latex file with the derivation are below.)
The use of lateral connections in APEX may indicate a more "biologically
plausible" implementation than the original GHA formulation, but the
performance of the two algorithms should be almost identical. 

Another apparently different algorithm which nevertheless conforms to the
hypothesis is Brockett's.  It is possible to think of GHA as a
"thresholded" form of Brockett's algorithm. (Instructions for Latex file
are below.)

I appreciate all comments/opinions/counterexamples, so please feel free!

Regards to all,
			Terry Sanger     (tds at ai.mit.edu)



Instructions for retrieving latex document:

ftp ftp.ai.mit.edu
login: anonymous
password: your-net-address
cd pub/sanger-papers
get apex.tex
get brockett.tex
quit
latex apex
latex brockett
lpr apex.dvi
lpr brockett.dvi