Randomized algorithms in numerical linear algebra. (English) Zbl 1378.65084
The paper is organized as an introductory survey to the use of randomization in the design of fast algorithms for numerical linear algebra. They consider several computational problems as low rank approximation of matrices, matrix product, tensors related to the randomized (preconditioned) length-squared sampling method.
Reviewer: Constantin Popa (Constanţa)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F08 | Preconditioners for iterative methods |
| 68W20 | Randomized algorithms |
| 15A69 | Multilinear algebra, tensor calculus |
| 62J05 | Linear regression; mixed models |
| 65-02 | Research exposition (monographs, survey articles) pertaining to numerical analysis |
Keywords:
randomized algorithms; regression; low-rank approximation; preconditioning; embeddings; introductory survey; matrix product; tensor; sampling methodReferences:
| [1] | Achlioptas, D.; Mcsherry, F., Fast computation of low-rank matrix approximations, J. Assoc. Comput. Mach., 54, pp., (2007) · Zbl 1311.94031 · doi:10.1145/1219092.1219097 |
| [2] | Ahlswede, R.; Winter, A., Strong converse for identification via quantum channels, IEEE Trans. Inform. Theory, 48, 568-579, (2002) · Zbl 1071.94530 |
| [3] | Anari, N.; Gharan, S.; Rezaei, A., COLT 2016: 29th Conference on Learning Theory, Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes, 103-115, (2016) |
| [4] | Arriaga, R.; Vempala, S., FOCS 1999: 40th Annual Symposium on Foundations of Computer Science, An algorithmic theory of learning: Robust concepts and random projection, 616-623, (1999) |
| [5] | Arriaga, R.; Vempala, S., An algorithmic theory of learning: robust concepts and random projection, Machine Learning, 63, 161-182, (2006) · Zbl 1095.68092 · doi:10.1007/s10994-006-6265-7 |
| [6] | Berry, M.; Pulatova, S.; Stewart, G., pp. |
| [7] | Bhatia, R., Matrix Analysis, pp., (1996), Springer · Zbl 0863.15001 |
| [8] | Boutsidis, C.; Woodruff, D., STOC 2014: Symposium on Theory of Computing, Optimal CUR matrix decompositions, 353-362, (2014) · Zbl 1315.65042 |
| [9] | Clarkson, K.; Woodruff, D., STOC 2009: 41st Annual ACM Symposium on Theory of Computing, Numerical linear algebra in the streaming model, 205-214, (2009) · Zbl 1304.65138 |
| [10] | Clarkson, K.; Woodruff, D., STOC 2013: Symposium on Theory of Computing Conference, Low rank approximation and regression in input sparsity time, 81-90, (2013) · Zbl 1293.65069 |
| [11] | Cohen, M., SODA 2016: 27th Annual ACM-SIAM Symposium on Discrete Algorithms, Nearly tight oblivious subspace embeddings by trace inequalities, 278-287, (2016) · Zbl 1415.65106 |
| [12] | Cohen, M.; Lee, Y.; Musco, C.; Musco, C.; Peng, R.; Sidford, A., ITCS 2015: Conference on Innovations in Theoretical Computer Science, Uniform sampling for matrix approximation, 181-190, (2015) · Zbl 1365.65108 |
| [13] | Cohen, M.; Musco, C.; Musco, C., SODA 2017: 27th Annual ACM-SIAM Symposium on Discrete Algorithms, Ridge leverage scores for low-rank approximation, 1758-1777, (2017) · Zbl 1410.68399 |
| [14] | Dasgupta, A.; Kumar, R.; Sarlós, T., STOC 2010: 42nd ACM Symposium on Theory of Computing, A sparse Johnson-Lindenstrauss transform, 341-350, (2010) · Zbl 1293.68140 |
| [15] | Dasgupta, S.; Gupta, A., An elementary proof of a theorem of Johnson and Lindenstrauss, Random Struct. Alg., 22, 60-65, (2003) · Zbl 1018.51010 · doi:10.1002/rsa.10073 |
| [16] | Deshpande, A.; Rademacher, L., FOCS 2010: 51th Annual IEEE Symposium on Foundations of Computer Science, Efficient volume sampling for row/column subset selection, 329-338, (2010) · doi:10.1109/FOCS.2010.38 |
| [17] | Deshpande, A.; Vempala, S., APPROX-RANDOM 2006, Adaptive sampling and fast low-rank matrix approximation, 292-303, (2006), Springer · Zbl 1155.68575 |
| [18] | Deshpande, A.; Rademacher, L.; Vempala, S.; Wang, G., Matrix approximation and projective clustering via volume sampling, Theory of Computing, 2, 225-247, (2006) · Zbl 1213.68702 · doi:10.4086/toc.2006.v002a012 |
| [19] | Drineas, P.; Kannan, R.; Mahoney, M., Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix, SIAM J. Comput., 36, 158-183, (2006) · Zbl 1111.68148 · doi:10.1137/S0097539704442696 |
| [20] | Drineas, P.; Magdon-Ismail, M.; Mahoney, M.; Woodruff, D., Fast approximation of matrix coherence and statistical leverage, J. Mach. Learn. Res., 13, 3475-3506, (2012) · Zbl 1437.65030 |
| [21] | Drineas, P.; Mahoney, M.; Muthukrishnan, S., Relative-error CUR matrix decompositions, SIAM J. Matrix Anal. Appl., 30, 844-881, (2008) · Zbl 1183.68738 · doi:10.1137/07070471X |
| [22] | Freedman, D., On tail probabilities for martingales, Ann. Probab., 3, 100-118, (1975) · Zbl 0313.60037 · doi:10.1214/aop/1176996452 |
| [23] | Frieze, A.; Kannan, R.; Vempala, S., FOCS 1998: 39th Annual Symposium on Foundations of Computer Science, Fast Monte-Carlo algorithms for finding low-rank approximations, 370-378, (1998) |
| [24] | Frieze, A.; Kannan, R.; Vempala, S., Fast Monte-Carlo algorithms for finding low-rank approximations, J. Assoc. Comput. Mach., 51, 1025-1041, (2004) · Zbl 1125.65005 · doi:10.1145/1039488.1039494 |
| [25] | Golub, G.; Van Loan, C., Matrix Computations, pp., (1996), Johns Hopkins University Press · Zbl 0865.65009 |
| [26] | Goreinov, S.; Tyrtyshnikov, E., The maximum-volume concept in approximation by low-rank matrices, Contemp. Math., 280, 47-51, (2001) · Zbl 1003.15025 · doi:10.1090/conm/280/4620 |
| [27] | Goreinov, S.; Tyrtyshnikov, E.; Zamarashkin, N., A theory of pseudoskeleton approximations, Linear Algebra Appl., 261, 1-21, (1997) · Zbl 0877.65021 · doi:10.1016/S0024-3795(96)00301-1 |
| [28] | Halko, N.; Martinsson, P.; Tropp, J., Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review, 53, 217-288, (2011) · Zbl 1269.65043 · doi:10.1137/090771806 |
| [29] | Hillar, C.; Lim, L., Most tensor problems are NP-hard, J. Assoc. Comput. Mach., 60, pp., (2013) · Zbl 1281.68126 |
| [30] | Horn, R.; Johnson, C., Matrix Analysis, pp., (2012), Cambridge University Press · doi:10.1017/CBO9781139020411 |
| [31] | Indyk, P.; Motwani, R., STOC 1998: 30th Annual ACM Symposium on Theory of Computing, Approximate nearest neighbors: Towards removing the curse of dimensionality, 604-613, (1998) · Zbl 1029.68541 |
| [32] | Kane, D.; Nelson, J., Sparser Johnson-Lindenstrauss transforms, J. Assoc. Comput. Mach., 61, pp., (2014) · Zbl 1295.68134 |
| [33] | Kannan, R.; Vempala, S., Spectral algorithms, Found. Trends Theoret. Comput. Sci., 4, 157-288, (2009) · Zbl 1191.68852 · doi:10.1561/0400000025 |
| [34] | Lee, Y.; Sun, H., FOCS 2015: IEEE 56th Annual Symposium on Foundations of Computer Science, Constructing linear-sized spectral sparsification in almost-linear time, 250-269, (2015) · doi:10.1109/FOCS.2015.24 |
| [35] | Li, M.; Miller, G.; Peng, R., FOCS 2013: 54th Annual IEEE Symposium on Foundations of Computer Science, Iterative row sampling, 127-136, (2013) · doi:10.1109/FOCS.2013.22 |
| [36] | Mahoney, M., Randomized algorithms for matrices and data, Found. Trends Mach. Learning, 3, 123-224, (2011) · Zbl 1232.68173 |
| [37] | Meng, X.; Mahoney, M., STOC 2013: Symposium on Theory of Computing Conference, Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression, 91-100, (2013) · Zbl 1293.68150 |
| [38] | Nelson, J.; Nguyên, H., FOCS 2013: IEEE 54th Annual Symposium on Foundations of Computer Science, OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, 117-126, (2013) · doi:10.1109/FOCS.2013.21 |
| [39] | Pisier, G., The Volume of Convex Bodies and Banach Space Geometry, pp., (1989), Cambridge University Press · Zbl 0698.46008 · doi:10.1017/CBO9780511662454 |
| [40] | Rudelson, M.; Vershynin, R., Sampling from large matrices: an approach through geometric functional analysis, J. Assoc. Comput. Mach., 54, pp., (2007) · Zbl 1326.68333 · doi:10.1145/1255443.1255449 |
| [41] | Sarlós, T., FOCS 2006: 47th Annual IEEE Symposium on Foundations of Computer Science, Improved approximation algorithms for large matrices via random projections, 143-152, (2006) · doi:10.1109/FOCS.2006.37 |
| [42] | Spielman, D.; Srivastava, N., Graph sparsification by effective resistances, SIAM J. Comput., 40, 1913-1926, (2011) · Zbl 1237.05129 · doi:10.1137/080734029 |
| [43] | Stewart, G., Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix, Numer. Math., 83, 313-323, (1999) · Zbl 0957.65031 · doi:10.1007/s002110050451 |
| [44] | Stewart, G., pp. |
| [45] | Tropp, J., Improved analysis of the subsampled randomized Hadamard transform, Adv. Adapt. Data Anal., 3, 115-126, (2011) · Zbl 1232.15029 · doi:10.1142/S1793536911000787 |
| [46] | Vempala, S., The Random Projection Method, pp., (2004), DIMACS/AMS · Zbl 1058.68063 |
| [47] | Vishnoi, N., \( \text{Lx}=\text{b} \), Found. Trends Theoret. Comput. Sci., 8, 1-141, (2013) · Zbl 1280.65003 · doi:10.1561/0400000054 |
| [48] | Woodruff, D., Sketching as a tool for numerical linear algebra, Found. Trends Theoret. Comput. Sci., 10, 1-157, (2014) · Zbl 1316.65046 · doi:10.1561/0400000060 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
