Dr. Brajesh Kumar Jha

Approximate Matrix Multiplication using Random Sampling Background: Approximate Matrix Multiplication (AMM) Matrix multiplication is a fundamental operation in scientific computing, machine learning, data mining, and numerical linear algebra. Given two matrices \( A \in \mathbb{R}^{n \times d} \) and \( B \in \mathbb{R}^{d \times m} \), the exact computation of \( AB \) requires \( O(ndm) \) arithmetic operations, which becomes computationally expensive when the inner dimension \( d \) is large. Approximate Matrix Multiplication (AMM) addresses this challenge by computing an approximation \( \widetilde{C} \approx AB \) that is significantly faster to obtain while maintaining provable accuracy guarantees. The key idea is to reduce the dimensionality of the problem using randomized techniques, thereby lowering computational cost and memory usage. Random Sampling of Columns and Rows (Sketching) One of the simplest and most intuitive approaches to AMM is ra...