Compressed convolution
  We introduce the concept of compressed convolution, a technique to convolve a
given data set with a large number of non-orthogonal kernels. In typical
applications our technique drastically reduces the effective number of
computations. The new method is applicable to convolutions with symmetric and
asymmetric kernels and can be easily controlled for an optimal trade-off
between speed and accuracy. It is based on linear compression of the collection
of kernels into a small number of coefficients in an optimal eigenbasis. The
final result can then be decompressed in constant time for each desired
convolved output. The method is fully general and suitable for a wide variety
of problems. We give explicit examples in the context of simulation challenges
for upcoming multi-kilo-detector cosmic microwave background (CMB) missions.
For a CMB experiment with O(10,000) detectors with similar beam properties, we
demonstrate that the algorithm can decrease the costs of beam convolution by
two to three orders of magnitude with negligible loss of accuracy. Likewise, it
has the potential to allow the reduction of disk space required to store signal
simulations by a similar amount. Applications in other areas of astrophysics
and beyond are optimal searches for a large number of templates in noisy data,
e.g. from a parametrized family of gravitational wave templates; or calculating
convolutions with highly overcomplete wavelet dictionaries, e.g. in methods
designed to uncover sparse signal representations.
