The lanczos algorithm under few iterations: Concentration and location of the output

We study the Lanczos algorithm where the initial vector is sampled uniformly from Sn 1. Let A be an n \times n Hermitian matrix. We show that when run for few iterations, the output of Lanczos on A is almost deterministic. More precisely, we show that for any \varepsilon \in (0, 1) there exists c > 0 depending only on \varepsilon and a certain global property of the spectrum of A (in particular, not depending on n) such that when Lanczos is run for at most c log n iterations, the output Jacobi coefficients deviate from their medians by t with probability at most exp( n\varepsilon t2) for t < \| A\| . We directly obtain a similar result for the Ritz values and vectors. Our techniques also yield asymptotic results: Suppose one runs Lanczos on a sequence of Hermitian matrices An \in Mn(C) whose spectral distributions converge in Kolmogorov distance with rate O(n \varepsilon ) to a density \mu for some \varepsilon > 0. Then we show that for large enough n, and for k = O( \surd log n), the Jacobi coefficients output after k iterations concentrate around those for \mu . The asymptotic setting is relevant since Lanczos is often used to approximate the spectral density of an infinite-dimensional operator by way of the Jacobi coefficients; our result provides some theoretical justification for this approach. In a different direction, we show that Lanczos fails with high probability to identify outliers of the spectrum when run for at most c\prime log n iterations, where again c\prime depends only on the same global property of the spectrum of A. Classical results imply that the bound c\prime log n is tight up to a constant factor.