Compressed convolution
arXiv:1312.3948 · doi:10.1051/0004-6361/201322177
Abstract
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.
arXiv comment8 pages, 7 figures. Accepted for publication in Astronomy and Astrophysics
References in corpus (18)
- HEALPix -- a Framework for High Resolution Discretization, and Fast Analysis of Data Distributed on the Sphere
- Planck Early Results: The Planck mission
- How to make maps from CMB data without losing information
- Planck early results: first assessment of the High Frequency Instrument in-flight performance
- Singular value decomposition applied to compact binary coalescence gravitational-wave signals
- Removing point sources from CMB maps
- Fast Convolution on the Sphere
- The performance of spherical wavelets to detect non-Gaussianity in the CMB sky
- Isotropic Wavelets: a Powerful Tool to Extract Point Sources from CMB Maps
- A Map-Making Algorithm for the Planck Surveyor
- Libsharp - spherical harmonic transforms revisited
- Fast directional continuous spherical wavelet transform algorithms
- Efficient Wiener filtering without preconditioning
- Deconvolution With a Spatially-Variant PSF
- Fast directional correlation on the sphere with steerable filters
- The discriminating power of wavelets to detect non-Gaussianity in the CMB
- Optimal filters for detecting cosmic bubble collisions
- ARKCoS: Artifact-Suppressed Accelerated Radial Kernel Convolution on the Sphere