LAUSR

A common task in single particle electron cryomicroscopy (cryo-EM) is the rigid alignment of images and/or volumes. In the context of images, a rigid alignment involves estimating the inner product between one image of N × N pixels and another image that has been translated by some displacement and rotated by some angle γ. In many situations the number of rotations γ considered is large (e.g. ), while the number of translations considered is much smaller (e.g. ). In these scenarios a naive algorithm requires operations to calculate the array of inner products for each image pair. This computation can be accelerated by using a Fourier–Bessel basis and the fast Fourier transform, requiring only operations per image pair. We propose a simple data driven compression algorithm to further accelerate this computation, which we refer to as the ‘radial SVD’. Our approach involves linearly recombining the different rings of the original images (expressed in polar coordinates), taking advantage of the singular value decomposition (SVD) to both compress the images and optimize a certain measure of angular discriminability. When aligning multiple images to multiple targets, the complexity of our approach is O(N(log(N)+H)) per image pair, where H is the rank of the SVD used in the compression above. A very similar strategy can be used to accelerate volume alignment, using a spherical harmonic based compression, which we will refer to as a ‘degree SVD’. The advantage gained by these approaches depends on the ratio between H and N; the smaller H is the better. In many applications H can be quite a bit smaller than N while still maintaining accuracy. We present numerical results in a cryo-EM application demonstrating that the radial and degree SVD can help save a factor of 5–10 or more for both image and volume alignment.