Date: Friday, April 15, 2022
Location: 2866 East Hall (4:00 PM to 5:00 PM)
Title: Approximate Matrix Multiplication and Laplacian Sparsifiers
Abstract: A ubiquitous operation in numerical analysis and scientific computing is matrix multiplication. However, it presents a major computational bottleneck when the matrix dimension is high, as can occur for large data size or feature dimension. A common approach in approximating the product, is to subsample row vectors from the two matrices, and sum the rank1 outer products of the sampled pairs. We propose a sampling distribution based on the leverage scores of the two matrices. We give a characterization of our approximation in terms of the Euclidean norm, analogous to that of a L_2subspace embedding. We then show connections between our algorithm; CRmultiplication, with Laplacian spectral sparsifiers, which also have numerous applications in data science, and how approximate matrix multiplication can be used to devise sparsifiers.
Files:
Speaker: Neophytos Charalambides
Institution: University of Michigan
Event Organizer:
