Implementing PCA/Whitening

Revision as of 20:30, 4 April 2011 (view source)

(Created page with "In this section, we summarize the PCA, PCA whitening and ZCA whitening algorithms, and also describe how you can implement them using efficient linear algebra libraries. First, ...")

← Older edit

Revision as of 03:28, 6 April 2011 (view source)

Cyfoo (Talk | contribs)

m (sigma bug)

Newer edit →

Line 2:

and also describe how you can implement them using efficient linear algebra libraries.

-

First, we need to compute <math>\textstyle \Sigma = \sum_{i=1}^m (x^{(i)})(x^{(i)})^T</math>. If you're

+

First, we need to compute <math>\textstyle \Sigma = \frac{1}{m} \sum_{i=1}^m (x^{(i)})(x^{(i)})^T</math>. If you're implementing this in Matlab (or even if you're implementing this in C++, Java, etc., but have access to an efficient linear algebra library), doing it as an explicit sum is inefficient. Instead, we can instead compute this in one fell swoop as

-

implementing this in Matlab (or even if you're implementing this in C++, Java, etc.,

+

-

but have access to an efficient linear algebra library), doing it as an explicit sum is inefficient.

+

-

Instead, we can instead compute this in one fell swoop as

+

-

Sigma = x * x';

+

Sigma = x * x' / size(x, 2);

(Check the math yourself for correctness.)

-

Here, we assume that <math>x</math> is a ~~datastructure~~ that contains one training

+

Here, we assume that <math>x</math> is a data structure that contains one training example per column (so, <math>x</math> is a <math>\textstyle n</math>-by-<math>\textstyle m</math> matrix).

-

example per column (so, <math>x</math> is a <math>\textstyle n</math>-by-<math>\textstyle m</math> matrix).

+

-

Next, PCA computes the eigenvectors of {\tt Sigma}. One could do this using the

+

Next, PCA computes the eigenvectors of {\tt Sigma}. One could do this using the Matlab <math>eig</math> function. However, because <math>Sigma</math> is a symmetric positive semi-definite matrix, it is more numerically reliable to do this using the <math>svd</math> function. Concretely, if you implement

-

Matlab <math>eig</math> function. However, because <math>Sigma</math> is a symmetric

+

-

positive semi-definite matrix, it is more numerically reliable to do this

+

-

using the <math>svd</math> function. Concretely, if you implement

+

[U,S,V] = svd(Sigma);

-

then the matrix <math>U</math> will contain the eigenvectors of <math>Sigma</math> (one eigenvector per column,

+

then the matrix <math>U</math> will contain the eigenvectors of <math>Sigma</math> (one eigenvector per column, sorted in order from top to bottom eigenvector), and the diagonal entries of the matrix <math>S</math> will contain the corresponding eigenvalues (also sorted in decreasing order). The matrix <math>V</math> will be equal to transpose of <math>U</math>, and can be safely ignored.

-

sorted in order from top to bottom eigenvector),

+

-

and the diagonal entries of the matrix <math>S</math> will contain the corresponding eigenvalues

+

-

(also sorted in decreasing order). The matrix <math>V</math> will be equal to transpose of <math>U</math>,

+

-

and can be safely ignored.

+

-

(Note: The <math>svd</math>

+

(Note: The <math>svd</math> function actually computes the singular vectors and singular values of a matrix, which for the special case of a symmetric positive semi-definite matrix---which is all that we're concerned with here---is equal to its eigenvectors and eigenvalues. A full discussion of singular vectors vs. eigenvectors is beyond the scope of these notes.)

-

function actually computes the singular vectors and singular values of a matrix, which for

+

-

the special case of a symmetric positive semi-definite matrix---which is all that

+

-

we're concerned with here---is equal to its eigenvectors and eigenvalues. A

+

-

full discussion of singular vectors vs. eigenvectors is beyond the scope of

+

-

these notes.)

+

Finally, you can compute <math>\textstyle x_{\rm rot}</math> and <math>\textstyle \tilde{x}</math> as follows:

Implementing PCA/Whitening

From Ufldl

Revision as of 03:28, 6 April 2011

Views

Personal tools

ufldl resources

wiki

Search

Toolbox

@@ Line 2: / Line 2: @@
 and also describe how you can implement them using efficient linear algebra libraries.
-First, we need to compute <math>\textstyle \Sigma = \sum_{i=1}^m (x^{(i)})(x^{(i)})^T</math>.  If you're
+First, we need to compute <math>\textstyle \Sigma = \frac{1}{m} \sum_{i=1}^m (x^{(i)})(x^{(i)})^T</math>.  If you're implementing this in Matlab (or even if you're implementing this in C++, Java, etc., but have access to an efficient linear algebra library), doing it as an explicit sum is inefficient. Instead, we can instead compute this in one fell swoop as
-implementing this in Matlab (or even if you're implementing this in C++, Java, etc.,
-but have access to an efficient linear algebra library), doing it as an explicit sum is inefficient.
-Instead, we can instead compute this in one fell swoop as
-  Sigma = x * x';
+  Sigma = x * x' / size(x, 2);
 (Check the math yourself for correctness.)
-Here, we assume that <math>x</math> is a datastructure that contains one training
+Here, we assume that <math>x</math> is a data structure that contains one training example per column (so, <math>x</math> is a <math>\textstyle n</math>-by-<math>\textstyle m</math> matrix).
-example per column (so, <math>x</math> is a <math>\textstyle n</math>-by-<math>\textstyle m</math> matrix).
-Next, PCA computes the eigenvectors of {\tt Sigma}.  One could do this using the
+Next, PCA computes the eigenvectors of {\tt Sigma}.  One could do this using the Matlab <math>eig</math> function.  However, because <math>Sigma</math> is a symmetric positive semi-definite matrix, it is more numerically reliable to do this using the <math>svd</math> function. Concretely, if you implement
-Matlab <math>eig</math> function.  However, because <math>Sigma</math> is a symmetric
-positive semi-definite matrix, it is more numerically reliable to do this
-using the <math>svd</math> function.  Concretely, if you implement
   [U,S,V] = svd(Sigma);
-then the matrix <math>U</math> will contain the eigenvectors of <math>Sigma</math> (one eigenvector per column,
+then the matrix <math>U</math> will contain the eigenvectors of <math>Sigma</math> (one eigenvector per column,  sorted in order from top to bottom eigenvector), and the diagonal entries of the matrix <math>S</math> will contain the corresponding eigenvalues (also sorted in decreasing order).  The matrix <math>V</math> will be equal to transpose of <math>U</math>, and can be safely ignored.
-sorted in order from top to bottom eigenvector),
-and the diagonal entries of the matrix <math>S</math> will contain the corresponding eigenvalues
-(also sorted in decreasing order).  The matrix <math>V</math> will be equal to transpose of <math>U</math>,
-and can be safely ignored.
-(Note: The <math>svd</math>
+(Note: The <math>svd</math> function actually computes the singular vectors and singular values of a matrix, which for the special case of a symmetric positive semi-definite matrix---which is all that we're concerned with here---is equal to its eigenvectors and eigenvalues.  A full discussion of singular vectors vs. eigenvectors is beyond the scope of these notes.)
-function actually computes the singular vectors and singular values of a matrix, which for
-the special case of a symmetric positive semi-definite matrix---which is all that
-we're concerned with here---is equal to its eigenvectors and eigenvalues.  A
-full discussion of singular vectors vs. eigenvectors is beyond the scope of
-these notes.)
 Finally, you can compute <math>\textstyle x_{\rm rot}</math> and <math>\textstyle \tilde{x}</math> as follows: