Approximation of integral operators using product-convolution expansions

Paul Escande (1) , Pierre Weiss (2, 3)

1 DMIA - Département de Mathématiques, Informatique, Automatique
2 ITAV - Institut des Technologies Avancées en sciences du Vivant
3 IMT - Institut de Mathématiques de Toulouse UMR5219

We consider a class of linear integral operators with impulse responses varying regularly in time or space. These operators appear in a large number of applications ranging from signal/image processing to biology. Evaluating their action on functions is a computationally intensive problem necessary for many practical problems. We analyze a technique called product-convolution expansion: the operator is locally approximated by a convolution, allowing to design fast numerical algorithms based on the fast Fourier transform. We design various types of expansions, provide their explicit rates of approximation and their complexity depending on the time varying impulse response smoothness. This analysis suggests novel wavelet based implementations of the method with numerous assets such as optimal approximation rates, low complexity and storage requirements as well as adaptivity to the kernels regularity. The proposed methods are an alternative to more standard procedures such as panel clustering, cross approximations, wavelet expansions or hierarchical matrices.

Mots clés: Integral operators; numerical complexity; structured low rank decomposition; fast Fourier transform; approximation rate; wavelet; spline

Domaines: Analyse numérique [math.NA]; Traitement des images [eess.IV]; Traitement du signal et de l'image [eess.SP]

Paul Escande, Pierre Weiss. Approximation of integral operators using product-convolution expansions. Journal of Mathematical Imaging and Vision, 2017, 58 (3), pp.333-348. ⟨10.1007/s10851-017-0714-8⟩. ⟨hal-01301235v2⟩