[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Lifting for Blind Deconvolution in Random Mask Imaging: : Identifiability and Convex Relaxation

Published: 01 January 2015 Publication History

Abstract

In this paper we analyze the blind deconvolution of an image and an unknown blur in a coded imaging system. The measurements consist of subsampled convolution of an unknown blurring kernel with multiple random binary modulations (coded masks) of the image. To perform the deconvolution, we consider a standard lifting of the image and the blurring kernel that transforms the measurements into a set of linear equations of the matrix formed by their outer product. Any rank-one solution to this system of equations provides a valid pair of an image and a blur. We first express the necessary and sufficient conditions for the uniqueness of a rank-one solution under some additional assumptions (uniform subsampling and no limit on the number of coded masks). These conditions are a special case of a previously established result regarding identifiability in the matrix completion problem. We also characterize a low-dimensional subspace model for the blur kernel that is sufficient to guarantee identifiability, including the interesting instance of “bandpass” blur kernels. Next, assuming the bandpass model for the blur kernel, we show that the image and the blur kernel can be found using nuclear norm minimization. Our main results show that recovery is achieved (with high probability) when the number of masks is on the order of $\mu\log^{2}L\,\log\frac{Le}{\mu}\,\log\log(N+1),$ where $\mu$ is the coherence of the blur, $L$ is the dimension of the image, and $N$ is the number of measured samples per mask.

References

[1]
A. Ahmed, B. Recht, and J. Romberg, Blind deconvolution using convex programming, IEEE Trans. Inform. Theory, 60 (2014), pp. 1711--1732.
[2]
S. Burer and R. D.C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95 (2003), pp. 329--357.
[3]
S. Burer and R. D.C. Monteiro, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103 (2005), pp. 427--444.
[4]
P. Campisi and K. Egiazarian, eds., Blind Image Deconvolution, CRC Press, Boca Raton, FL, 2007.
[5]
E. Candès, X. Li, and M. Soltanolkotabi, Phase retrieval from coded diffraction patterns. arXiv:1310.3240, 2013.
[6]
E. J. Candès and Y. Plan, Matrix completion with noise, Proc. IEEE, 98 (2010), pp. 925--936.
[7]
E. J. Candès, T. Strohmer, and V. Voroninski, Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure Appl. Math., 66 (2013), pp. 1241--1274.
[8]
M. F. Duarte, M. A. Davenport, D. Takhar, J. N. Laska, T. Sun, K. F. Kelly, and R. G. Baraniuk, Single-pixel imaging via compressive sampling, IEEE Signal Process. Mag., 25 (2008), pp. 83--91.
[9]
D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57 (2011), pp. 1548--1566.
[10]
D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Quantum state tomography via compressed sensing, Phys. Rev. Lett., 105 (2010), 150401.
[11]
F. Király and R. Tomioka, A combinatorial algebraic approach for the identifiability of low-rank matrix completion, in Proceedings of the 29th International Conference on Machine Learning (ICML-12), J. Langford and J. Pineau, eds., Omnipress, New York, 2012, pp. 967--974.
[12]
H. Kirshner, F. Aguet, D. Sage, and M. Unser, 3-D PSF fitting for fluorescence microscopy: Implementation and localization application, J. Microscopy, 249 (2013), pp. 13--25; software available online at http://bigwww.epfl.ch/algorithms/psfgenerator/.
[13]
D. Kittle, K. Choi, A. Wagadarikar, and D. J. Brady, Multiframe image estimation for coded aperture snapshot spectral imagers, Appl. Optics, 49 (2010), pp. 6824--6833.
[14]
V. Koltchinskii, K. Lounici, and A. B. Tsybakov, Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, Ann. Statist., 39 (2011), pp. 2302--2329.
[15]
A. Levin, Y. Weiss, F. Durand, and W. T. Freeman, Understanding and evaluating blind deconvolution algorithms, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009, pp. 1964--1971.
[16]
A. Levin, Y. Weiss, F. Durand, and W. T. Freeman, Efficient marginal likelihood optimization in blind deconvolution, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011, pp. 2657--2664.
[17]
C. Li, T. Sun, K. F. Kelly, and Y. Zhang, A compressive sensing and unmixing scheme for hyperspectral data processing, IEEE Trans. Image Process., 21 (2012), pp. 1200--1210.
[18]
S. Oymak, A. Jalali, M. Fazel, Y. Eldar, and B. Hassibi, Simultaneously structured models with application to sparse and low-rank matrices, IEEE Trans. Inform. Theory, 61 (2015), pp. 2886--2908.
[19]
A. Rajwade, D. Kittle, T.-H. Tsai, D. Brady, and L. Carin, Coded hyperspectral imaging and blind compressive sensing, SIAM J. Imaging Sci., 6 (2013), pp. 782--812.
[20]
R. Raskar, A. Agrawal, and J. Tumblin, Coded exposure photography: Motion deblurring using fluttered shutter, in ACM SIGGRAPH 2006 Papers (SIGGRAPH'06), ACM, New York, 2006, pp. 795--804.
[21]
B. Recht, A simpler approach to matrix completion, J. Mach. Learn. Res., 12 (2011), pp. 3413--3430.
[22]
M. Rudelson and R. Vershynin, Non-asymptotic theory of random matrices: Extreme singular values, in Proceedings of the International Congress of Mathematicians, Vol. III, Hindustan Book Agency, New Delhi, 2010, pp. 1576--1602.
[23]
M. Rudelson and R. Vershynin, Hanson-Wright inequality and sub-Gaussian concentration, Electron. Commun. Probab., 18 (2013), pp. 1--9.
[24]
T. Sun and K. Kelly, Compressive sensing hyperspectral imager, in Frontiers in Optics 2009/Laser Science XXV/Fall 2009 OSA Optics & Photonics Technical Digest, Optical Society of America, Washington, DC, 2009, CTuA5.
[25]
G. Tang and B. Recht, Convex blind deconvolution with random masks, in Classical Optics 2014, OSA Technical Digest (online), Optical Society of America, Washington, DC, 2014, CW4C.1.
[26]
L. Tong and S. Perreau, Multichannel blind identification: From subspace to maximum likelihood methods, Proc. IEEE, 86 (1998), pp. 1951--1968.
[27]
A. W. van der Vaart and J. A. Wellner, Weak Convergence and Empirical Processes: With Applications to Statistics, Springer Ser. Statist., Springer-Verlag, New York, 1996.
[28]
H. Zhang, D. Wipf, and Y. Zhang, Multi-image blind deblurring using a coupled adaptive sparse prior, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013, pp. 1051--1058.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Imaging Sciences
SIAM Journal on Imaging Sciences  Volume 8, Issue 4
EISSN:1936-4954
DOI:10.1137/sjisbi.8.4
Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2015

Author Tags

  1. blind deconvolution
  2. coded mask imaging
  3. lifting
  4. nuclear norm minimization

Author Tags

  1. 15A29
  2. 6008
  3. 90C25
  4. 68U10

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 0
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media