gov.sandia.cognition.math.matrix.decomposition

## Class 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
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

All Methods
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.
Constant Field Values
• #### DEFAULT_MAXIMUM_ITERATIONS

`public static final int DEFAULT_MAXIMUM_ITERATIONS`
Default maximum iterations for power iteration, 100.
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