Does the Lanczos starting vector have to be random?

Question

In all descriptions of the Lanczos vector, it's said that the starting vector is random.

But let's say I'm only interested in the eigenvector associated with the lowest eigenvalue (as is the case when using Lanczos to find the ground-state of a quantum mechanical system).

Wouldn't then any start vector that has some non-zero overlap with the ground-state do?

Answer 1

The other answers make some excellent suggestions, but for the sake of completeness, let me give an explicit answer to the two questions you posed:

1. No, the starting vector does not have to be random, and

2. Yes, any vector with a non-zero projection onto the desired eigenvector will do. (A random vector is just the simplest reliable way of achieving that in the absence of further information.)

This is independent of which (or how many) eigenvectors you want to find; as long as your starting vector has non-zero projection onto the corresponding eigenspace, the Lanczos approximations of a given eigenvalue will converge (with a speed depending on, among others, the magnitude of the projection¹). The details are a bit technical, but you can find them for example in Youcef Saad's book on iterative methods (in particular, Theorem 6.4 on page 149).

---

_{1. In fact, if the starting vector is an eigenvector (or more generally, lies in the eigenspace), the Lanczos method will give you the corresponding eigenvalue in a single iteration.}

Answer 2

If an algorithm starts with a random vector and is known to converge to a correct result, that means that it can work with an arbitrary vector. How would it succeed starting from an arbitrary random vector otherwise?

The only exception might be that there is a set of vectors for which the algorithm fails, but which are picked with essentially zero probability.

This isn't specific to Lanczos algorithm either: this would apply to any algorithm that doesn't require a stream of random vectors and doesn't rely on good statistical properties of the RNG.

Mostly this is done for convenience, because for a fixed vector $u$ the probability that $u^\top v = 0$ is zero for most sensible probability distributions over $v$, thus the picked starting random vector $v$ can be assumed to not be special in any way.

Answer 3

But let's say I'm only interested in the eigenvector associated with the lowest eigenvalue (as is the case when using Lanczos to find the ground-state of a quantum mechanical system).

You'd want to use a shift-and-invert spectral transformation with an estimate of the eigenvalue you care about. Lanczos normally finds the largest magnitude eigenvalue and its eigenvector (after some post-processing); inversion transforms the problem to solving the smallest magnitude eigenvalue, and shifting transforms the problem to solving for the eigenvalue closest to an eigenvalue of interest (the shift).

Wouldn't then any start vector that has some non-zero overlap with the ground-state do?

If I remember correctly, if you give Lanczos the exact eigenvector corresponding to a given eigenvalue, it will only generate the Krylov subspace corresponding to that eigenvector-eigenvalue pair, assuming all calculations are performed in exact arithmetic. In double precision arithmetic, with some partial reorthogonalization, it will eventually generate a basis, given enough iterations (with probability 1, since on a set of measure zero, there are pathological inputs, as Kirill points out). So, essentially any starting vector will work.