A note on the blind deconvolution of multiple sparse signals from unknown subspaces

This note studies the recovery of multiple sparse signals, x(n) is an element of R-L, n = 1, . . .N, from the knowledge of their convolution with an unknown point spread function h is an element of R-L. When the point spread function is known to be nonzero, vertical bar h[k]vertical bar > 0, this blind deconvolution problem can be relaxed into a linear, ill-posed inverse problem in the vector concatenating the unknown inputs x(n) together with the inverse of the filter, d is an element of R-L where d[k] = 1/h [k]. When prior information is given on the input subspaces, the resulting overdetermined linear system can be solved efficiently via least squares ( see Ling et al. 2016(1)). When no information is given on those subspaces, and the inputs are only known to be sparse, it still remains possible to recover these inputs along with the filter by considering an additional l(1) penalty. This note certifies exact recovery of both the unknown PSF and unknown sparse inputs, from the knowledge of their convolutions, as soon as the number of inputs N and the dimension of each input, L, satisfy L greater than or similar to N and N greater than or similar to T-max(2), up to log factors. Here T-max = max(n){T} and T-n, n = 1, . . . , N denote the supports of the inputs x(n). Our proof system combines the recent results on blind deconvolution via least squares to certify invertibility of the linear map encoding the convolutions, with the construction of a dual certificate following the structure first suggested in Candes et al. 2007.(2) Unlike in these papers, however, it is not possible to rely on the norm parallel to(A*(T)A(T))(-1)parallel to to certify recovery. We instead use a combination of the Schur Complement and Neumann series to compute an expression for the inverse (A*(T)A(T))(-1). Given this expression, it is possible to show that the poorly scaled blocks in (A*(T)A(T))(-1) are multiplied by the better scaled ones or vanish in the construction of the certificate. Recovery is certified with high probablility on the choice of the supports and distribution of the signs of each input x(n) on the support. The paper follows the line of previous work by Wang et al. 2016(3) where the authors guarantee recovery for subgaussian x Bernoulli inputs satisfying Ex(n) [k] is an element of [1/10,1] as soon as N greater than or similar to L. Examples of applications include seismic imaging with unknown source or marine seismic data deghosting, magnetic resonance autocalibration or multiple channel estimation in communication. Numerical experiments are provided along with a discussion on the sample complexity tightness.