The basic reason is the Johnson-Lindenstrauss lemma which says that you can approximate the structure of an operator with a small number of random vectors. Krylog sub-space methods like Lanczos use only a single random vector and with repeated multiplication, round-off errors shoot off in the direction of the larger eigenvectors. When looking for the smaller eigenvalues, this makes re-orthogonalization happen.
With these randomized algorithms, you multiply several random vectors by your matrix A at one time to get A R = y. Since you choose a few extra vectors in R, you know with high certainty that the projection of these random vectors y spans the range of A. This means that you can use y to compute an orthonormal basis of A very accurately. So the key trick here is that unlike power methods, you aren't doing repeated multiplications by A. That avoids the entire round-off explosion problem. Moreover, since all of these multiplications are independent, you can do these multiplications row by row on A. As you do this, you can store A R and at the same time be recursively doing a random decomposition on AR so that after one pass of the data, you have a small dense matrix to work on. Another pass over AR and one on A' later and you have full decomposition. If you only want one of the sets of eigenvectors, then you only need the pass over AR which is much smaller than A. On Fri, Sep 25, 2009 at 12:21 PM, Jake Mannix <[email protected]> wrote: > On Fri, Sep 25, 2009 at 12:11 PM, Ted Dunning <[email protected]> > wrote: > > a) the random vectors are multiplied by A simultaneously rather than > > sequentially as in Lanczos > > > > b) no risk of losing orthgonality > > > > I haven't read the papers in detail yet, have you seen how these two points > are done? In a parallel environment, how do you maintain orthogonality > while > looking for multiple projection directions? Whats to keep you from finding > the same > directions? -- Ted Dunning, CTO DeepDyve
