This paper considers recovering @math -dimensional vectors @math , and @math from their circular convolutions @math . The vector @math is assumed to be @math -sparse in a known basis that is spread out in the Fourier domain, and each input @math is a member of a known @math -dimensional random subspace. We prove that whenever @math , the problem can be solved effectively by using only the nuclear-norm minimization as the convex relaxation, as long as the inputs are sufficiently diverse and obey @math . By "diverse inputs", we mean that the @math 's belong to different, generic subspaces. To our knowledge, this is the first theoretical result on blind deconvolution where the subspace to which @math belongs is not fixed, but needs to be determined. We discuss the result in the context of multipath channel estimation in wireless communications. Both the fading coefficients, and the delays in the channel impulse response @math are unknown. The encoder codes the @math -dimensional message vectors randomly and then transmits coded messages @math 's over a fixed channel one after the other. The decoder then discovers all of the messages and the channel response when the number of samples taken for each received message are roughly greater than @math , and the number of messages is roughly at least @math .
An important recent article from the same group settles the recovery guarantee for a regularized gradient descent algorithm for blind deconvolution, in the single-input case and with the scaling @math @cite_29 . This result, however, makes the assumption of a fixed subspace for the sparse impulse response. Note that gradient descent algorithms are expected to have much more favorable runtimes than semidefinite programming, when their basin of attraction can be established to be wide enough, as in @cite_29 .
@cite_29
2430435693
We study the question of reconstructing two signals @math and @math from their convolution @math . This problem, known as blind deconvolution , pervades many areas of science and technology, including astronomy, medical imaging, optics, and wireless communications. A key challenge of this intricate non-convex optimization problem is that it might exhibit many local minima. We present an efficient numerical algorithm that is guaranteed to recover the exact solution, when the number of measurements is (up to log-factors) slightly larger than the information-theoretical minimum, and under reasonable conditions on @math and @math . The proposed regularized gradient descent algorithm converges at a geometric rate and is provably robust in the presence of noise. To the best of our knowledge, our algorithm is the first blind deconvolution algorithm that is numerically efficient, robust against noise, and comes with rigorous recovery guarantees under certain subspace conditions. Moreover, numerical experiments do not only provide empirical verification of our theory, but they also demonstrate that our method yields excellent performance even in situations beyond our theoretical framework.