Fetching the paper…

Reading the bibliography…

2017

An $N \log N$ Parallel Fast Direct Solver for Kernel Matrices

Yu, Chenhan D., March, William B., Biros, George

Original
PDF
Post on X

Understand

Kernel matrices appear in machine learning and non-parametric statistics.

Given $N$ points in $d$ dimensions and a kernel function that requires $\mathcal{O}(d)$ work to evaluate, we present an $\mathcal{O}(dN\log N)$-work algorithm for the approximate factorization of a regularized kernel matrix, a common computational bottleneck in the training phase of a learning task.
With this factorization, solving a linear system with a kernel matrix can be done with $\mathcal{O}(N\log N)$ work.
Our algorithm only requires kernel evaluations and does not require that the kernel matrix admits an efficient global low rank approximation.

An $N \log N$ Parallel Fast Direct Solver for Kernel Matrices · Around

Built on

W. W. Hager
1989
Earlier work this paper cites.
S. M. Omohundro
1989
Earlier work this paper cites.
A. Gray and A. Moore
2001
Earlier work this paper cites.
C. Williams and M. Seeger
2001
Earlier work this paper cites.
R. Kriemann
2004
Earlier work this paper cites.
L. Wasserman
2004
Earlier work this paper cites.
D. Lee, A. Gray, and A. Moore
2006
Earlier work this paper cites.
C. E. Rasmussen and C. Williams
2006
Earlier work this paper cites.
M. Bebendorf
2008
Earlier work this paper cites.
W. Hackbusch, B. N. Khoromskij, and E. E. Tyrtyshnikov
2008
Earlier work this paper cites.
T. Hofmann, B. Schölkopf, and A. J. Smola
2008
Earlier work this paper cites.
C.-C. Chang and C.-J. Lin
2011
Earlier work this paper cites.

Similar

N. Halko, P.-G. Martinsson, and J. Tropp
2011
Cited alongside, same era.
M. Izadi Khaleghabadi et al
2012
Cited alongside, same era.
S. Ambikasaran and E. Darve
2013
Cited alongside, same era.
A. Gittens and M. Mahoney
2013
Cited alongside, same era.
M. Lichman
2013
Cited alongside, same era.
S. Wang, X. S. Li, J. Xia, Y. Situ, and M. V. De Hoop
2013
Cited alongside, same era.
S. Ambikasaran, D. Foreman-Mackey, L. Greengard, D. W. Hogg, and M. O’Neil
Original
2014
Cited alongside, same era.

Then

Z. Lu et al
Original
2014
Later among the works it cites.
Menze et al
2014
Later among the works it cites.
S. Si, C.-J. Hsieh, and I. Dhillon
2014
Later among the works it cites.
W. B. March, B. Xiao, and G. Biros
2015
Later among the works it cites.
W. B. March, B. Xiao, S. Tharakan, C. D. Yu, and G. Biros
2015
Later among the works it cites.
W. B. March, B. Xiao, C. D. Yu, and G. Biros
2015
Later among the works it cites.
F. G. Van Zee and R. A. Van De Geijn
2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

S. Balay et al

2014

Cited alongside, same era.

B. Dai, B. Xie, N. He, Y. Liang, A. Raj, M.-F. F. Balcan, and L. Song

2014

Cited alongside, same era.

C.-J. Hsieh, S. Si, and I. S. Dhillon

2014

Cited alongside, same era.

R. Kondor, N. Teneva, and V. Garg

2014

Cited alongside, same era.

R. Wang, Y. Li, M. W. Mahoney, and E. Darve

2015

Later among the works it cites.

C. D. Yu, J. Huang, W. Austin, B. Xiao, and G. Biros

2015

Later among the works it cites.

A. Sodani et al

2016

Later among the works it cites.

C. D. Yu, W. B. March, B. Xiao, and G. Biros

2016

Later among the works it cites.