Optimal sampling algorithms for block matrix multiplication. (English) Zbl 07700256
Summary: In this paper, we investigate the randomized algorithms for block matrix multiplication from random sampling perspective. Specifically, based on the A-optimal design criterion, we obtain the optimal sampling probabilities and sampling block sizes. To improve the practicability of the block sizes, two modified ones with less computation cost are provided. With respect to the second modified block size, we devise a two step algorithm. Moreover, the probability error bounds for the proposed algorithms are also given. Extensive numerical results show that our methods outperform the state-of-the-art ones given in the literature.
MSC:
| 68W20 | Randomized algorithms |
Keywords:
optimal sampling; block matrix multiplication; a-optimal design criterion; two step algorithm; probability error boundReferences:
| [1] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 1268.65037 |
| [2] | Cohen, E.; Lewis, D. D., Approximating matrix multiplication for pattern recognition tasks, J. Algorithms, 30, 2, 211-252 (1999) · Zbl 0923.68110 |
| [3] | Frieze, A.; Kannan, R.; Vempala, S., Fast Monte-Carlo algorithms for finding low-rank approximations, J. ACM, 51, 6, 1025-1041 (2004) · Zbl 1125.65005 |
| [4] | Drineas, P.; Kannan, R.; Mahoney, M. W., Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication, SIAM J. Comput., 36, 1, 132-157 (2006) · Zbl 1111.68147 |
| [5] | Wu, Y., A note on random sampling for matrix multiplication (2018), arXiv preprint arXiv:1811.11237 |
| [6] | Chang, W.-T.; Tandon, R., Random sampling for distributed coded matrix multiplication, (ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing. ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP (2019), IEEE), 8187-8191 |
| [7] | Charalambides, N.; Pilanci, M.; Hero, A. O., Approximate weighted \(C R\) coded matrix multiplication, (ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing. ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP (2021)), 5095-5099 |
| [8] | Eriksson-Bique, S.; Solbrig, M.; Stefanelli, M.; Warkentin, S.; Abbey, R.; Ipsen, I. C.F., Importance sampling for a Monte Carlo matrix multiplication algorithm, with application to information retrieval, SIAM J. Sci. Comput., 33, 4, 1689-1706 (2011) · Zbl 1228.68065 |
| [9] | Wu, Y.; Polydorides, N., A multilevel Monte Carlo estimator for matrix multiplication, SIAM J. Sci. Comput., 42, 5, A2731-A2749 (2020) · Zbl 1492.65129 |
| [10] | Cohen, M. B.; Nelson, J.; Woodruff, D. P., Optimal approximate matrix product in terms of stable rank, (Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, Vol. 55. Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, Vol. 55, ICALP 2016 (2016), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 11:1-11:14 · Zbl 1404.65032 |
| [11] | Eftekhari, A.; Yap, H. L.; Rozell, C. J.; Wakin, M. B., The restricted isometry property for random block diagonal matrices, Appl. Comput. Harmon. Anal., 38, 1, 1-31 (2015) · Zbl 1302.15046 |
| [12] | Srinivasa, R. S.; Davenport, M. A.; Romberg, J., Localized sketching for matrix multiplication and ridge regression (2020), arXiv preprint arXiv:2003.09097 |
| [13] | Wang, H.; Zhu, R.; Ma, P., Optimal subsampling for large sample logistic regression, J. Amer. Statist. Assoc., 113, 522, 829-844 (2018) · Zbl 1398.62196 |
| [14] | Ma, P.; Zhang, X.; Xing, X.; Ma, J.; Mahoney, M., Asymptotic analysis of sampling estimators for randomized numerical linear algebra algorithms, (Proceedings of the 23nd International Conference on Artificial Intelligence and Statistics, vol. 108 (2020), PMLR), 1026-1035 |
| [15] | Wang, H.; Ma, Y., Optimal subsampling for quantile regression in big data, Biometrika, 108, 1, 99-112 (2021) · Zbl 1462.62248 |
| [16] | Zhang, H.; Wang, H., Distributed subdata selection for big data via sampling-based approach, Comput. Statist. Data Anal., 153, Article 107072 pp. (2021) · Zbl 1510.62083 |
| [17] | Pukelsheim, F., Optimal Design of Experiments (1993), Wiley: Wiley New York · Zbl 0834.62068 |
| [18] | Tyurin, I., A refinement of the remainder in the Lyapunov theorem, Theory Probab. Appl., 56, 4, 693-696 (2012) · Zbl 1260.60043 |
| [19] | McDiarmid, C., On the method of bounded differences, Surv. Comb., 141, 1, 148-188 (1989) · Zbl 0712.05012 |
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.
