Optimal sampling algorithms for block matrix multiplication

DOI10.1016/J.CAM.2023.115063MaRDI QIDQ6100583zbMATH OpenOpenAlexFDO

Authors Chengmei Niu, Hanyu Li

Publication date 22 June 2023

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.04940

zbMATH Keywords

a-optimal design criterionblock matrix multiplicationoptimal samplingprobability error boundtwo step algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Abstract: In this paper, we investigate the randomized algorithms for block matrix multiplication from random sampling perspective. Based on the A-optimal design criterion, the optimal sampling probabilities and sampling block sizes are obtained. To improve the practicability of the block sizes, two modified ones with less computation cost are provided. With respect to the second one, a two step algorithm is also devised. Moreover, the probability error bounds for the proposed algorithms are given. Extensive numerical results show that our methods outperform the existing one in the literature.

Cites work

• A multilevel Monte Carlo estimator for matrix multiplication
• A refinement of the remainder in the Lyapunov theorem
• Approximating Matrix Multiplication for Pattern Recognition Tasks
• Distributed subdata selection for big data via sampling-based approach
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast monte-carlo algorithms for finding low-rank approximations
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 800961 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• Importance sampling for a Monte Carlo matrix multiplication algorithm, with application to information retrieval
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Optimal subsampling for large sample logistic regression
• Optimal subsampling for quantile regression in big data
• The restricted isometry property for random block diagonal matrices

Cited in

(4)

• A block-randomized stochastic method with importance sampling for CP tensor decomposition
• Accelerated alternating least squares for tensor wheel decomposition with applications
• Efficient algorithms for Tucker decomposition via approximate matrix multiplication
• A note on optimal block-scaling of matrices

This page was built for publication: Optimal sampling algorithms for block matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6100583)