Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 80 views

    Three Derivations of Principal Component Analysis

    Uploaded by

    ritesh sinha
    There are three main derivations of principal component analysis (PCA): 1. By maximizing variance - the PCA basis vectors are the eigenvectors of the covariance/correlation matrix, as these vectors maximize the variance of the projected data points. 2. By minimizing error - the PCA basis vectors minimize the reconstruction error when representing data points as a linear combination of the basis vectors. 3. By diagonalizing the correlation matrix - if the data is transformed by the eigenvectors of the correlation matrix, this diagonalizes the correlation matrix of the transformed data.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Three Derivations of Principal Component Analysis

    Uploaded by

    ritesh sinha
    80 views2 pages
    There are three main derivations of principal component analysis (PCA): 1. By maximizing variance - the PCA basis vectors are the eigenvectors of the covariance/correlation matrix, as these vectors maximize the variance of the projected data points. 2. By minimizing error - the PCA basis vectors minimize the reconstruction error when representing data points as a linear combination of the basis vectors. 3. By diagonalizing the correlation matrix - if the data is transformed by the eigenvectors of the correlation matrix, this diagonalizes the correlation matrix of the transformed data.

    Original Title

    lewis_pca_derivs

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    There are three main derivations of principal component analysis (PCA): 1. By maximizing variance - the PCA basis vectors are the eigenvectors of the covariance/correlation matrix, as these vectors maximize the variance of the projected data points. 2. By minimizing error - the PCA basis vectors minimize the reconstruction error when representing data points as a linear combination of the basis vectors. 3. By diagonalizing the correlation matrix - if the data is transformed by the eigenvectors of the correlation matrix, this diagonalizes the correlation matrix of the transformed data.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    80 views2 pages

    Three Derivations of Principal Component Analysis

    Uploaded by

    ritesh sinha
    There are three main derivations of principal component analysis (PCA): 1. By maximizing variance - the PCA basis vectors are the eigenvectors of the covariance/correlation matrix, as these vectors maximize the variance of the projected data points. 2. By minimizing error - the PCA basis vectors minimize the reconstruction error when representing data points as a linear combination of the basis vectors. 3. By diagonalizing the correlation matrix - if the data is transformed by the eigenvectors of the correlation matrix, this diagonalizes the correlation matrix of the transformed data.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Three Derivations of Principal Components j.p.

    lewis

    Three Derivations of Principal Component Analysis

    Why are the PCA basis vectors the eigenvectors of the correlation matrix?

    Derivation #1: by maximizing variance

    ¿From Ballard & Brown, Computer Vision: The (random) data vector is x; its component along a proposed axis u is (x · u).
    The variance of this is E(x · u − E(x · u))2 (the variance is the expectation of the square of the data with its mean removed).

    E(x · u − E(x · u))2 = E[(u · (x − Ex))2 ]


    = uE[(x − Ex) · (x − Ex)T ]u
    = uT Cu

    C is the covariance or ’correlation’ matrix. The u that gives the maximum value to u T Cu (with the constraint that u is a unit
    vector) is the eigenvector of C with the largest eigenvalue. The second and subsequent principal component axes are the other
    eigenvectors sorted by eigenvalue.

    #2: ...by error minimization

    Find PCA basis vectors u that minimize E||x − x̂||2 for a partial expansion out to P components:

    X
    P
    x̂ = (x · uk )uk
    k=1

    X
    N
    x − x̂ = (x · uk )uk
    k=P +1

    where N is the full set of vectors necessary to represent the data.


    So, minimize the square of the last sum. The cross terms disappear because of the orthogonality of u k . For each term:

    E((x · u)u)2 = Eu(x · u)(x · u)u

    the outer u’s disappear because u · u = 1.


    = E(x · u)(x · u) = uCu
    But uCu = λ, so the truncation error is the sum of the lower eigenvalues! Why: we know that u are eigenvectors, so they
    satisfy Cu = λu, also u · u = 1, so....

    #3: ...by diagonalizing the correlation matrix

    The correlation matrix of some data: C = E[xxT ]. The correlation matrix of the data x transformed by some transform T:
    C 0 = E[T x(T x)T ] = E[T xxT T T ]. The inner xxT is the correlation matrix of the original data. Now suppose that the rows
    of T are chosen to be the eigenvectors of this correlation matrix– then because of the orthogonality of the eigenvectors, the
    resuling matrix C’ will be diagonal. Thus C’, the correlation matrix of the transformed data, is uncorrelated. So the basis that
    diagonalizes the correlation matrix consists of the eigenvectors of the (original) correlation matrix.
    Three Derivations of Principal Components j.p.lewis

    Correlation matrices

    For a vector x, ExxT is a correlation matrix.


    Say M is a matrix whose columns contain data vectors. I think both M M T and M M T can be interpreted as correlation
    matrices.
    M M T is the usual correlation matrix, a sum of outer products:
    X
    (M M T )i,j = xk [i]xk [j]
    k
    X
    T
    (M M ) = xk xTk ≈ ExxT = C
    k

    If xk are a sliding window through a signal, i.e. x0 contains samples 0..10, x1 samples 1..11, etc., then this corresponds to
    estimating the autocovariance of the signal. If xk are images scanned into a vector, this gives the average (after dividing by N)
    correlation of pixel i with pixel j.
    The i, j entry of M T M is the dot of data vector i with data vector j. If a column of M contains various measurements for a
    particular person then (M T M )i,j gives the correlation, averaged across tests, of person i with person j, while (M M T )i,j gives
    the correlation, averaged across people, of test i versus test j.

    PCA and SVD

    SVD decomposes a possibly non-square matrix M into USV where U,V are square rotation-like matrices and S is a diagonal
    matrix of singular values. The columns of U are the eigenvectors of M M T , the columns of V are the eigenvectors of M T M .

    Computation Trick

    If we are computing PCA on an image, M will be (e.g.) a million by N (N images), and M M T will be million2 . Instead, first
    find the eigenvectors of M T M (which is N xN ): M T M x = λx. Then premultiply by M and interpret as (M M T )(M x) =
    λ(M x), i.e., M x are the desired eigenvectors, now given as a linear combination of the original data using weights which are
    the eigenvector of the smaller system.

    You might also like