Regularized Gradient Descent: A Nonconvex Recipe for Fast Joint Blind Deconvolution and Demixing

Abstract

We study the question of extracting a sequence of functions $\{{\mathbf{f}}_i,{\mathbf{g}}_i{\}}_{i=1}^s$ from observing only the sum of their convolutions, i.e., from $\mathbf{y}={\sum }_{i=1}^s{\mathbf{f}}_i\ast {\mathbf{g}}_i$. While convex optimization techniques are able to solve this joint blind deconvolution-demixing problem provably and robustly under certain conditions, for medium-size or large-size problems we need computationally faster methods without sacrificing the benefits of mathematical rigor that come with convex methods. In this paper, we present a non-convex algorithm which guarantees exact recovery under conditions that are competitive with convex optimization methods, with the additional advantage of being computationally much more efficient. Our two-step algorithm converges to the global minimum linearly and is also robust in the presence of additive noise. While the derived performance bounds are suboptimal in terms of the information-theoretic limit, numerical simulations show remarkable performance even if the number of measurements is close to the number of degrees of freedom. We discuss an application of the proposed framework in wireless communications in connection with the Internet-of-Things.

arXiv commentAccepted to Information and Inference: a Journal of the IMA

References in corpus (8)

• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Self-Calibration and Biconvex Compressive Sensing
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• The achievable performance of convex demixing
• Greed is Super: A Fast Algorithm for Super-Resolution
• Through the Haze: a Non-Convex Approach to Blind Gain Calibration for Linear Random Sensing Models
• Blind Demixing and Deconvolution at Near-Optimal Rate

Cited by in corpus (3)

• Convolutional Phase Retrieval via Gradient Descent
• Blind Demixing and Deconvolution at Near-Optimal Rate
• Painless Breakups -- Efficient Demixing of Low Rank Matrices