Frequent Direction Algorithms for Approximate Matrix Multiplication with Applications in CCA

Abstract

Approximate matrix multiplication (AMM) becomes increasingly popular because it makes matrix computation suitable for large-scale datasets. Most previous AMM methods are based on the idea of random selection or random projection. In this paper, we propose a deterministic algorithm FD-AMM for computing an approximation to the product of two given matrices. Moreover, the algorithm works in a streaming manner. In particular, our approach is inspired by a recently proposed matrix sketching algorithm called Frequent Directions (FD). FD-AMM has stronger error bound than both random selection and random projection algorithms with respect to the same space complexity. Our approach also leads to an algorithm for computing the Canonical Correlation Analysis (CCA) of two matrices exactly in a streaming way, which takes less space than the classical method. Experimental results validate the effectiveness of our method. PDF