Large-Scale Approximate Matrix Multiplication Algorithms And Applications

With the growing popularity of personal devices and the rapid development of the Internet,it becomes much more easier for people to collect and store data.A large amount of data has been accumulated in all fields of scientific research and social life in the last few years.There-fore,how to analyze and effectively manage these data has become a common concern in both computer science and applied mathematics.Many machine learning and data management tasks can be expressed as matrix forms.However,real-world applications often involves thousands of millions of records,the time and space complexity of current machine learning techniques scales roughly quadratically with the size of data matrices,which makes many applications in-tractable as the size of matrices becomes large.Therefore,how to approximate matrices and make the data analysis techniques more accurate and scalable is a hot topic in the machine learning community.In this thesis,we discuss the problem of approximate matrix multiplication(AMM)and its applications.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 comput-ing 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 sketch-ing 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 complex-ity.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.