Randomized LU decomposition

Stewart, 2000, The decompositional approach to matrix computation, Comput. Sci. Eng., 2, 50, 10.1109/5992.814658 Elad, 2006, Image denoising via sparse and redundant representations over learned dictionaries, IEEE Trans. Image Process., 15, 3736, 10.1109/TIP.2006.881969 Mazumder, 2010, Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res., 99, 2287 Koren, 2009, Matrix factorization techniques for recommender systems, Computer, 42, 30, 10.1109/MC.2009.263 Wolf, 2003, Learning over sets using kernel principal angles, J. Mach. Learn. Res., 4, 913 Coifman, 2006, Diffusion maps, Appl. Comput. Harmon. Anal., 21, 5, 10.1016/j.acha.2006.04.006 Shabat, 2015, Accelerating particle filter using randomized multiscale and fast multipole type methods, IEEE Trans. Pattern Anal. Mach. Intell., 37, 1396, 10.1109/TPAMI.2015.2392754 Schenk, 2000, Efficient sparse Lu factorization with left–right looking strategy on shared memory multiprocessors, BIT Numer. Math., 40, 158, 10.1023/A:1022326604210 Demmel, 1999, A supernodal approach to sparse partial pivoting, SIAM J. Matrix Anal. Appl., 20, 720, 10.1137/S0895479895291765 Davis, 1997, An unsymmetric-pattern multifrontal method for sparse LU factorization, SIAM J. Matrix Anal. Appl., 18, 140, 10.1137/S0895479894246905 Golub, 2012 Kirk, 2007, nVidia CUDA software and GPU parallel computing architecture, vol. 7, 103 Martinsson, 2011, A randomized algorithm for the decomposition of matrices, Appl. Comput. Harmon. Anal., 30, 47, 10.1016/j.acha.2010.02.003 Halko, 2011, Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53, 217, 10.1137/090771806 Litvak, 2005, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math., 195, 491, 10.1016/j.aim.2004.08.004 Litvak, 2010, Smallest singular value of sparse random matrices, Studia Math., 212, 195, 10.4064/sm212-3-1 Bermanis, 2013, Multiscale data sampling and function extension, Appl. Comput. Harmon. Anal., 34, 15, 10.1016/j.acha.2012.03.002 David, 2009 Donoho, 2006, Compressed sensing, IEEE Trans. Inform. Theory, 52, 1289, 10.1109/TIT.2006.871582 Avron, 2010, Blendenpik: supercharging LAPACK's least-squares solver, SIAM J. Sci. Comput., 32, 1217, 10.1137/090767911 Chan, 1987, Rank revealing QR factorizations, Linear Algebra Appl., 88, 67 Gu, 1996, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Sci. Comput., 17, 848, 10.1137/0917055 Pan, 2000, On the existence and computation of rank-revealing LU factorizations, Linear Algebra Appl., 316, 199, 10.1016/S0024-3795(00)00120-8 Miranian, 2003, Strong rank revealing LU factorizations, Linear Algebra Appl., 367, 1, 10.1016/S0024-3795(02)00572-4 Cheng, 2005, On the compression of low rank matrices, SIAM J. Sci. Comput., 26, 1389, 10.1137/030602678 Drineas, 2008, Relative-error CUR matrix decompositions, SIAM J. Matrix Anal. Appl., 30, 844, 10.1137/07070471X Rokhlin, 2008, A fast randomized algorithm for overdetermined linear least-squares regression, Proc. Nat. Acad. Sci., 105, 13212, 10.1073/pnas.0804869105 Clarkson, 2013, Low rank approximation and regression in input sparsity time, 81 Achlioptas, 2007, Fast computation of low-rank matrix approximations, J. ACM, 54, 9, 10.1145/1219092.1219097 Clarkson, 2009, Numerical linear algebra in the streaming model, 205 Magen, 2011, Low rank matrix-valued Chernoff bounds and approximate matrix multiplication, 1422 Frieze, 2004, Fast Monte-Carlo algorithms for finding low-rank approximations, J. ACM, 51, 1025, 10.1145/1039488.1039494 Drineas, 2006, Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix, SIAM J. Comput., 36, 158, 10.1137/S0097539704442696 Boutsidis, 2013, Improved matrix algorithms via the subsampled randomized Hadamard transform, SIAM J. Matrix Anal. Appl., 34, 1301, 10.1137/120874540 Bhatia, 1997 Goldstine, 1951, Numerical inverting of matrices of high order II, Proc. Amer. Math. Soc., 2, 188, 10.1090/S0002-9939-1951-0041539-X Rudelson, 2009, Smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math., 62, 1707, 10.1002/cpa.20294 Ailon, 2009, The fast Johnson–Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput., 39, 302, 10.1137/060673096 Woolfe, 2008, A fast randomized algorithm for the approximation of matrices, Appl. Comput. Harmon. Anal., 25, 335, 10.1016/j.acha.2007.12.002 Trefethen, 1990, Average-case stability of Gaussian elimination, SIAM J. Matrix Anal. Appl., 11, 335, 10.1137/0611023 Stewart, 1995 Chen, 2005, Condition numbers of Gaussian random matrices, SIAM J. Matrix Anal. Appl., 27, 603, 10.1137/040616413 Witten, 2013, Randomized algorithms for low-rank matrix factorizations: sharp performance bounds, Algorithmica, 1 Tropp, 2011, Improved analysis of the subsampled randomized Hadamard transform, Adv. Adapt. Data Anal., 3, 115, 10.1142/S1793536911000787 P.-G. Martinsson, A. Szlam, M. Tygert, Normalized power iterations for the computation of SVD, Manuscript, Nov. Larsen, 1998