The Living Thing / Notebooks :

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. TODO: 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

Dammit, 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 because of course.

Reading

AhRR12
Ahmed, A., Recht, B., & Romberg, J. (2012) Blind Deconvolution using Convex Programming. arXiv:1211.5608 [cs, Math].
AlAl08
Almeida, M. S. C., & Almeida, L. B.(2008) Blind deblurring of natural images. In IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008 (pp. 1261–1264). DOI.
AlAl10
Almeida, M. S. C., & Almeida, L. B.(2010) Blind and Semi-Blind Deblurring of Natural Images. IEEE Transactions on Image Processing, 19(1), 36–52. DOI.
AlFi13
Almeida, M. S., & Figueiredo, M. A.(2013) Blind image deblurring with unknown boundaries using the alternating direction method of multipliers. In ICIP (pp. 586–590). Citeseer
BMDK12
Babacan, S. D., Molina, R., Do, M. N., & Katsaggelos, A. K.(2012) Bayesian Blind Deconvolution with General Sparse Image Priors. In A. Fitzgibbon, S. Lazebnik, P. Perona, Y. Sato, & C. Schmid (Eds.), Computer Vision – ECCV 2012 (pp. 341–355). Springer Berlin Heidelberg
BeVG13
Benichoux, A., Vincent, E., & Gribonval, R. (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.
BPGD13
Bilen, C., Puy, G., Gribonval, R., & Daudet, L. (2013) Blind sensor calibration in sparse recovery using convex optimization. In SAMPTA-10th International Conference on Sampling Theory and Applications-2013.
BrHu00
Brooks, T. F., & Humphreys Jr, W. M.(n.d.) Extension of DAMAS Phased Array Processing for Spatial Coherence Determination (DAMAS-C). In 12th AIAA/CEAS Aeroacoustics Conference (27th AIAA Aeroacoustics Conference). American Institute of Aeronautics and Astronautics
BrHu06
Brooks, T. F., & Humphreys, W. M.(2006) A deconvolution approach for the mapping of acoustic sources (DAMAS) determined from phased microphone arrays. Journal of Sound and Vibration, 294(4–5), 856–879. DOI.
BuCo09
Butucea, C., & Comte, F. (2009) Adaptive estimation of linear functionals in the convolution model and applications. Bernoulli, 15(1), 69–98. DOI.
CaFl11
Carrasco, M., & Florens, J.-P. (2011) Spectral Method for Deconvolving a Density. Econometric Theory, 27(Special Issue 03), 546–581. DOI.
CaHa88
Carroll, R. J., & Hall, P. (1988) Optimal Rates of Convergence for Deconvolving a Density. Journal of the American Statistical Association, 83(404), 1184–1186. DOI.
Cuca08
Cucala, L. (2008) Intensity Estimation for Spatial Point Processes Observed with Noise. Scandinavian Journal of Statistics, 35(2), 322–334. DOI.
DeHa15
Delaigle, A., & Hall, P. (2015) Methodology for non-parametric deconvolution when the error distribution is unknown. Journal of the Royal Statistical Society: Series B (Statistical Methodology), n/a–n/a. DOI.
DeHM08
Delaigle, A., Hall, P., & Meister, A. (2008) On Deconvolution with Repeated Measurements. The Annals of Statistics, 36(2), 665–685. DOI.
DeMe08
Delaigle, A., & Meister, A. (2008) Density estimation with heteroscedastic error. Bernoulli, 14(2), 562–579.
DPWL13
Dokmanić, I., Parhizkar, R., Walther, A., Lu, Y. M., & Vetterli, M. (2013) Acoustic echoes reveal room shape. Proceedings of the National Academy of Sciences, 110(30), 12186–12191. DOI.
Efro14
Efron, B. (2014) The Bayes deconvolution problem.
Fan91
Fan, J. (1991) On the Optimal Rates of Convergence for Nonparametric Deconvolution Problems. The Annals of Statistics, 19(3), 1257–1272. DOI.
GrGS10
Griffa, A., Garin, N., & Sage, D. (2010) Comparison of deconvolution software in 3D microscopy: A user point of view—Part 1. GIT Imaging & Microscopy, 12(EPFL-ARTICLE-163617), 43–45.
HaMe07
Hall, P., & Meister, A. (2007) A ridge-parameter approach to deconvolution. The Annals of Statistics, 35(4), 1535–1558. DOI.
Hard13
Hardy, S. J.(2013) Direct deconvolution of radio synthesis images using L 1 minimisation. Astronomy & Astrophysics, 557, A134. DOI.
HaKD13
Hawe, S., Kleinsteuber, M., & Diepold, K. (2013) Analysis operator learning and its application to image reconstruction. IEEE Transactions on Image Processing, 22(6), 2138–2150. DOI.
HMLH07
Hom, E. F. Y., Marchis, F., Lee, T. K., Haase, S., Agard, D. A., & Sedat, J. W.(2007) AIDA: an adaptive image deconvolution algorithm with application to multi-frame and three-dimensional data. Journal of the Optical Society of America. A, Optics, Image Science, and Vision, 24(6), 1580–1600.
HuSa90
Hua, Y., & Sarkar, T. K.(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–824. DOI.
Lair78
Laird, N. (1978) Nonparametric Maximum Likelihood Estimation of a Mixing Distribution. Journal of the American Statistical Association, 73(364), 805–811. DOI.
LiCM12
Liu, G., Chang, S., & Ma, Y. (2012) Blind Image Deblurring by Spectral Properties of Convolution Operators. arXiv:1209.2082 [cs].
Mall86
Mallet, A. (1986) A maximum likelihood estimation method for random coefficient regression models. Biometrika, 73(3), 645–656. DOI.
Meis08
Meister, A. (2008) Deconvolution from Fourier-oscillating error densities under decay and smoothness restrictions. Inverse Problems, 24(1), 015003. DOI.
OrGR10
Orieux, F., Giovannelli, J.-F., & Rodet, T. (2010) Bayesian estimation of regularization and PSF parameters for Wiener-Hunt deconvolution. Journal of the Optical Society of America A, 27(7), 1593. DOI.
Penc00
Pencil, M. (n.d.) Method for Estimating Parameters of bxponentially DampedKJndamped Sinusoids in Noise.
RoKa89
Roy, R., & Kailath, T. (1989) ESPRIT-estimation of signal parameters via rotational invariance techniques. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7), 984–995. DOI.
SHHS14
Schuler, C. J., Hirsch, M., Harmeling, S., & Schölkopf, B. (2014) Learning to Deblur. arXiv:1406.7444 [cs].
StCa90
Stefanski, L. A., & Carroll, R. J.(1990) Deconvolving kernel density estimators. Statistics, 21(2), 169–184. DOI.
StCI75
Stockham, J., T. G., Cannon, T. M., & Ingebretsen, R. B.(1975) Blind deconvolution through digital signal processing. Proceedings of the IEEE, 63(4), 678–692. DOI.
WöHK13
Wörmann, J., Hawe, S., & Kleinsteuber, M. (2013) Analysis Based Blind Compressive Sensing. IEEE Signal Processing Letters, 20(5), 491–494. DOI.