  An important component of many image alignment methods is the calculation of
inner products (correlations) between an image of $n\times n$ pixels and
another image translated by some shift and rotated by some angle. For robust
alignment of an image pair, the number of considered shifts and angles is
typically high, thus the inner product calculation becomes a bottleneck.
Existing methods, based on fast Fourier transforms (FFTs), compute all such
inner products with computational complexity $\mathcal{O}(n^3 \log n)$ per
image pair, which is reduced to $\mathcal{O}(N n^2)$ if only $N$ distinct
shifts are needed. We propose to use a factorization of the translation kernel
(FTK), an optimal interpolation method which represents images in a
Fourier--Bessel basis and uses a rank-$H$ approximation of the translation
kernel via an operator singular value decomposition (SVD). Its complexity is
$\mathcal{O}(Hn(n + N))$ per image pair. We prove that $H = \mathcal{O}((W +
\log(1/\epsilon))^2)$, where $2W$ is the magnitude of the maximum desired shift
in pixels and $\epsilon$ is the desired accuracy. For fixed $W$ this leads to
an acceleration when $N$ is large, such as when sub-pixel shift grids are
considered. Finally, we present numerical results in an electron cryomicroscopy
application showing speedup factors of $3$-$10$ with respect to the state of
the art.
