  Restoring images degraded by spatially varying blur is a problem encountered
in many disciplines such as astrophysics, computer vision or biomedical
imaging. One of the main challenges to perform this task is to design efficient
numerical algorithms to approximate integral operators.We introduce a new
method based on a sparse approximation of the blurring operator in the wavelet
domain. This method requires $\mathcal{O}\left(N \epsilon^{-d/M}\right)$
operations to provide $\epsilon$-approximations, where $N$ is the number of
pixels of a $d$-dimensional image and $M\geq 1$ is a scalar describing the
regularity of the blur kernel. In addition, we propose original methods to
define sparsity patterns when only the operators regularity is known.Numerical
experiments reveal that our algorithm provides a significant improvement
compared to standard methods based on windowed convolutions.
