Timezone: »

 
Poster
Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix
Insu Han · Haim Avron · Jinwoo Shin

Wed Jul 15 08:00 AM -- 08:45 AM & Wed Jul 15 07:00 PM -- 07:45 PM (PDT) @
in Poster Session 22 »

This paper studies how to sketch element-wise functions of low-rank matrices. Formally, given low-rank matrix A = [Aij] and scalar non-linear function f, we aim for finding an approximated low-rank representation of the (possibly high-rank) matrix [f(Aij)]. To this end, we propose an efficient sketching-based algorithm whose complexity is significantly lower than the number of entries of A, i.e., it runs without accessing all entries of [f(Aij)] explicitly. The main idea underlying our method is to combine a polynomial approximation of f with the existing tensor sketch scheme for approximating monomials of entries of A. To balance the errors of the two approximation components in an optimal manner, we propose a novel regression formula to find polynomial coefficients given A and f. In particular, we utilize a coreset-based regression with a rigorous approximation guarantee. Finally, we demonstrate the applicability and superiority of the proposed scheme under various machine learning tasks.

Keywords: Dimensionality Reduction · Kernel Methods · Matrix/Tensor Methods · General Machine Learning Techniques

Author Information

Insu Han (KAIST)
Haim Avron (Tel Aviv University)
Jinwoo Shin (KAIST)

More from the Same Authors