Nonconvex Demixing From Bilinear Measurements

Abstract

We consider the problem of demixing a sequence of source signals from the sum of noisy bilinear measurements. It is a generalized mathematical model for blind demixing with blind deconvolution, which is prevalent across the areas of dictionary learning, image processing, and communications. However, state-of- the-art convex methods for blind demixing via semidefinite programming are computationally infeasible for large-scale problems. Although the existing nonconvex algorithms are able to address the scaling issue, they normally require proper regularization to establish optimality guarantees. The additional regularization yields tedious algorithmic parameters and pessimistic convergence rates with conservative step sizes. To address the limitations of existing methods, we thus develop a provable nonconvex demixing procedure viaWirtinger flow, much like vanilla gradient descent, to harness the benefits of regularization-free fast convergence rate with aggressive step size and computational optimality guarantees. This is achieved by exploiting the benign geometry of the blind demixing problem, thereby revealing that Wirtinger flow enforces the regularization-free iterates in the region of strong convexity and qualified level of smoothness, where the step size can be chosen aggressively.

arXiv commentThis paper has been accepted by IEEE Transactions on Signal Processing

References in corpus (7)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• On the low-rank approach for semidefinite programs arising in synchronization and community detection

Cited by in corpus (10)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Reconfigurable Intelligent Surface Empowered Downlink Non-Orthogonal Multiple Access
• Intelligent Reflecting Surface for Downlink Non-Orthogonal Multiple Access Networks
• Blind Over-the-Air Computation and Data Fusion via Provable Wirtinger Flow
• Reconfigurable Intelligent Surface Enhanced Cognitive Radio Networks
• Separable Joint Blind Deconvolution and Demixing
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Blind Demixing for Low-Latency Communication
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications
• Learning One-hidden-layer neural networks via Provable Gradient Descent with Random Initialization