Deconvolution


I wish, for a project of my own, to know about how to deconvolve with

  1. High dimensional data
  2. irregularly sampled data
  3. inhomogenous (although known) convolution kernels

This is in a signal processing setting; for the (closely-related) kernel-density estimation in a statistical setting, see kernel approximation. If you don’t know your noise spectrum, see blind deconvolution.

Vanilla deconvolution

Wiener filtering! Deconvolving a signal convolved with a known kernel. Say, reconstructing the pure sound of an instrument, or, the sound of the echo in a church, from a recording made in a reverberant church. It’s not purely acoustic, though; applies to images, abstract wacky function spaces etc. The procedure is to presume your signal has been blurred by (or generally convolved with) some filter, and then to find a new filter that that undoes the effects of the previous filter, or as close as possible to that, since not all filters are invertible. In the basic case, then, this is approximately the same thing as filter inversion, although there are some fiddly cases when the kernel is noninvertible, or the inverse transform is unstable.

Linear versions are (apparently) straightforward Wiener filters (more-or-less generalized Kalman filters; although I think they are historically prior. 🏗 make this precise.) Clearly you get deconvolution-like behaviour in state filters sometimes too. I should inspect the edges of these definitions to work out the precise intersection. Markovian case?

Non-linear “deconvolutions” are AFAIK not strictly speaking deconvolution since convolution is a linear operation. Anyway, that usage seems to be in the literature. c.f. the “iterative Richardson-Lucy algorithm”.

See also compressive sensing, convolution kernels.

Deconvolution method in statistics

Curses! I thought that this weird obvious idea was actually a new idea of mine. Turns out it’s old. “Density deconvolution” is a keyword here, and it’s reasonably common in hierarchical models.

Ahmed, Ali, Benjamin Recht, and Justin Romberg. 2012. “Blind Deconvolution Using Convex Programming,” November. http://arxiv.org/abs/1211.5608.

Almeida, M. S. C., and M. A. T. Figueiredo. 2013. “Blind Image Deblurring with Unknown Boundaries Using the Alternating Direction Method of Multipliers.” In 2013 IEEE International Conference on Image Processing, 586–90. https://doi.org/10.1109/ICIP.2013.6738121.

Babacan, S. Derin, Rafael Molina, Minh N. Do, and Aggelos K. Katsaggelos. 2012. “Bayesian Blind Deconvolution with General Sparse Image Priors.” In Computer Vision – ECCV 2012, edited by Andrew Fitzgibbon, Svetlana Lazebnik, Pietro Perona, Yoichi Sato, and Cordelia Schmid, 341–55. Lecture Notes in Computer Science 7577. Springer Berlin Heidelberg. http://www.dbabacan.info/papers/Babacan_ECCV_2012.pdf.

Benichoux, Alexis, Emmanuel Vincent, and Rémi Gribonval. 2013. “A Fundamental Pitfall in Blind Deconvolution with Sparse and Shift-Invariant Priors.” In ICASSP-38th International Conference on Acoustics, Speech, and Signal Processing-2013. https://hal.inria.fr/hal-00800770/.

Berkhout, A. J., and P. R. Zaanen. 1976. “A Comparison Between Wiener Filtering, Kalman Filtering, and Deterministic Least Squares Estimation*.” Geophysical Prospecting 24 (1): 141–97. https://doi.org/10.1111/j.1365-2478.1976.tb00390.x.

Carrasco, Marine, and Jean-Pierre Florens. 2011. “Spectral Method for Deconvolving a Density.” Econometric Theory 27 (Special Issue 03): 546–81. https://doi.org/10.1017/S026646661000040X.

Carroll, Raymond J., and Peter Hall. 1988. “Optimal Rates of Convergence for Deconvolving a Density.” Journal of the American Statistical Association 83 (404): 1184–6. https://doi.org/10.1080/01621459.1988.10478718.

Cucala, Lionel. 2008. “Intensity Estimation for Spatial Point Processes Observed with Noise.” Scandinavian Journal of Statistics 35 (2): 322–34. https://doi.org/10.1111/j.1467-9469.2007.00583.x.

Delaigle, Aurore, and Peter Hall. 2015. “Methodology for Non-Parametric Deconvolution When the Error Distribution Is Unknown.” Journal of the Royal Statistical Society: Series B (Statistical Methodology), February, n/a–n/a. https://doi.org/10.1111/rssb.12109.

