Subspace Embeddings for the Polynomial Kernel

By Haim Avron, Huy L. Nguyen, David P. Woodruff. 2014

104 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels (2014, methodology): “It can also be shown that their feature map is an oblivious subspace embedding, and this observation provides stronger theoretical guarantees than point-wise error bounds prevalent in the feature map literature (Avron et al., 2014). By invoking a variant of Bochner’s theorem that replaces the Fourie”
Principal Component Analysis and Higher Correlations for Distributed Data (2013, methodology): “The technique for our upper bound is based on a two-stage adaptive sketching process, and has played an important role in several followup works, including CUR Matrix Factorizations of [10] and subspace embeddings for the polynomial kernel by [7].”
Kernel Pooling for Convolutional Neural Networks (2017, methodology): “There are several recently proposed work on kernel approximation with random feature projections [33, 17, 31, 2].”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “ure in A can be non-trivially exploited to further accelerate the running time of ℓ2-regression. Given that A is structured, perhaps we can run in time even faster than O(nnz(A)). This was studied in [10, 9], and we shall present the result in [10]. Perhaps one of the oldest regression problems is p”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “Avron et al. [2013a] show how to combine a fast multiplication algorithm of Pagh [2013] for applying our subspace embeddings to the polynomial kernel expansion k ( A ) of an underlying matrix A , in time that only depends on O ( nnz ( A )) rather than on nnz ( k ( A )).”