BranchHull: convex bilinear inversion from the entrywise product of signals with known signs

DOI10.1016/J.ACHA.2019.03.002zbMATH Open1448.94042arXiv1702.04342OpenAlexW2594807468MaRDI QIDQ778035FDOQ778035

Authors: D. Kharzeev 

Publication date: 30 June 2020

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: We consider the bilinear inverse problem of recovering two vectors, $x$ and $w$, in $mathbb{R}^L$ from their entrywise product. For the case where the vectors have known signs and belong to known subspaces, we introduce the convex program BranchHull, which is posed in the natural parameter space that does not require an approximate solution or initialization in order to be stated or solved. Under the structural assumptions that $x$ and $w$ are members of known $K$ and $N$ dimensional random subspaces, we present a recovery guarantee for the noiseless case and a noisy case. In the noiseless case, we prove that the BranchHull recovers $x$ and $w$ up to the inherent scaling ambiguity with high probability when $Lgg2(K+N)$. The analysis provides a precise upper bound on the coefficient for the sample complexity. In a noisy case, we show that with high probability the BranchHull is robust to small dense noise when $L=Omega(K+N)$. BranchHull is motivated by the sweep distortion removal task in dielectric imaging, where one of the signals is a nonnegative reflectivity, and the other signal lives in a known wavelet subspace. Additional potential applications are blind deconvolution and self-calibration.

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

Recommendations

• Bilinear Compressed Sensing Under Known Signs via Convex Programming
• Signal detection for inverse problems in a multidimensional framework
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• On the \(\ell_1\)-norm invariant convex \(k\)-sparse decomposition of signals
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Signal Recovery by Proximal Forward-Backward Splitting
• A block-iterative surrogate constraint splitting method for quadratic signal recovery
• Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization
• scientific article; zbMATH DE number 7370569

zbMATH Keywords

blind source separationblind deconvolutionconvex programmingBranchHull

Mathematics Subject Classification ID

Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• Non-negative matrix factorization with sparseness constraints
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• A global optimization algorithm for linear fractional and bilinear programs
• Blind Deconvolution Using Convex Programming
• A Problem in Geometric Probability.
• Self-calibration and biconvex compressive sensing
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Leveraging Diversity and Sparsity in Blind Deconvolution

Cited In (4)

• Simultaneous Phase Retrieval and Blind Deconvolution via Convex Programming
• Estimation from nonlinear observations via convex programming with application to bilinear regression
• BranchHull
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs

Uses Software

• PhaseMax
• Wirtinger Flow

This page was built for publication: BranchHull: convex bilinear inversion from the entrywise product of signals with known signs

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