Share Email Print
cover

Proceedings Paper • new

A note on the blind deconvolution of multiple sparse signals from unknown subspaces
Author(s): Augustin Cosse
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

This note studies the recovery of multiple sparse signals, xn ∈ ℝL, n = 1, . . . , N, from the knowledge of their convolution with an unknown point spread function h ∈ ℝL. When the point spread function is known to be nonzero, |h[k]| > 0, this blind deconvolution problem can be relaxed into a linear, ill-posed inverse problem in the vector concatenating the unknown inputs xn together with the inverse of the filter, d ∈ ℝ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. 20161). 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 l1 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 N and NT2max, up to log factors. Here Tmax = maxn{Tn} and Tn, n = 1, . . . , N denote the supports of the inputs xn. 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 Candés et al. 2007.2 Unlike in these papers, however, it is not possible to rely on the norm ||(A*TAT)−1|| to certify recovery. We instead use a combination of the Schur Complement and Neumann series to compute an expression for the inverse (A*TAT)−1. Given this expression, it is possible to show that the poorly scaled blocks in (A*TAT)−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 xn on the support. The paper follows the line of previous work by Wang et al. 20163 where the authors guarantee recovery for subgaussian × Bernoulli inputs satisfying 𝔼xn|k| ∈ [1/10, 1] as soon as NL. 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.

Paper Details

Date Published: 24 August 2017
PDF: 18 pages
Proc. SPIE 10394, Wavelets and Sparsity XVII, 103941N (24 August 2017); doi: 10.1117/12.2272836
Show Author Affiliations
Augustin Cosse, New York Univ. (United States)
Ecole Normale Supérieure, Paris (France)


Published in SPIE Proceedings Vol. 10394:
Wavelets and Sparsity XVII
Yue M. Lu; Dimitri Van De Ville; Manos Papadakis, Editor(s)

Video Presentation

A-note-on-the-blind-deconvolution-of-multiple-sparse-signals



© SPIE. Terms of Use
Back to Top