Optimal Injectivity Conditions for Bilinear Inverse Problems with Applications to Identifiability of Deconvolution Problems

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(s_1+s_2)-2$, where $s_1$ and $s_2$ denote the sparsity of the two input vectors, and injective on the set of pairs of vectors lying in known subspaces of dimensions $n_1$ and $n_2$ if $m\geq 2(n_1+n_2)-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, Lee, and Bresler [Y. Li, K. Lee, and Y. Bresler, Identifiability and Stability in Blind Deconvolution under Minimal Assumptions, preprint, https://arxiv.org/abs/1507.01308, 2015].