Delaigle, Aurore, Peter Hall, and Alexander Meister. 2008. “On Deconvolution with Repeated Measurements.” The Annals of Statistics 36 (2): 665–85. https://doi.org/10.1214/009053607000000884.

Delaigle, Aurore, and Alexander Meister. 2008. “Density Estimation with Heteroscedastic Error.” Bernoulli 14 (2): 562–79. http://www.maths.bristol.ac.uk/research/stats/reports/2005/0523.pdf.

Dokmanić, Ivan, Reza Parhizkar, Andreas Walther, Yue M. Lu, and Martin Vetterli. 2013. “Acoustic Echoes Reveal Room Shape.” Proceedings of the National Academy of Sciences 110 (30): 12186–91. https://doi.org/10.1073/pnas.1221464110.

Efron, Bradley. 2014. “The Bayes Deconvolution Problem.” http://statweb.stanford.edu/~ckirby/brad/papers/2014BayesDeconvolutionProblem.pdf.

Fan, Jianqing. 1991. “On the Optimal Rates of Convergence for Nonparametric Deconvolution Problems.” The Annals of Statistics 19 (3): 1257–72. https://doi.org/10.1214/aos/1176348248.

———. 1992. “Deconvolution with Supersmooth Distributions.” Canadian Journal of Statistics 20 (2): 155–69. https://doi.org/10.2307/3315465.

Hall, Peter, and Alexander Meister. 2007. “A Ridge-Parameter Approach to Deconvolution.” The Annals of Statistics 35 (4): 1535–58. https://doi.org/10.1214/009053607000000028.

Hawe, S., M. Kleinsteuber, and K. Diepold. 2013. “Analysis Operator Learning and Its Application to Image Reconstruction.” IEEE Transactions on Image Processing 22 (6): 2138–50. https://doi.org/10.1109/TIP.2013.2246175.

Hua, Yingbo, and Tapan K. Sarkar. 1990. “Matrix Pencil Method for Estimating Parameters of Exponentially Damped/Undamped Sinusoids in Noise.” IEEE Transactions on Acoustics, Speech and Signal Processing 38 (5): 814–24. https://doi.org/10.1109/29.56027.

Laird, Nan. 1978. “Nonparametric Maximum Likelihood Estimation of a Mixing Distribution.” Journal of the American Statistical Association 73 (364): 805–11. https://doi.org/10.2307/2286284.

Liu, Guangcan, Shiyu Chang, and Yi Ma. 2012. “Blind Image Deblurring by Spectral Properties of Convolution Operators,” September. http://arxiv.org/abs/1209.2082.

Mallet, A. 1986. “A Maximum Likelihood Estimation Method for Random Coefficient Regression Models.” Biometrika 73 (3): 645–56. https://doi.org/10.1093/biomet/73.3.645.

Meister, Alexander. 2008. “Deconvolution from Fourier-Oscillating Error Densities Under Decay and Smoothness Restrictions.” Inverse Problems 24 (1): 015003. https://doi.org/10.1088/0266-5611/24/1/015003.

Roy, R., and T. Kailath. 1989. “ESPRIT-Estimation of Signal Parameters via Rotational Invariance Techniques.” IEEE Transactions on Acoustics, Speech, and Signal Processing 37 (7): 984–95. https://doi.org/10.1109/29.32276.

Schuler, Christian J., Michael Hirsch, Stefan Harmeling, and Bernhard Schölkopf. 2014. “Learning to Deblur,” June. http://arxiv.org/abs/1406.7444.

Stefanski, Leonard A., and Raymond J. Carroll. 1990. “Deconvolving Kernel Density Estimators.” Statistics 21 (2): 169–84. https://doi.org/10.1080/02331889008802238.

Stockham, Jr., T. G., T. M. Cannon, and R. B. Ingebretsen. 1975. “Blind Deconvolution Through Digital Signal Processing.” Proceedings of the IEEE 63 (4): 678–92. https://doi.org/10.1109/PROC.1975.9800.

Wörmann, Julian, Simon Hawe, and Martin Kleinsteuber. 2013. “Analysis Based Blind Compressive Sensing.” IEEE Signal Processing Letters 20 (5): 491–94. https://doi.org/10.1109/LSP.2013.2252900.