6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ And how would you pick such a starting vector, if you don't know the ground-state beforehand (otherwise you wouldn't need Lanczos in the first place)? You pick one at random, and hope for the best... $\endgroup$ – Christian Clason Aug 18 '15 at 21:31
  • $\begingroup$ @ChristianClason: One may have a sequence of problems to solve with slightly perturbed data. $\endgroup$ – hardmath Aug 19 '15 at 18:42
  • $\begingroup$ @hardmath: Of course, and then you could use the solution of the previous problem as a starting vector (and basis of the Krylov space). There is nothing in the Lanczos algorithm that requires a random vector -- you only need to guarantee a non-zero projection onto the desired eigenspaces. A random vector is just the simplest and most reliable way if you don't know anything else. That is all I wanted to point out (needlessly facetiously, in hindsight). $\endgroup$ – Christian Clason Aug 19 '15 at 19:01
5
$\begingroup$

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 projection1). 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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.