Blind Deconvolution using Convex Programming

Understand

We consider the problem of recovering two unknown vectors, $\boldsymbol{w}$ and $\boldsymbol{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 $\boldsymbol{w}$ and $\boldsymbol{x}$, it is linear in the rank-1 matrix formed by their outer product $\boldsymbol{w}\boldsymbol{x}^*$.
• 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.