ECE Seminar Series

Title: Improved Nystrom Kernel Matrix Approximation for Large-Scale Learning: Practical and Theoretical Aspects
Speaker: Dr. Farhad Pourkamali Anaraki
Affiliation: Applied Mathematics, University of Colorado-Boulder
Day: Monday, October 2, 2017
Time: 11:00 am - 12:00 pm
Location: LSC 328-330

Abstract: The Nystrom method is a popular technique for generating fixed-rank approximations of large kernel matrices that arise in many machine learning problems. The approximation quality of the Nystrom method depends crucially on the number of selected landmark points and the selection procedure. In practice, to ensure high quality approximations, the number of landmark points is chosen to be greater than the target rank. However, the standard Nystrom method uses a sub-optimal procedure for rank reduction. This talk highlights the drawbacks of standard Nystrom in terms of poor performance and lack of theoretical guarantees. To address these issues, we present an efficient method for generating improved fixed-rank Nystrom approximations. Furthermore, we present a randomized algorithm for generating landmark points that is scalable to large high-dimensional data sets and streaming scenarios. The proposed method performs K-means clustering on low-dimensional random projections of a data set and thus leads to significant savings. Extensive numerical experiments on classification and regression tasks demonstrate the superior performance and efficiency of the proposed method compared with state-of-the-art methods.

Bio: Farhad Pourkamali-Anaraki is a postdoctoral research associate in the department of Applied Mathematics at the University of Colorado at Boulder. He received his Ph.D. in 2017 in Electrical Engineering from the University of Colorado at Boulder. He won the 2017 Gold Research Award in recognition of outstanding contribution to the department of Electrical, Computer, and Energy Engineering. His research interests are in algorithmic and theoretical aspects of large-scale data analysis, statistical signal processing, machine learning, and optimization.