44. A STUDY OF LOW-RANK MATRIX APPROXIMATION METHODS

Department: Computer Science & Engineering
Faculty Advisor(s): Charles Elkan

Primary Student
Name: Aditya K Menon
Email: akmenon@ucsd.edu
Phone: 858-699-1354
Grad Year: 2012

Abstract
A low rank approximation to a matrix A is a matrix with significantly smaller rank than A, and which is very close to A according to some norm. Many practical applications involving the use of large matrices focus on low-rank approximations instead; by reducing the rank or dimensionality of the data, we reduce the complexity of analyzing the data. The singular value decomposition is one of the most popular low-rank matrix approximations. However, due to its expensive computational requirements, it has traditionally been considered intractable for practical applications involving massive data. Recent developments have tried to address this problem, with several methods proposed to approximate the decomposition with better asymptotic runtime. However, these methods provide disparate theoretical guarantees, and there has not been a systematic comparison of them. We present an empirical study of such approximation techniques on real-world datasets, with the intent of testing which method is superior. Our experiments reveal a recent projection-based approach of Sarlos to be superior in terms of accuracy and runtime, although a sampling approach of Drineas, Kannan and Mahoney also performs favourably. We also conclude that most methods do not offer any savings for sparse input data, which suggests an important direction for further research.

« Back to Posters or Search Results