Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently

Abstract

Multi-channel sparse blind deconvolution, or convolutional sparse coding, refers to the problem of learning an unknown filter by observing its circulant convolutions with multiple input signals that are sparse. This problem finds numerous applications in signal processing, computer vision, and inverse problems. However, it is challenging to learn the filter efficiently due to the bilinear structure of the observations with the respect to the unknown filter and inputs, as well as the sparsity constraint. In this paper, we propose a novel approach based on nonconvex optimization over the sphere manifold by minimizing a smooth surrogate of the sparsity-promoting loss function. It is demonstrated that manifold gradient descent with random initializations will provably recover the filter, up to scaling and shift ambiguity, as soon as the number of observations is sufficiently large under an appropriate random data model. Numerical experiments are provided to illustrate the performance of the proposed method with comparisons to existing ones.

arXiv commentaccepted by IEEE Transactions on Information Theory

References in corpus (16)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Self-Calibration and Biconvex Compressive Sensing
• Matrix Completion has No Spurious Local Minimum
• Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization
• Global Optimality in Low-rank Matrix Optimization
• Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed l1/l2 Regularization
• Subgradient Descent Learns Orthogonal Dictionaries
• A Unified Framework for Identifiability Analysis in Bilinear Inverse Problems with Applications to Subspace and Sparsity Models
• From Symmetry to Geometry: Tractable Nonconvex Problems
• A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolution
• Composite optimization for robust blind deconvolution
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs

Cited by in corpus (2)

• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications