2021-07-01-backurs21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Faster Kernel Matrix Algebra via Density Estimation	We study fast algorithms for computing basic properties of an n x n positive semidefinite kernel matrix K corresponding to n points x_1,...,x_n in R^d. In particular, we consider the estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. These are some of the most basic problems defined over kernel matrices. We show that the sum of matrix entries can be estimated up to a multiplicative factor of 1+\epsilon in time sublinear in n and linear in d for many popular kernel functions, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and a witnessing approximate eigenvector) can be approximated to a multiplicative factor of 1+\epsilon in time sub-quadratic in n and linear in d. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	backurs21a	0	Faster Kernel Matrix Algebra via Density Estimation	500	510	500-510	500	false	Backurs, Arturs and Indyk, Piotr and Musco, Cameron and Wagner, Tal	given family Arturs Backurs given family Piotr Indyk given family Cameron Musco given family Tal Wagner	2021-07-01		Proceedings of the 38th International Conference on Machine Learning	139	inproceedings	date-parts 2021 7 1	http://proceedings.mlr.press/v139/backurs21a/backurs21a.pdf	label link Supplementary PDF http://proceedings.mlr.press/v139/backurs21a/backurs21a-supp.pdf