INB-Lunch-Seminar

Sparsity, fast Fourier transforms, and photoacoustic imaging

Stefan Kunis, University Osnabrück and Helmholtz Zentrum München, joint work with Y. Dong, T. Görner, R. Hielscher, and I. Melzer

A straightforward discretization of high dimensional problems often leads to a serious growth in the number of degrees of freedom and thus even efficient algorithms like the fast Fourier transform (FFT) have high computational costs. Utilizing sparsity, as done e.g. in compressed sensing, allows for a severe decrease of the problem size but asks for the customization of efficient algorithms to these thinner discretizations. We discuss a sparse FFT based on the so-called butterfly approximation scheme which relies on a sequence of low rank approximations and show in which way these local approximations influence the final accuracy and arithmetic complexity of the method. The second part of the talk considers a specific application and numerical results in photoacoustic imaging. Here, the measurements can be modeled by a spherical mean value transform of the data similar to the classical Radon transform in computerized tomography. We then solve the reconstruction problem by an iterative scheme using a total variation regularizer and a spectral discretization such that computations can be realized efficiently.