Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs

Abstract

We investigate the effectiveness of convex relaxation and nonconvex optimization in solving bilinear systems of equations under two different designs (i.e. a sort of random Fourier design and Gaussian design). Despite the wide applicability, the theoretical understanding about these two paradigms remains largely inadequate in the presence of random noise. The current paper makes two contributions by demonstrating that: (1) a two-stage nonconvex algorithm attains minimax-optimal accuracy within a logarithmic number of iterations. (2) convex relaxation also achieves minimax-optimal statistical accuracy vis-à-vis random noise. Both results significantly improve upon the state-of-the-art theoretical guarantees.

References in corpus (18)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Self-Calibration and Biconvex Compressive Sensing
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Sparse Signal Processing Concepts for Efficient 5G System Design
• Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Near-optimal bounds for phase synchronization
• Nonconvex Demixing From Bilinear Measurements
• 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
• Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Consistent Risk Estimation in Moderately High-Dimensional Linear Regression

Cited by in corpus (2)

• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently