Ground-State Projection

Ground-state projection applies a function of the Hamiltonian that enhances a desired low-energy eigenspace relative to the rest. Power iteration, imaginary-time evolution, and polynomial filtering share this mechanism. Their practical differences are the cost of the filter, the spectral information it needs, and its sensitivity to roundoff and small gaps.

Helpful background. Matrix diagonalization supplies spectral decompositions and residual tests.

Filter ratios determine convergence

For a finite Hermitian matrix, let $H|n\rangle=E_n|n\rangle$ with $E_0<E_1\leq\cdots$, and let $|\psi\rangle=\sum_n c_n|n\rangle$, where $c_0\neq0$. After $k$ filter applications,

$$F(H)^k|\psi\rangle =\sum_n c_nF(E_n)^k|n\rangle.$$

If $|F(E_0)|>|F(E_n)|$ for all $n>0$, normalized iteration converges toward the ground state. Defining

$$\rho=\max_{n>0}\left|\frac{F(E_n)}{F(E_0)}\right|<1,$$

the unwanted-to-wanted amplitude ratio decreases at least as $\rho^k$ times its initial value. A good filter reduces $\rho$ without making each application prohibitively expensive.

For $F(E)=a-E$ with $a>E_{\max}$, the ground eigenvalue has largest magnitude, and the leading ratio is $(a-E_1)/(a-E_0)$. A very large shift makes this ratio close to one and convergence slow. Applying $H$ itself normally targets the largest-magnitude energy, which is not necessarily the ground energy.

Exponential, inverse, and polynomial choices

The filter $F(E)=e^{-\delta\tau E}$ has ratio $e^{-\delta\tau(E_1-E_0)}$ and leads to imaginary-time evolution. Its implementation needs an exponential action or a controlled approximation.

An inverse filter $(H-\sigma I)^{-1}$ emphasizes the eigenvalue closest to $\sigma$. It targets the ground state only with an appropriate shift and spectral knowledge. Each application requires a linear solve, so compare factorization cost and fill-in with repeated matrix–vector products.

For polynomial filtering, map an unwanted energy interval $[a,b]$ to $[-1,1]$,

$$x(E)=\frac{2E-a-b}{b-a}.$$

Chebyshev polynomials obey $|T_m(x)|\leq1$ on this interval, whereas for $x<-1$ their magnitude grows like $\cosh[m\,\operatorname{arcosh}(-x)]$. If $E_0<a$, the filter $T_m(x(H))/T_m(x(E_0))$ can suppress the unwanted interval strongly. In practice one uses estimated bounds and stable rescaling; a wrong spectral interval can amplify unwanted modes. The recurrence $T_{m+1}=2xT_m-T_{m-1}$ makes application matrix-free.

Checking which state has converged

A filter cannot recover a missing symmetry sector from an exactly invariant initial sector. Nor can it separate degenerate ground states by energy alone. For several low states, evolve a block and orthonormalize it, rather than repeatedly projecting one vector and hoping for different answers.

After convergence, calculate the Rayleigh quotient and original residual. A small residual confirms proximity to some eigenspace. Ground-state identification also needs a target argument, a gap or symmetry analysis, and comparison with other starts or methods. Approximate tensor compression or stochastic sampling introduces errors beyond the ideal filtering argument.

As an example, take energies $0,1,4$ and $F(E)=5-E$. Unwanted amplitudes decay relative to the ground as $(4/5)^k$ and $(1/5)^k$. With $F(E)=10-E$, these become $(9/10)^k$ and $(6/10)^k$: the safer-looking larger shift is slower. A starting vector supported only on energies $1$ and $4$ instead converges to the energy-$1$ state with either filter.

Exercises

How many applications are sufficient to suppress an initial amplitude ratio of one below $10^{-6}$ when $\rho=0.8$?

Solution

Require $0.8^k\leq10^{-6}$, giving $k\geq\log(10^{-6})/\log(0.8)\approx61.92$. Thus $62$ applications suffice in the exact filter model. A probability tolerance would involve the square of this amplitude ratio.

References

• Bai, Z., J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, 2000, online text — power iteration, spectral transformations, and subspace methods.
• Saad, Y., Numerical Methods for Large Eigenvalue Problems, revised ed., SIAM, 2011 — polynomial acceleration and iterative spectral approximation.