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

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

Authors D. Kharzeev

Publication date 30 June 2020

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

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

zbMATH Keywords

blind source separationblind deconvolutionconvex programmingBranchHull

Mathematics Subject Classification ID

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

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.

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
• Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations

Cites work

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

Cited in

(5)

• Estimation from nonlinear observations via convex programming with application to bilinear regression
• Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems
• BranchHull
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Simultaneous phase retrieval and blind deconvolution via convex programming

Describes a project that uses

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)