Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
Published Web Location
https://arxiv.org/pdf/1512.07730.pdfAbstract
Suppose that we have $r$ sensors and each one intends to send a function $z_i$ (e.g. a signal or an image) to a receiver common to all $r$ sensors. During transmission, each $z_i$ gets convolved with a function $g_i$. The receiver records the function $y$, given by the sum of all these convolved signals. When and under which conditions is it possible to recover the individual signals $z_i$ and the blurring functions $g_i$ from just one received signal $y$? This challenging problem, which intertwines blind deconvolution with blind demixing, appears in a variety of applications, such as audio processing, image processing, neuroscience, spectroscopy, and astronomy. It is also expected to play a central role in connection with the future Internet-of-Things. We will prove that under reasonable and practical assumptions, it is possible to solve this otherwise highly ill-posed problem and recover the $r$ transmitted functions $z_i$ and the impulse responses $g_i$ in a robust, reliable, and efficient manner from just one single received function $y$ by solving a semidefinite program. We derive explicit bounds on the number of measurements needed for successful recovery and prove that our method is robust in presence of noise. Our theory is actually a bit pessimistic, since numerical experiments demonstrate that, quite remarkably, recovery is still possible if the number of measurements is close to the number of degrees of freedom.