Use power iteration and Dimensionality reduction for eigenvalues

[Beakerboy]

I think I figured out the general technique for simultaneously finding eigenvalues and eigenvectors for any matrix...numerically.

use power iteration to find largest...this gives both the value and the vector, then subtract it from the source matrix and repeat.

$eigenvalues = [];
$vectors = [];
for ($i = 0l $i < $A->getM(); $i++) {
    list ($eigenvalue, $eigenvector) = Eigen::powerIteration($A);
    $eigenvalues[] = $eigenvalue;
    $vector = MatrixFactory::columnMatrix($eigenvector);
    $vectors[] = $eigenvector; // Adding as a new row
    $A = $A->subtract($vector->multiply($vector->transpose())->scalarMultiply($value));
}
$eigenvectors = MatrixFactory::create($vectors)->transpose();

[markrogoyski]

Is there a use case for this that differs from existing methods? Like it is better for large matrices vs Jacobi, for instance?

[Beakerboy]

The Jacobi method only works on symmetric matrixes.

[markrogoyski]

Would implementing this solve issue https://github.com/markrogoyski/math-php/issues/346 where power Iteration finds an eigenvalue that is not necessarily the dominant one because of the selection of the random starting vector? Basically, could you use this process to find all the eigenvalues, and then just figure out what the dominant one is and return that for the powerIteration method?

[Beakerboy]

That’s a good idea. Instead of finding just the “largest”, find a few and then grab the largest of those. Alternatively, I wonder if, after a solution is found, the solution eigenvector could be perturbed slightly and used as a new starting point to ensure that it converges on the same eigenvalue, and not one that is larger.