Blind Deconvolution Using Convex Programming

By Ali Ahmed, B. Recht, Justin K. Romberg. IEEE Transactions on Information Theory, 2012

442 citations recorded by the source corpus.

We consider the problem of recovering two unknown vectors, w and x, 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 w and x, it is linear in the rank-1 matrix formed by their outer product wx*. 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 w and x exactly when the maximum of N and K is almost on the order of L. That is, we show that if x is drawn from a random subspace of dimension N, and w is a vector in a subspace of dimension K whose basis vectors are spread out in the frequency domain, then nuclear norm minimization recovers wx* 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 L x N 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 L ≳ N + K, to within constant and log factors.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/8b29797ee87243d601289b2d2d4701dd0baf6252

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, methodology): “Because of the practical significance of the phase retrieval problem in imaging science, the community has developed methods for recovering a signal x ∈ Cn from data of the form yr = ∣⟨ar,x⟩∣2 in the special case where one samples the (square) modulus of its Fourier transform.”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, background): “In [133], it is shown that if h is restricted to have any known support of size K on {0, .”
Phase Retrieval from Coded Diffraction Patterns (2013, unknown): “Other areas where related problems appear include acoustics [12, 8], blind channel estimation in wireless communications [4, 45], interferometry [28], quantum mechanics [25, 47] and quantum information [34].”
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk (2017, methodology): “More broadly, the principled use of sparsity as a prior has led to the development of the field of matrix completion [6], breakthroughs in phase retrieval [7], [8] and blind deconvolution [9]; and is at this point routinely utilized across applied mathematics and machine learning.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Examples include low-rank matrix completion [1]–[3], phase retrieval [4], blind deconvolution and self-calibration [5], [6], robust principal component analysis [7], [8], synchronization and alignment [9]–[11], to name just a few.”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, methodology): “Before proceeding, we need to introduce the incoherence parameter [3,76], which is crucial for blind deconvolution, whose role is similar to the incoherence parameter (cf.”