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

Michael Kech, Felix Krahmer

Abstract

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 et al. [1].

Introduction

In signal processing, an inverse problem involves recovering a hidden signal from its measurements. A bilinear inverse problem is a more complex variant where the measurements depend on the interaction of two unknown signals. A classic example is blind deconvolution, where an observer has the output of a system but lacks knowledge of both the original message and the system's impulse response.

The core challenge in these problems is identifiability: under what conditions can we guarantee that only one unique pair of signals could have produced the observed data? Because one can always scale one signal up and the other down without changing the bilinear product, researchers look for uniqueness "up to a global scaling factor." This paper establishes the fundamental limits for this uniqueness, determining the exact minimum number of measurements ($m$) required for recovery under sparsity and subspace constraints.

Methodology: An Algebraic Geometry Approach

To move beyond the "near-optimal" bounds of previous research, the authors utilize tools from algebraic geometry rather than relying solely on probabilistic arguments. The methodology follows three primary steps:

  1. Lifting: The bilinear problem is treated as a linear problem acting on the outer product of the two signal vectors (a rank-1 matrix). This "lifts" the problem into a higher-dimensional matrix space.
  2. Dimension Counting and Intersection Theory: The researchers model the set of "bad" measurement maps—those that fail to be injective—as an algebraic variety. By applying the intersection theorem for complex varieties, they calculate the precise dimensions of these sets.
  3. Genericity: The authors prove that for "almost all" measurement setups (in a measure-theoretic sense), injectivity holds as long as the number of measurements exceeds a specific threshold based on the signals' degrees of freedom.

Key Insights and Theoretical Bounds

The paper provides concrete, tight formulas for the minimum number of measurements $m$ required for almost all bilinear maps to be injective (up to scaling):

Sparse Signals

If the two input vectors have sparsities $s_1$ and $s_2$, the required measurements are: $$m \ge 2(s_1 + s_2) - 2$$ This is a significant refinement of previous work, which suggested $m > 2(s_1 + s_2)$ was necessary. The paper proves that $2(s_1 + s_2) - 2$ is the absolute mathematical floor.

Subspace Constraints

If the vectors are restricted to known subspaces of dimensions $n_1$ and $n_2$, the limit is: $$m \ge 2(n_1 + n_2) - 4$$ The difference between the $-2$ and $-4$ terms arises from the specific geometry of how sparse vectors (which inhabit a union of subspaces) sit within the larger space compared to fixed, singular subspaces.

Applications to Blind Deconvolution

These theoretical bounds apply directly to the blind deconvolution problem. By establishing these limits, the authors improve upon the benchmarks set by Li et al. (2015), providing the most precise conditions to date for when a deconvolution problem is inherently solvable.

Limitations and Future Work

While this work establishes the information-theoretic limits of identifiability, it leaves several avenues for practical exploration:

  • Existence vs. Construction: The results prove that almost all measurement matrices work, but they do not provide a deterministic method to construct a specific matrix guaranteed to work for all signals.
  • Stability and Noise: The focus is on the noiseless setting. In real-world applications with high noise levels, the number of measurements required for stable recovery may be significantly higher than these theoretical minimums.
  • Algorithmic Gap: Proving that a solution is unique (identifiable) is the first step; however, this paper does not provide a computationally efficient algorithm (such as a convex optimization solver) to find that solution. The gap between theoretical identifiability and algorithmic tractability remains a key area for future study.

References

[1] S. Li, K. Huang, and Y. Chi, "Identifiability of blind deconvolution under subspace constraints," 2015.

Summary updated

Abstract

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 et al. [1].
BibTeX
@article{kech2017optimal,
  author = {Michael Kech and Felix Krahmer},
  title = {{Optimal Injectivity Conditions for Bilinear Inverse Problems with Applications to Identifiability of Deconvolution Problems}},
  journal = {SIAM J. Appl. Algebra Geom.},
  year = {2017},
  url = {https://openreview.net/forum?id=NeBrM9BLZ9},
}
Figure