  Kernel methods underpin many of the most successful approaches in data
science and statistics, and they allow representing probability measures as
elements of a reproducing kernel Hilbert space without loss of information.
Recently, the kernel Stein discrepancy (KSD), which combines Stein's method
with kernel techniques, gained considerable attention. Through the Stein
operator, KSD allows the construction of powerful goodness-of-fit tests where
it is sufficient to know the target distribution up to a multiplicative
constant. However, the typical U- and V-statistic-based KSD estimators suffer
from a quadratic runtime complexity, which hinders their application in
large-scale settings. In this work, we propose a Nystr\"om-based KSD
acceleration -- with runtime $\mathcal O\!\left(mn+m^3\right)$ for $n$ samples
and $m\ll n$ Nystr\"om points -- , show its $\sqrt{n}$-consistency under the
null with a classical sub-Gaussian assumption, and demonstrate its
applicability for goodness-of-fit testing on a suite of benchmarks.
