/Sketching for Kronecker Product Regression and P-splines

Sketching for Kronecker Product Regression and P-splines

Huaian Diao, Zhao Song, Wen Sun and David P. Woodruff
Conference Paper, International Conference on Artificial Intelligence and Statistics (AISTATS 2018), April, 2018

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

TensorSketch is an oblivious linear sketch introduced in (Pagh, 2013) and later used in (Pham and Pagh, 2013) in the context of SVMs for polynomial kernels. It was shown in (Avron et al., 2014) that TensorSketch provides a subspace embedding, and there- fore can be used for canonical correlation analysis, low rank approximation, and princi- pal component regression for the polynomial kernel. We take TensorSketch outside of the context of polynomials kernels, and show its utility in applications in which the under- lying design matrix is a Kronecker product of smaller matrices. This allows us to solve Kronecker product regression and non-negative Kronecker product regression, as well as regularized spline regression. Our main technical result is then in extending TensorSketch to other norms. That is, TensorSketch only provides input sparsity time for Kronecker product regression with respect to the 2-norm. We show how to solve Kronecker product regression with respect to the 1-norm in time sublinear in the time required for computing the Kronecker product, as well as for more general p-norms.

BibTeX Reference
@conference{Sun-2018-103733,
author = {Huaian Diao and Zhao Song and Wen Sun and David P. Woodruff},
title = {Sketching for Kronecker Product Regression and P-splines},
booktitle = {International Conference on Artificial Intelligence and Statistics (AISTATS 2018)},
year = {2018},
month = {April},
keywords = {Tensor Sketch, Kronecker Product, Splines},
}
2018-02-07T12:29:18+00:00