Fetching the paper…
Reading the bibliography…
The \emph{Fast Gaussian Transform} (FGT) enables subquadratic-time multiplication of an $n\times n$ Gaussian kernel matrix $\mathsf{K}_{i,j}= \exp ( - \| x_i - x_j \|_2^2 ) $ with an arbitrary vector $h \in \mathbb{R}^n$, where $x_1,\dots, x_n \in \mathbb{R}^d$ are a set of \emph{fixed} source points.
A class of reciprocal functions
Einar Hille · 1926
Earlier work this paper cites.
Decomposable searching problems i. static-to-dynamic transformation
Jon Louis Bentley and James B Saxe · 1980
Earlier work this paper cites.
A fast algorithm for particle simulations
Leslie Greengard and Vladimir Rokhlin · 1987
Earlier work this paper cites.
The rapid evaluation of potential fields in three dimensions
Leslie Greengard and Vladimir Rokhlin · 1988
Earlier work this paper cites.
The rapid evaluation of potential fields in particle systems
Leslie Greengard · 1988
Earlier work this paper cites.
On the evaluation of electrostatic interactions in molecular modeling
Leslie Greengard and Vladimir Rokhlin · 1989
Earlier work this paper cites.
The numerical solution of the n n -body problem
Leslie Greengard · 1990
Earlier work this paper cites.
The fast gauss transform
Leslie Greengard and John Strain · 1991
Earlier work this paper cites.
The fast multipole method for electromagnetic scattering computation
Nader Engheta, William D. Murphy, Vladimir Rokhlin, and Marius Vassiliou · 1992
Earlier work this paper cites.
A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem
Ming Gu and Stanley C. Eisenstat · 1994
Earlier work this paper cites.
Fast algorithms for classical physics
Leslie Greengard · 1994
Earlier work this paper cites.
Local polynomial modelling and its applications
Jianqing Fan and Irène Gijbels · 1996
Earlier work this paper cites.
An improved fast multipole algorithm in thre dimensions
Leslie Greengard and Vladimir Rokhlin · 1996
Earlier work this paper cites.
A short course on fast multipole methods
Rick Beatson and Leslie Greengard · 1997
Earlier work this paper cites.
Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs
James R. Driscoll, Dennis M. Healy Jr., and Daniel N. Rockmore · 1997
Earlier work this paper cites.
The fast multipole method: numerical implementation
Eric Darve · 2000
Earlier work this paper cites.
Guest editors’ introduction: The top 10 algorithms
Jack Dongarra and Francis Sullivan · 2000
Earlier work this paper cites.
A new error estimate of the fast gauss transform
Bradley John Charles Baxter and George Roussos · 2002
Earlier work this paper cites.
On spectral clustering: Analysis and an algorithm
Andrew Y Ng, Michael I Jordan, and Yair Weiss · 2002
Earlier work this paper cites.
Learning with kernels : support vector machines, regularization, optimization, and beyond
Bernhard Schölkopf and Alexander J. Smola · 2002
Earlier work this paper cites.
Learning with kernels: support vector machines, regularization, optimization, and beyond
Bernhard Schölkopf, Alexander J Smola, and Francis Bach · 2002
Earlier work this paper cites.
Improved fast gauss transform and efficient kernel density estimation
Changjiang Yang, Ramani Duraiswami, Nail A. Gumerov, and Larry Davis · 2003
Earlier work this paper cites.
Kernel methods for pattern analysis
John Shawe-Taylor and Nello Cristianini · 2004
Earlier work this paper cites.
Efficient kernel machines using the improved fast gauss transform
Changjiang Yang, Ramani Duraiswami, and Larry Davis · 2004
Earlier work this paper cites.
Dual-tree fast gauss transforms
Dongryeol Lee, Andrew Moore, and Alexander Gray · 2005
Earlier work this paper cites.
A fast solver for hss representations via sparse matrices
S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals · 2006
Earlier work this paper cites.
Kernel methods in machine learning
Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola · 2008
Cited alongside, same era.
Online metric learning and fast similarity search
Prateek Jain, Brian Kulis, Inderjit S Dhillon, and Kristen Grauman · 2008
Cited alongside, same era.
Random features for large-scale kernel machines
Ali Rahimi and Benjamin Recht · 2008
Cited alongside, same era.
Gaussian processes for machine learning (gpml) toolbox
Carl Edward Rasmussen and Hannes Nickisch · 2010
Cited alongside, same era.
Encyclopedia entry on “fast multipole methods”
Per-Gunnar Martinsson · 2012
Cited alongside, same era.
How robust are linear sketches to adaptive inputs?
Moritz Hardt and David P Woodruff · 2013
Cited alongside, same era.
Kernel density estimation through density constrained near neighbor search
Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis · 2020
Later among the works it cites.
Mongoose: A learnable lsh framework for efficient neural network training
Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re · 2020
Later among the works it cites.
Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems
Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al · 2020
Later among the works it cites.
On adaptive distance estimation
Yeshwanth Cherapanamjeri and Jelani Nelson · 2020
Later among the works it cites.
Generalized leverage score sampling for neural networks
Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu · 2020
Later among the works it cites.
Metric transforms and low rank representations of kernels
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Generalized outlier detection with flexible kernel density estimates
Erich Schubert, Arthur Zimek, and Hans Peter Kriegel · 2014
Cited alongside, same era.
Fast randomized kernel ridge regression with statistical guarantees
Ahmed Alaoui and Michael W Mahoney · 2015
Cited alongside, same era.
Uniform sampling for matrix approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Cited alongside, same era.
An o (n) direct solver for integral equations on the plane
Eduardo Corona, Per-Gunnar Martinsson, and Denis Zorin · 2015
Cited alongside, same era.
Sharper bounds for regularized data fitting
Haim Avron, Kenneth L Clarkson, and David P Woodruff · 2017
Cited alongside, same era.
Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh · 2017
Cited alongside, same era.
Josh Alman, Gary Miller, Timothy Chu, Shyam Narayanan, Mark Sellke, and Zhao Song · 2021
Later among the works it cites.
Training (overparametrized) neural networks in near-linear time
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein · 2021
Later among the works it cites.
Pixelated butterfly: Simple and efficient sparse training for neural network models
Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, and Christopher Re · 2021
Later among the works it cites.
Efficiently modeling long sequences with structured state spaces
Albert Gu, Karan Goel, and Christopher Ré · 2021
Later among the works it cites.
Sublinear least-squares value iteration via locality sensitive hashing
Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu · 2021
Later among the works it cites.
Does preprocessing help training over-parameterized neural networks?
Zhao Song, Shuo Yang, and Ruizhe Zhang · 2021
Later among the works it cites.
Training multi-layer over-parametrized neural network in subquadratic time
Zhao Song, Lichen Zhang, and Ruizhe Zhang · 2021
Later among the works it cites.
Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures
Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava · 2021
Later among the works it cites.
Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, and Danyang Zhuo · 2022
Closest in time.
Uniform approximations for randomized hadamard transforms with applications
Yeshwanth Cherapanamjeri and Jelani Nelson · 2022
Closest in time.
Training overparametrized neural networks in sublinear time
Hang Hu, Zhao Song, Omri Weinstein, and Danyang Zhuo · 2022
Closest in time.
Dynamic least-squares regression
Shunhua Jiang, Binghui Peng, and Omri Weinstein · 2022
Closest in time.
Speeding up optimizations via data structures: Faster search, sample and maintenance
Lichen Zhang · 2022
Closest in time.
Fast attention requires bounded entries
Josh Alman and Zhao Song · 2023
Closest in time.
Subquadratic algorithms for kernel matrices via kernel density estimation
Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, and Samson Zhou · 2023
Closest in time.
Randomized and deterministic attention sparsification algorithms for over-parameterized feature dimension
Yichuan Deng, Sridhar Mahadevan, and Zhao Song · 2023
Closest in time.
An over-parameterized exponential regression
Yeqi Gao, Sridhar Mahadevan, and Zhao Song · 2023
Closest in time.
Differentially private attention computation
Yeqi Gao, Zhao Song, and Xin Yang · 2023
Closest in time.
Convergence and generalization of wide neural networks with large bias, 2023
Hongru Yang, Ziyu Jiang, Ruizhe Zhang, Zhangyang Wang, and Yingbin Liang · 2023
Closest in time.
Kdeformer: Accelerating transformers via kernel density estimation
Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi · 2023
Closest in time.