2019/06/28 by Alireza Aghasi, Ali Ahmed, Paul Hand +1 · 5 citations
Computer Science · Engineering · Mathematics · #Algorithm #Bilinear interpolation #Combinatorics #Compressed sensing #Computer science #Constant (computer programming) #Discrete mathematics #Electrical and Bioimpedance Tomography #Geometry #Image and Signal Denoising Methods #Mathematical analysis #Mathematics #Omega #Physics #Piecewise #Regular polygon #Sparse and Compressive Sensing Techniques #cs.IT #math.IT #math.OC
paper · pdf · doi:10.1109/tsp.2020.3017929
published in IEEE Transactions on Signal Processing 68, 6366-6379 (Institute of Electrical and Electronics Engineers) · arXiv admin note: substantial text overlap with arXiv:1809.08359
arxiv created 2019/06/28 · openalex publication_date 2020/01/01 · arxiv updated 2021/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider the bilinear inverse problem of recovering two vectors, x ∈ RLand w ∈ RL, 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. Under the assumptions that x and w satisfy a comparable-effective-sparsity condition and are S1- and S2-sparse with respect to a random dictionary, we present a recovery guarantee in a noisy case. We show that ℓ1-BranchHull is robust to small dense noise with high probability if the number of measurements satisfy L ≥ Ω((S1+ S2) log2(K + N)). Numerical experiments show that the scaling constant in the theorem is not too large. We also introduce 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.