Timezone: »
We study fast algorithms for computing basic properties of an n x n positive semidefinite kernel matrix K corresponding to n points x1,...,xn 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.
Author Information
Arturs Backurs (TTIC)
Piotr Indyk (MIT)
Cameron Musco (UMass)
Tal Wagner (MIT)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Faster Kernel Matrix Algebra via Density Estimation »
Wed. Jul 21st 02:45 -- 02:50 PM Room
More from the Same Authors
-
2021 : Coresets for Classification – Simplified and Strengthened »
Anup Rao · Tung Mai · Cameron Musco -
2023 Oral: Fast Private Kernel Density Estimation via Locality Sensitive Quantization »
Tal Wagner · Yonatan Naamad · Nina Mishra -
2023 Poster: Fast Private Kernel Density Estimation via Locality Sensitive Quantization »
Tal Wagner · Yonatan Naamad · Nina Mishra -
2023 Poster: Data Structures for Density Estimation »
Anders Aamand · Alexandr Andoni · Justin Chen · Piotr Indyk · Shyam Narayanan · Sandeep Silwal -
2022 Poster: Streaming Algorithms for Support-Aware Histograms »
Justin Chen · Piotr Indyk · Tal Wagner -
2022 Spotlight: Streaming Algorithms for Support-Aware Histograms »
Justin Chen · Piotr Indyk · Tal Wagner -
2021 : Coresets for Classification – Simplified and Strengthened »
Tung Mai · Anup Rao · Cameron Musco -
2021 Poster: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering »
Shyam Narayanan · Sandeep Silwal · Piotr Indyk · Or Zamir -
2021 Spotlight: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering »
Shyam Narayanan · Sandeep Silwal · Piotr Indyk · Or Zamir -
2020 Poster: Efficient Intervention Design for Causal Discovery with Latents »
Raghavendra Addanki · Shiva Kasiviswanathan · Andrew McGregor · Cameron Musco -
2020 Poster: Scalable Nearest Neighbor Search for Optimal Transport »
Arturs Backurs · Yihe Dong · Piotr Indyk · Ilya Razenshteyn · Tal Wagner -
2019 Poster: Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm »
Sepideh Mahabadi · Piotr Indyk · Shayan Oveis Gharan · Alireza Rezaei -
2019 Poster: Scalable Fair Clustering »
Arturs Backurs · Piotr Indyk · Krzysztof Onak · Baruch Schieber · Ali Vakilian · Tal Wagner -
2019 Oral: Scalable Fair Clustering »
Arturs Backurs · Piotr Indyk · Krzysztof Onak · Baruch Schieber · Ali Vakilian · Tal Wagner -
2019 Oral: Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm »
Sepideh Mahabadi · Piotr Indyk · Shayan Oveis Gharan · Alireza Rezaei -
2018 Poster: Semi-Supervised Learning on Data Streams via Temporal Label Propagation »
Tal Wagner · Sudipto Guha · Shiva Kasiviswanathan · Nina Mishra -
2018 Oral: Semi-Supervised Learning on Data Streams via Temporal Label Propagation »
Tal Wagner · Sudipto Guha · Shiva Kasiviswanathan · Nina Mishra