A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolution

Abstract

We study the multi-channel sparse blind deconvolution (MCS-BD) problem, whose task is to simultaneously recover a kernel $\mathbf{a}$ and multiple sparse inputs $\{{\mathbf{x}}_i{\}}_{i=1}^p$ from their circulant convolution ${\mathbf{y}}_i=\mathbf{a}⊛{\mathbf{x}}_i$ ($i=1,\cdots ,p$). We formulate the task as a nonconvex optimization problem over the sphere. Under mild statistical assumptions of the data, we prove that the vanilla Riemannian gradient descent (RGD) method, with random initializations, provably recovers both the kernel $\mathbf{a}$ and the signals $\{{\mathbf{x}}_i{\}}_{i=1}^p$ up to a signed shift ambiguity. In comparison with state-of-the-art results, our work shows significant improvements in terms of sample complexity and computational efficiency. Our theoretical results are corroborated by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods on both synthetic and real datasets.

62 pages, 6 figures; short version accepted as a spotlight paper at NeurIPS'19 (https://papers.nips.cc/paper/8656-a-nonconvex-approach-for-exact-and-efficient-multichannel-sparse-blind-deconvolution) ; A long journal version is under revision at SIIMS

Cited by in corpus (13)

• ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Blind Data Detection in Massive MIMO via ${\ell }_3$-norm Maximization over the Stiefel Manifold
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Deep Networks from the Principle of Rate Reduction
• Complete Dictionary Learning via ${\ell }_p$-norm Maximization
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Convolutional Normalization: Improving Deep Convolutional Network Robustness and Training
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Stochastic Approximation for Online Tensorial Independent Component Analysis