Lifting for blind deconvolution in random mask imaging: identifiability and convex relaxation

DOI10.1137/141002165zbMATH Open1330.94006arXiv1501.00046OpenAlexW1953819449MaRDI QIDQ3454489FDOQ3454489

Authors: Sohail Bahmani, Justin Romberg 

Publication date: 25 November 2015

Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)

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 equation 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 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 $mulo{g}^{2}L,logfracLemu,loglogleft(N+1ight)$ where $mu$ is the emph{coherence} of the blur, $L$ is the dimension of the image, and $N$ is the number of measured samples per mask.

Full work available at URL: https://arxiv.org/abs/1501.00046

Recommendations

• Image completion and blind deconvolution: model and algorithm
• Simultaneous phase retrieval and blind deconvolution via convex programming
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• A non-iterative regularization approach to blind deconvolution
• On the convex geometry of blind deconvolution and matrix completion

zbMATH Keywords

blind deconvolutionliftingnuclear norm minimizationcoded mask imaging

Mathematics Subject Classification ID

Convex programming (90C25) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Computing methodologies for image processing (68U10) Inverse problems in linear algebra (15A29)

Cites Work

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Weak convergence and empirical processes. With applications to statistics
• Hanson-Wright inequality and sub-Gaussian concentration
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Local minima and convergence in low-rank semidefinite programming
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• A simpler approach to matrix completion
• Non-asymptotic theory of random matrices: extreme singular values
• Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
• Phase retrieval from coded diffraction patterns
• Blind Deconvolution Using Convex Programming
• A Compressive Sensing and Unmixing Scheme for Hyperspectral Data Processing
• Blind deconvolution and deblurring in image analysis
• Coded hyperspectral imaging and blind compressive sensing

Cited In (6)

• Multilinear compressive sensing and an application to convolutional linear networks
• Efficient Identification of Butterfly Sparse Matrix Factorizations
• Estimation from nonlinear observations via convex programming with application to bilinear regression
• Self-calibration and bilinear inverse problems via linear least squares
• Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements
• Non-blind and blind deconvolution under Poisson noise using fractional-order total variation

Uses Software

• SDPLR
• PSF Generator
• PhaseLift

This page was built for publication: Lifting for blind deconvolution in random mask imaging: identifiability and convex relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3454489)