2016/03/23 by Michael Kech, Kech, Michael, Felix Krahmer +1 · 1 citation
Computer Science · Engineering · Mathematics · #Algebraic Geometry (math.AG) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Mathematical Approximation and Integration #Numerical methods in inverse problems #Sparse and Compressive Sensing Techniques #cs.IT #math.AG #math.IT
paper · pdf · doi:10.48550/arxiv.1603.07316
arxiv created 2016/03/23 · openalex publication_date 2016/03/23 · arxiv updated 2016/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study identifiability for bilinear inverse problems under sparsity and subspace constraints. We show that, up to a global scaling ambiguity, almost all such maps are injective on the set of pairs of sparse vectors if the number of measurements m exceeds 2(s1+s2)-2, where s1 and s2 denote the sparsity of the two input vectors, and injective on the set of pairs of vectors lying in known subspaces of dimensions n1 and n2 if m≥ 2(n1+n2)-4. We also prove that both these bounds are tight in the sense that one cannot have injectivity for a smaller number of measurements. Our proof technique draws from algebraic geometry. As an application we derive optimal identifiability conditions for the deconvolution problem, thus improving on recent work of Li et al. [1].