  Kernel matrices, as well as weighted graphs represented by them, are
ubiquitous objects in machine learning, statistics and other related fields.
The main drawback of using kernel methods (learning and inference using kernel
matrices) is efficiency -- given $n$ input points, most kernel-based algorithms
need to materialize the full $n \times n$ kernel matrix before performing any
subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this
quadratic barrier for various problems has therefore, been a subject of
extensive research efforts.
  We break the quadratic barrier and obtain $\textit{subquadratic}$ time
algorithms for several fundamental linear-algebraic and graph processing
primitives, including approximating the top eigenvalue and eigenvector,
spectral sparsification, solving linear systems, local clustering, low-rank
approximation, arboricity estimation and counting weighted triangles. We build
on the recent Kernel Density Estimation framework, which (after preprocessing
in time subquadratic in $n$) can return estimates of row/column sums of the
kernel matrix. In particular, we develop efficient reductions from
$\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel
graphs, $\textit{simulating random walks}$ on kernel graphs, and
$\textit{importance sampling}$ on matrices to Kernel Density Estimation and
show that we can generate samples from these distributions in
$\textit{sublinear}$ (in the support of the distribution) time. Our reductions
are the central ingredient in each of our applications and we believe they may
be of independent interest. We empirically demonstrate the efficacy of our
algorithms on low-rank approximation (LRA) and spectral sparsification, where
we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over
baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral
sparsification.
