Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. (English) Zbl 1269.65043

Halko, N.; Martinsson, P. G.; Tropp, J. A.

SIAM Rev. 53, No. 2, 217-288 (2011).

MSC:

65F30	Other matrix algorithms (MSC2010)
68W20	Randomized algorithms
60B20	Random matrices (probabilistic aspects)
65F20	Numerical solutions to overdetermined systems, pseudoinverses
65Y05	Parallel numerical computation
15B52	Random matrices (algebraic aspects)
62-07	Data analysis (statistics) (MSC2010)
68W30	Symbolic computation and algebraic computation

Keywords:

dimension reduction; eigenvalue decomposition; interpolative decomposition; Johnson-lindenstrauss lemma; matrix approximation; parallel algorithm; pass-efficient algorithm; principal component analysis; randomized algorithm; random matrix; rank-revealing QR factorization; singular value decomposition; streaming algorithm; numerical examples; data analysis; scientific computing;sparse input matrix; Krylov subspace methods