Blind Deconvolution Using Convex Programming

DOI10.1109/TIT.2013.2294644MaRDI QIDQ2986493zbMATH OpenWikidataFDO

Authors

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We consider the problem of recovering two unknown vectors, $$ and $$, of length $L$ from their circular convolution. We make the structural assumption that the two vectors are members of known subspaces, one with dimension $N$ and the other with dimension $K$. Although the observed convolution is nonlinear in both $$ and $$, it is linear in the rank-1 matrix formed by their outer product $$. This observation allows us to recast the deconvolution problem as low-rank matrix recovery problem from linear measurements, whose natural convex relaxation is a nuclear norm minimization program. We prove the effectiveness of this relaxation by showing that for "generic" signals, the program can deconvolve $$ and $$ exactly when the maximum of $N$ and $K$ is almost on the order of $L$. That is, we show that if $$ is drawn from a random subspace of dimension $N$, and $$ is a vector in a subspace of dimension $K$ whose basis vectors are "spread out" in the frequency domain, then nuclear norm minimization recovers $$ without error. We discuss this result in the context of blind channel estimation in communications. If we have a message of length $N$ which we code using a random $LimesN$ coding matrix, and the encoded message travels through an unknown linear time-invariant channel of maximum length $K$, then the receiver can recover both the channel response and the message when $LgtrsimN+K$, to within constant and log factors.

Cited in

(83)

• Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
• Painless breakups -- efficient demixing of low rank matrices
• An investigation on semi-blind deconvolution by using nonlinear programming
• Blind deconvolution when noise is symmetric: Existence and examples of solutions
• A convex variational model for learning convolutional image atoms from incomplete data
• Blind image deconvolution via Hankel based method for computing the GCD of polynomials
• Sparse power factorization: balancing peakiness and sample complexity
• Estimation from nonlinear observations via convex programming with application to bilinear regression
• On recovery guarantees for one-bit compressed sensing on manifolds
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• Proof methods for robust low-rank matrix recovery
• Solving blind ptychography effectively via linearized alternating direction method of multipliers
• An optimal statistical and computational framework for generalized tensor estimation
• On the robustness of noise-blind low-rank recovery from rank-one measurements
• Guarantees of Riemannian optimization for low rank matrix completion
• Designing a stable feedback control system for blind image deconvolution
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Blind three dimensional deconvolution via convex optimization
• Identification of affinely parameterized state-space models with unknown inputs
• Modeling and identification of uncertain-input systems
• Sensor calibration for off-the-grid spectral estimation
• Solving equations of random convex functions via anchored regression
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Non-smooth non-convex Bregman minimization: unification and new algorithms
• Parametric PSF estimation based on recursive SURE for sparse deconvolution
• Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
• Image completion and blind deconvolution: model and algorithm
• Direct blind deconvolution
• Low-rank spectral optimization via gauge duality
• Guarantees of Riemannian optimization for low rank matrix recovery
• Reconstruction methods in THz single-pixel imaging
• scientific article; zbMATH DE number 5138963 (Why is no real title available?)
• Lifting for blind deconvolution in random mask imaging: identifiability and convex relaxation
• Self-calibration and biconvex compressive sensing
• Sparse model uncertainties in compressed sensing with application to convolutions and sporadic communication
• Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
• Low rank matrix recovery from rank one measurements
• scientific article; zbMATH DE number 4047573 (Why is no real title available?)
• Constrained numerical optimization methods for blind deconvolution
• Blind Image Deblurring Using Spectral Properties of Convolution Operators
• Approximate global minimizers to pairwise interaction problems via convex relaxation
• Multichannel blind deconvolution via maximum likelihood estimator: application in neural recordings
• Self-calibration and bilinear inverse problems via linear least squares
• Structured random measurements in signal processing
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
• Multilinear compressive sensing and an application to convolutional linear networks
• Geometry and symmetry in short-and-sparse deconvolution
• L₁-Norm Regularization for Short-and-Sparse Blind Deconvolution: Point Source Separability and Region Selection
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
• Multi-target detection with application to cryo-electron microscopy
• Non-convex matrix completion and related problems via strong duality
• Simultaneous phase retrieval and blind deconvolution via convex programming
• Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness
• On representer theorems and convex regularization
• Blind deconvolution by a steepest descent algorithm on a quotient manifold
• Blind Ptychographic Phase Retrieval via Convergent Alternating Direction Method of Multipliers
• A scalable estimator of sets of integral operators
• Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems
• Compressive Blind Image Deconvolution
• Plug in estimation in high dimensional linear inverse problems a rigorous analysis
• Efficient Identification of Butterfly Sparse Matrix Factorizations
• The numerics of phase retrieval
• Gradient adaptive algorithms for contrast-based blind deconvolution
• Neural network approximation of continuous functions in high dimensions with applications to inverse problems
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Riemannian thresholding methods for row-sparse and low-rank matrix recovery
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• Guarantees of fast band restricted thresholding algorithm for low-rank matrix recovery problem
• Generalized variational framework with minimax optimization for parametric blind deconvolution
• Training adaptive reconstruction networks for blind inverse problems
• Stochastic algorithms with geometric step decay converge linearly on sharp functions
• Truncated amplitude flow with coded diffraction patterns
• Levenberg-Marquardt hard thresholding pursuit for sparse bilinear inverse problems
• Bisparse blind deconvolution through hierarchical sparse recovery
• A Kronecker approximation with a convex constrained optimization method for blind image restoration
• How robust is randomized blind deconvolution via nuclear norm minimization against adversarial noise?
• Generalized orthogonal Procrustes problem under arbitrary adversaries
• Auto-calibration and biconvex compressive sensing with applications to parallel MRI
• Recovery performance of PhaseLift for phase retrieval from coded diffraction patterns
• Blind image deconvolution through Bezoutians
• BranchHull: convex bilinear inversion from the entrywise product of signals with known signs

This page was built for publication: Blind Deconvolution Using Convex Programming

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