A convex program for bilinear inversion of sparse vectors
We consider the bilinear inverse problem of recovering two vectors, x 2 R L and w 2 R L , from their entrywise product. We consider the case where x and w have known signs and are sparse with respect to known dictionaries of size K and N , respectively. Here, K and N may be larger than, smaller than, or equal to L. We introduce`1-BranchHull, which is a convex program posed in the natural parameter space and does not require an approximate solution or initialization in order to be stated or solved. We study the case where x and w are S 1 -and S 2 -sparse with respect to a random dictionary, with the sparse vectors satisfying an effective sparsity condition, and present a recovery guarantee that depends on the number of measurements as L ⌦(S 1 + S 2 ) log 2 (K + N ). Numerical experiments verify that the scaling constant in the theorem is not too large. One application of this problem is 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 subspace, for example that given by dominant wavelet coefficients. We also introduce a variants of`1-BranchHull for the purposes of tolerating noise and outliers, and for the purpose of recovering piecewise constant signals. We provide an ADMM implementation of these variants and show they can extract piecewise constant behavior from real images.
This paper concerns the problem of recovering two unknown signals from their entrywise product, assuming their signs are known. To constrain the problem further, the two signals are assumed to be sparse with respect to known dictionaries. The entrywise products naturally lead to hyperbola-shaped constraints. The known signs cut the space and help to restrict the feasible set to one branch of hyperbola for each product. This enables convexification of the constraint. Based on this, this paper proposes a convex formulation Eq (2) for the problem. The paper further proposes robust and total-variation extensions of the canonical formulation, and employs the ADMM to solve the resulting general formulation. On the theory side, this paper proves that (Theorem 1) when the dimension of the two vectors is slightly higher in order than the total nonzeros of the hidden sparse vectors (intuitively, the intrinsic degrees of freedom), the proposed convex formulation recovers the two unknown signals, provided the known dictionaries are iid Gaussian.   The problem considered in this paper seems new, although there is a similar prior work   -- Aghasi, Alireza, Ali Ahmed, and Paul Hand. "BranchHull: Convex bilinear inversion from the entrywise product of signals with known signs." arXiv preprint arXiv:1702.04342 (2017).   There are minor differences between the two:   1) For data model, the prior work does not assume sparsity. This causes (simple) changes of the objectives in the convex relaxations, although the constraints are exactly the same.   2) For recovery guarantee, both guarantees are near optimal and requires dimension proportional to the intrinsic degrees of freedom of the signals. The result presented in the current paper implies the prior one.   3) The proof strategies are very similar and there are differences in the technicalities though.   So while the results presented are novel, it is also incremental in view of the above points. I think it is worthwhile to clarify the technical novelty in the proof and highlight what significant changes are needed to obtain the current result.   Another concern is how relevant is the iid Gaussian assumption on the known dictionaries to practice. Thinking of application such as real-world phase retrieval, one of the dictionaries might be the partial Fourier matrix. Sec 3.2 includes a verification close to this practical situation, although the basis is random partial DCT matrix. I think more practical evaluation is needed.      Additional comments:   * Line 35: "Unlike prior studies like Ahmed et al. [2014], where the signals are assumed to live in known subspaces, ..." Ahmed et al. [2014] considers the blind convolution problem and so is considerably more different than just without the sparsity constraint. Is the target reference actually Aghasi et al 2016?    * Line 39: "Recent work on sparse BIP, specifically sparse blind deconvolution, in Lee et al. [2017] provides ..." looks confusing. Lee et al [2017] considers recovery of sparse rank-1 matrix, and at least superficially it is not about the BIP problem considered here or sparse blind deconvolution. Can the connection be stated more explicitly? Then it would start to make sense to discuss the deficiency of the previous work and hence highlight any improvement the current work can offer. Unless this can be clarified and direct comparison makes sense, I think the claim about the contribution in the next paragraph should be revised to avoid confusion.   * The bib information of Aghasi et al 2016 and Lee et al. [2017] seems problematic: the arXiv numbers should probably be switched.    * Connection to one-bit compressed sensing: as the signs of both unknown signals are known, and the known dictionaries are assumed to be "generic", i.e., Gaussian, there is a superficial connection to one-bit compressed sensing. Please comment on the connection, and discuss what happens if one approaches the problem as two one-bit compressed sensing problems.    * Proof of Lemma 1: Why one needs to multiply |y_\ell| to both sides of the inequalities above Line 340? This does not seem necessary.