The nonsmooth landscape of blind deconvolution
arXiv:1911.08526
Abstract
The blind deconvolution problem aims to recover a rank-one matrix from a set of rank-one linear measurements. Recently, Charisopulos et al. introduced a nonconvex nonsmooth formulation that can be used, in combination with an initialization procedure, to provably solve this problem under standard statistical assumptions. In practice, however, initialization is unnecessary. As we demonstrate numerically, a randomly initialized subgradient method consistently solves the problem. In pursuit of a better understanding of this phenomenon, we study the random landscape of this formulation. We characterize in closed form the landscape of the population objective and describe the approximate location of the stationary points of the sample objective. In particular, we show that the set of spurious critical points lies close to a codimension two subspace. In doing this, we develop tools for studying the landscape of a broader family of singular value functions, these results may be of independent interest.
arXiv comment25 pages, 2 figures
References in corpus (10)
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Guaranteed Matrix Completion via Non-convex Factorization
- 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
- Near-optimal bounds for phase synchronization
- Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
- Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
- Composite optimization for robust blind deconvolution
- Blind Deconvolutional Phase Retrieval via Convex Programming
- On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization