Composite optimization for robust blind deconvolution

Abstract

The blind deconvolution problem seeks to recover a pair of vectors from a set of rank one bilinear measurements. We consider a natural nonsmooth formulation of the problem and show that under standard statistical assumptions, its moduli of weak convexity, sharpness, and Lipschitz continuity are all dimension independent. This phenomenon persists even when up to half of the measurements are corrupted by noise. Consequently, standard algorithms, such as the subgradient and prox-linear methods, converge at a rapid dimension-independent rate when initialized within constant relative error of the solution. We then complete the paper with a new initialization strategy, complementing the local search algorithms. The initialization procedure is both provably efficient and robust to outlying measurements. Numerical experiments, on both simulated and real data, illustrate the developed theory and methods.

60 pages, 14 figures

References in corpus (6)

• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Self-Calibration and Biconvex Compressive Sensing
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• BranchHull: Convex bilinear inversion from the entrywise product of signals with known signs

Cited by in corpus (12)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Incremental Methods for Weakly Convex Optimization
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• The nonsmooth landscape of blind deconvolution
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Understanding Notions of Stationarity in Non-Smooth Optimization