Spectrum-Revealing Cholesky Factorization for Kernel Methods

Kernel methods represent some of the most popular machine learning tools for data analysis. Since exact kernel methods can be prohibitively expensive for large problems, reliable low-rank matrix approximations and high-performance implementations have become indispensable for practical applications...

Full description

Saved in:
Bibliographic Details
Main Authors: Jianwei Xiao, Ming Gu
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Approximation algorithms
Complexity theory
Kernel
kernel methods
low-rank approximation
Machine learning algorithms
Prediction algorithms
Reliability
Spectrum-Revealing Cholesky factorization
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Kernel methods represent some of the most popular machine learning tools for data analysis. Since exact kernel methods can be prohibitively expensive for large problems, reliable low-rank matrix approximations and high-performance implementations have become indispensable for practical applications of kernel methods. In this work, we introduce spectrum-revealing Cholesky factorization, a reliable low-rank matrix factorization, for kernel matrix approximation. We also develop an efficient and effective randomized algorithm for computing this factorization. Our numerical experiments demonstrate that this algorithm is as effective as other Cholesky factorization based kernel methods on machine learning problems, but significantly faster.
ISSN:2374-8486
DOI:10.1109/ICDM.2016.0175