Faster Kernel Matrix Algebra via Density Estimation

              Arturs Backurs * 1 Piotr Indyk * 2 Cameron Musco * 3 Tal Wagner * 4

              Abstract                  et al. (2008) for an overview.
   We study fast algorithms for computing funda-           Kernel methods typically operate using a kernel matrix.
   mental properties of a positive semidefinite ker-         Given n vectors x1 , . . . , xn ∈ Rd , the kernel matrix K ∈
   nel matrix K ∈ Rn×n corresponding to n points         ...