Fetching the paper…
Reading the bibliography…
We propose an input sparsity time sampling algorithm that can spectrally approximate the Gram matrix corresponding to the $q$-fold column-wise tensor product of $q$ matrices using a nearly optimal number of samples, improving upon all previously known methods by poly$(q)$ factors.
Using the nystroem method to speed up kernel machines
Williams, C. and Seeger, M · 2001
Earlier work this paper cites.
Finding frequent items in data streams
Charikar, M., Chen, K., and Farach-Colton, M · 2002
Earlier work this paper cites.
An elementary proof of a theorem of johnson and lindenstrauss
Dasgupta, S. and Gupta, A · 2003
Earlier work this paper cites.
On the best constants in noncommutative khintchine-type inequalities
Haagerup, U. and Musat, M · 2007
Earlier work this paper cites.
Random features for large-scale kernel machines
Rahimi, A. and Recht, B · 2008
Earlier work this paper cites.
The fast johnson–lindenstrauss transform and approximate nearest neighbors
Ailon, N. and Chazelle, B · 2009
Earlier work this paper cites.
Random Features for Large-Scale Kernel Machines
Rahimi, A. and Recht, B · 2009
Earlier work this paper cites.
Iterative row sampling
Li, M., Miller, G. L., and Peng, R · 2013
Cited alongside, same era.
Fast and scalable polynomial kernels via explicit feature maps
Pham, N. and Pagh, R · 2013
Cited alongside, same era.
Subspace embeddings for the polynomial kernel
Avron, H., Nguyen, H., and Woodruff, D · 2014
Cited alongside, same era.
Fast randomized kernel methods with statistical guarantees
El Alaoui, A. and Mahoney, M. W · 2014
Cited alongside, same era.
Uniform sampling for matrix approximation
Cohen, M. B., Lee, Y. T., Musco, C., Musco, C., Peng, R., and Sidford, A · 2015
Cited alongside, same era.
Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees
Avron, H., Kapralov, M., Musco, C., Musco, C., Velingker, A., and Zandieh, A · 2017
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Jacot, A., Gabriel, F., and Hongler, C · 2018
Later among the works it cites.
A universal sampling method for reconstructing signals with simple fourier transforms
Avron, H., Kapralov, M., Musco, C., Musco, C., Velingker, A., and Zandieh, A · 2019
Later among the works it cites.
Tight dimensionality reduction for sketching low degree polynomial kernels
Meister, M., Sarlos, T., and Woodruff, D · 2019
Later among the works it cites.
Oblivious sketching of high-degree polynomial kernels
Ahle, T. D., Kapralov, M., Knudsen, J. B., Pagh, R., Velingker, A., Woodruff, D. P., and Zandieh, A · 2020
Later among the works it cites.
Near input sparsity time kernel embeddings via adaptive sampling
Woodruff, D. and Zandieh, A · 2020
Later among the works it cites.
Fast sketching of polynomial kernels of polynomial degree
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Recursive sampling for the nystrom method
Musco, C. and Musco, C · 2017
Cited alongside, same era.
Song, Z., Woodruff, D., Yu, Z., and Zhang, L · 2021
Later among the works it cites.
Scaling neural tangent kernels via sketching and random features
Zandieh, A., Han, I., Avron, H., Shoham, N., Kim, C., and Shin, J · 2021
Later among the works it cites.