Optimal sampling algorithms for block matrix multiplication

DOI10.1016/J.CAM.2023.115063arXiv2105.04940OpenAlexW4316126879MaRDI QIDQ6100583FDOQ6100583

Authors: Chengmei Niu, Hanyu Li 

Publication date: 22 June 2023

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

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.

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

zbMATH Keywords

optimal samplinga-optimal design criterionblock matrix multiplicationprobability error boundtwo step algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Approximating Matrix Multiplication for Pattern Recognition Tasks
• The restricted isometry property for random block diagonal matrices
• A refinement of the remainder in the Lyapunov theorem
• Optimal subsampling for large sample logistic regression
• Distributed subdata selection for big data via sampling-based approach
• 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 quantile regression in big data
• A multilevel Monte Carlo estimator for matrix multiplication

Cited In (2)

• A note on optimal block-scaling of matrices
• A block-randomized stochastic method with importance sampling for CP tensor decomposition

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)