Composite optimization for robust rank one bilinear sensing

DOI10.1093/IMAIAI/IAAA027zbMATH Open1475.94032arXiv1901.01624OpenAlexW3093704854MaRDI QIDQ5155950FDOQ5155950

Authors: Vasileios Charisopoulos, Damek Davis, Mateo Díaz, D. Drusvyatskiy 

Publication date: 13 October 2021

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1901.01624

Recommendations

• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• On the robustness of noise-blind low-rank recovery from rank-one measurements
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• On the convex geometry of blind deconvolution and matrix completion
• Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval

zbMATH Keywords

spectralblind deconvolutionsubgradient methodGauss-Newton methodcomposite optimizationweak convexity

Mathematics Subject Classification ID

Multivariate distribution of statistics (62H10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Nonconvex programming, global optimization (90C26) Approximation algorithms (68W25)

Cited In (4)

• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• Alternating minimization for generalized rank-1 matrix sensing: sharp predictions from a random initialization
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Stochastic optimization over proximally smooth sets

This page was built for publication: Composite optimization for robust rank one bilinear sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5155950)