Composite optimization for robust rank one bilinear sensing

DOI10.1093/IMAIAI/IAAA027MaRDI QIDQ5155950zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(4)

• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Alternating minimization for generalized rank-1 matrix sensing: sharp predictions from a random initialization
• 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)