gov.sandia.cognition.math.matrix.decomposition

Class EigenvectorPowerIteration

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.math.matrix.decomposition.EigenvectorPowerIteration

All Implemented Interfaces:

CloneableSerializable, java.io.Serializable, java.lang.Cloneable

@PublicationReference(author="Wikipedia",
                      title="Power iteration",
                      type=WebPage,
                      year=2009,
                      url="http://en.wikipedia.org/wiki/Power_iteration")
public class EigenvectorPowerIteration
extends AbstractCloneableSerializable

Implementation of the Eigenvector Power Iteration algorithm. The core algorithm finds the eigenvector corresponding to the largest-magnitude eigenvalue by repeated iteration from an initial guess: (v=A*v). The rate of convergence of this algorithm is determined by the ratio of successive eigenvalues. In practice, I usually see convergence to extremely accurate estimates in less than ten iterations. Because this method only involves a simple matrix-vector multiplication, it can be readily used with very large, sparse matrices (which is what Google does). The algorithm requires that the input matrix ("A") be symmetric, but it will converge even when there are negative eigenvalues, repeated eigenvalues, and (in my experience) poorly conditioned matrices. The algorithm is known to have convergence problems in some cases, but I have not seen them occur.

We have also provided another method that will estimate the eigenvectors corresponding to the eigenvalues with the top "numEigenvectors" magnitudes. This algorithm works by finding eigenvectors in sequence with the Power Iteration algorithm and then subtracting the space spanned by the just-found eigenvector: (A=A-v*v'). Rinse, lather, repeat. Because of the subtraction, this is not appropriate for large sparse matrices, as the result will almost certainly be nonsparse. In practice, I have found this approach to be MUCH more computationally efficient than using LAPACK to compute a full EVD of a Matrix. However, we require that the matrix be symmetric (but can have negative or repeated eigenvalues), whereas LAPACK can compute the EVD of a general asymmetric real matrix.

Finally, we also provide a method for estimating the eigenvalue for a matrix and eigenvector.

Since:

2.0

Author:

Kevin R. Dixon

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_MAXIMUM_ITERATIONS Default maximum iterations for power iteration, 100.
static double	DEFAULT_STOPPING_THRESHOLD Default stopping threshold for power iteration, 1.0E-5.

Constructor Summary

Constructors

Constructor and Description
EigenvectorPowerIteration() Creates a new instance of EigenvectorPowerIteration.

Method Summary

Modifier and Type	Method and Description
static double	estimateEigenvalue(Matrix A, Vector v) Finds the eigenvalue associated with the given Matrix and eigenvector.
static Vector	estimateEigenvector(Vector initial, Matrix A, double stoppingThreshold, int maxIterations) Estimates the eigenvector corresponding to the largest magnitude eigenvalue.
static java.util.ArrayList<Vector>	estimateEigenvectors(Matrix A, int numEigenvectors) Estimates the top eigenvectors of the given matrix using the power iteration algorithm.
static java.util.ArrayList<Vector>	estimateEigenvectors(Matrix A, int numEigenvectors, double stoppingThreshold, int maxIterations) Estimates the top eigenvectors of the given matrix using the power iteration algorithm.

Methods inherited from class gov.sandia.cognition.util.AbstractCloneableSerializable

clone

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_STOPPING_THRESHOLD

public static final double DEFAULT_STOPPING_THRESHOLD

Default stopping threshold for power iteration, 1.0E-5.

See Also:

Constant Field Values

DEFAULT_MAXIMUM_ITERATIONS

public static final int DEFAULT_MAXIMUM_ITERATIONS

Default maximum iterations for power iteration, 100.

See Also:

Constant Field Values

Constructor Detail

EigenvectorPowerIteration

public EigenvectorPowerIteration()

Creates a new instance of EigenvectorPowerIteration.

Method Detail

estimateEigenvectors

public static java.util.ArrayList<Vector> estimateEigenvectors(Matrix A,
                                                               int numEigenvectors)

Estimates the top eigenvectors of the given matrix using the power iteration algorithm. This is a very efficient algorithm (used by Google and many others) to estimate the largest "numEigenvectors" eigenvectors of the symmetric matrix "A". By largest eigenvector, we mean the eigenvector corresponding to the largest eigenvalue (and so on). The matrix "A" is permitted to have negative eigenvalues. Power iteration will typically converge in less than ten iterations for for each eigenvector. However, the convergence rate is related to the ratio of sequential eigenvalues, so if a matrix has similar eigenvalues then convergence will be slow.

If you want a full eigendecomposition, you probably should not be using this method, but the EigenDecomposition interface. Please note that all eigenvectors are unique to a direction. That is, sometimes eigenvectors may be a scale factor of -1.0 to eigenvectors found by other approaches or initial conditions.

This approach is appropriate for sparse matrices for finding the top SINGLE eigenvector. That is, if multiple eigenvectors must be computed from a very large-dimension and very sparse matrix, then you should use another algorithm. This is because the first eigenvector is found by repeated multiplication (v=A*v until convergence). However, after the first eigenvector is found, and we are supposed to find more eigenvectors, then we subtract the space spanned by the first eigenvector from the matrix: (A=A-v*v'). This will almost certainly destroy any sparseness in the original matrix and result in a very unpleasant surprise of memory usage.

Note: The Matrix provided is modified for the estimation of the eigenvectors.

Parameters:

A - The matrix to estimate the eigenvectors for. It must be symmetric. It will be modified by the algorithm.

numEigenvectors - The number of eigenvectors to compute.

Returns:

Collection of eigenvectors (of size "numEigenvectors") where the ith entry corresponds to the eigenvector with the ith largest-magnitude eigenvector.

estimateEigenvectors

public static java.util.ArrayList<Vector> estimateEigenvectors(Matrix A,
                                                               int numEigenvectors,
                                                               double stoppingThreshold,
                                                               int maxIterations)

Estimates the top eigenvectors of the given matrix using the power iteration algorithm. This is a very efficient algorithm (used by Google and many others) to estimate the largest "numEigenvectors" eigenvectors of the symmetric matrix "A". By largest eigenvector, we mean the eigenvector corresponding to the largest eigenvalue (and so on). The matrix "A" is permitted to have negative eigenvalues. Power iteration will typically converge in less than ten iterations for for each eigenvector. However, the convergence rate is related to the ratio of sequential eigenvalues, so if a matrix has similar eigenvalues then convergence will be slow.

If you want a full eigendecomposition, you probably should not be using this method, but the EigenDecomposition interface. Please note that all eigenvectors are unique to a direction. That is, sometimes eigenvectors may be a scale factor of -1.0 to eigenvectors found by other approaches or initial conditions.

This approach is appropriate for sparse matrices for finding the top SINGLE eigenvector. That is, if multiple eigenvectors must be computed from a very large-dimension and very sparse matrix, then you should use another algorithm. This is because the first eigenvector is found by repeated multiplication (v=A*v until convergence). However, after the first eigenvector is found, and we are supposed to find more eigenvectors, then we subtract the space spanned by the first eigenvector from the matrix: (A=A-v*v'). This will almost certainly destroy any sparseness in the original matrix and result in a very unpleasant surprise of memory usage.

Note: The Matrix provided is modified for the estimation of the eigenvectors.

Parameters:

A - The matrix to estimate the eigenvectors for. It must be symmetric. It will be modified by the algorithm.

numEigenvectors - The number of eigenvectors to compute.

stoppingThreshold - The stopping threshold for the power iteration algorithm. The algorithm will stop its computation of an eigenvector when the

maxIterations - The maximum number of iterations for the power iteration algorithm.

Returns:

Collection of eigenvectors (of size "numEigenvectors") where the ith entry corresponds to the eigenvector with the ith largest-magnitude eigenvector.

estimateEigenvector

public static Vector estimateEigenvector(Vector initial,
                                         Matrix A,
                                         double stoppingThreshold,
                                         int maxIterations)

Estimates the eigenvector corresponding to the largest magnitude eigenvalue. The eigenvector will be of unit length, unless the input Matrix is all zeros, in which case the method will return an all-zero Vector. Please note that all eigenvectors are unique to a direction. That is, sometimes eigenvectors may be a scale factor of -1.0 to eigenvectors found by other approaches or initial conditions.

This method is appropriate for sparse matrix problems.

Parameters:

initial - Initial estimate of the eigenvector. This is generally a uniform (constant nonzero) Vector.

A - The matrix to estimate the eigenvectors for. It must be symmetric. It will be modified by the algorithm.

stoppingThreshold - The stopping threshold for the power iteration algorithm. The algorithm will stop its computation of an eigenvector when the

maxIterations - The maximum number of iterations for the power iteration algorithm.

Returns:

Eigenvector corresponding to the largest magnitude eigenvalue.

estimateEigenvalue

public static double estimateEigenvalue(Matrix A,
                                        Vector v)

Finds the eigenvalue associated with the given Matrix and eigenvector. This is found by noting that the definition of an eigensystem is: lamba*v=A*v. Therefore, the absolute value of the eigenvalue will be norm2(A*v), but determining the sign of the eigenvalue takes some minor computation (which we do, so this method works with negative eigenvalues).

Parameters:

A - Matrix to estimate the eigenvalue of. May have negative, repeated, positive, or zero eigenvalues

v - Eigenvector associated with the unknown eigenvalue

Returns:

Eigenvalue associated with the eigenvector and Matrix