In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix , the algorithm will produce a number , which is the greatest (in absolute value) eigenvalue of , and a nonzero vector , which is a corresponding eigenvector of , that is, . The algorithm is also known as the Von Mises iteration. Power iteration is a very simple algorithm, but it may converge slowly. The most time-consuming operation of the algorithm is the multiplication of matrix by a vector, so it is effective for a very large sparse matrix with appropriate implementation. The power iteration algorithm starts with a vector , which may be an approximation to the dominant eigenvector or a random vector. The method is described by the recurrence relation So, at every iteration, the vector is multiplied by the matrix and normalized. If we assume has an eigenvalue that is strictly greater in magnitude than its other eigenvalues and the starting vector has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then a subsequence converges to an eigenvector associated with the dominant eigenvalue. Without the two assumptions above, the sequence does not necessarily converge. In this sequence, where is an eigenvector associated with the dominant eigenvalue, and . The presence of the term implies that does not converge unless . Under the two assumptions listed above, the sequence defined by converges to the dominant eigenvalue (with Rayleigh quotient). One may compute this with the following algorithm (shown in Python with NumPy): #!/usr/bin/env python3 import numpy as np def power_iteration(A, num_iterations: int):

Ideally choose a random vector

To decrease the chance that our vector

Is orthogonal to the eigenvector

b_k = np.random.rand(A.shape[1]) for _ in range(num_iterations):

calculate the matrix-by-vector product Ab

b_k1 = np.dot(A, b_k)

calculate the norm

b_k1_norm = np.linalg.norm(b_k1)

re normalize the vector

b_k = b_k1 / b_k1_norm return b_k power_iteration(np.

SPEEDING UP KRYLOV SUBSPACE METHODS FOR COMPUTING f(A)b VIA RANDOMIZATION

Daniel Kressner, Alice Cortinovis

This work is concerned with the computation of the action of a matrix function f(A), such as the matrix exponential or the matrix square root, on a vector b. For a general matrix A, this can be done by computing the compression of A onto a suitable Krylov ...

Siam Publications2024

Learning ground states of gapped quantum Hamiltonians with Kernel Methods

Giuseppe Carleo, Riccardo Rossi, Clemens Giuliani, Filippo Vicentini

Neural network approaches to approximate the ground state of quantum hamiltonians require the numerical solution of a highly nonlinear optimization problem. We introduce a statistical learning approach that makes the optimization trivial by using kernel me ...

Wien2023

Estimation of Self-Exciting Point Processes from Time-Censored Data

Thomas Alois Weber, Philipp Schneider

Self-exciting point processes, widely used to model arrival phenomena in nature and society, are often difficult to identify. The estimation becomes even more challenging when arrivals are recorded only as bin counts on a finite partition of the observatio ...

2023