From Blind deconvolution to Blind Super-Resolution through convex\n programming

2017/09/26 by Augustin Cosse, Cosse, Augustin
Engineering · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Numerical methods in inverse problems #Random lasers and scattering media #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1709.09279

openalex publication_date 2017/09/26 · openalex created_date 2022/08/29 · openalex updated_date 2026/07/28

Abstract

This paper discusses the recovery of an unknown signal x\∈ \ℝ^L\nthrough the result of its convolution with an unknown filter h \∈\n\ℝ^L. This problem, also known as blind deconvolution, has been\nstudied extensively by the signal processing and applied mathematics\ncommunities, leading to a diversity of proofs and algorithms based on various\nassumptions on the filter and its input. Sparsity of this filter, or in\ncontrast, non vanishing of its Fourier transform are instances of such\nassumptions. The main result of this paper shows that blind deconvolution can\nbe solved through nuclear norm relaxation in the case of a fully unknown\nchannel, as soon as this channel is probed through a few N gtrsim \μ²_m\nK^1/2 input signals x_n = C_n m_n, n=1,\…,N, that are living in\nknown K-dimensional subspaces C_n of \ℝ^L. This result holds with\nhigh probability on the genericity of the subspaces C_n as soon as L gtrsim\nK^3/2 and N gtrsim K^1/2 up to log factors. Our proof system relies on\nthe construction of a certificate of optimality for the underlying convex\nprogram. This certificate expands as a Neumann series and is shown to satisfy\nthe conditions for the recovery of the matrix encoding the unknowns by\ncontrolling the terms in this series. An incidental consequence of the result\nof this paper, following from the lack of assumptions on the filter, is that\nnuclear norm relaxation can be extended from blind deconvolution to blind\nsuper-resolution, as soon as the unknown ideal low pass filter has a\nsufficiently large support compared to the ambient dimension L. Numerical\nexperiments supporting the theory as well as its application to blind\nsuper-resolution are provided.\n

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Leveraging Diversity and Sparsity in Blind Deconvolution
• Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion

Related

• Blind Deconvolution using Convex Programming
• Convex Sparse Blind Deconvolution
• How robust is randomized blind deconvolution via nuclear norm minimization against adversarial noise?
• Non-Convex Recovery from Phaseless Low-Resolution Blind Deconvolution Measurements using Noisy Masked Patterns
• On the convex geometry of blind deconvolution and matrix completion