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

Michael Kech, Felix Krahmer

TL;DR

This paper establishes the fundamental limits for uniquely recovering signals in bilinear inverse problems, such as blind deconvolution. By leveraging tools from algebraic geometry, the authors prove the exact minimum number of measurements required for "strong identifiability" under sparsity and subspace constraints, showing that previously known bounds were close but not quite optimal.

What Problem Does This Paper Address?

In signal processing, an inverse problem involves recovering a hidden signal from its measurements. A bilinear inverse problem is a trickier version where the measurements depend on the interaction of two unknown signals (think of a signal passing through an unknown filter). A classic example is blind deconvolution, where you have the output of a system but don't know the original message or the system's impulse response.

The core challenge is identifiability: under what conditions can we guarantee that there is only one unique pair of signals that could have produced the observed data? Because you can always double one signal and halve the other without changing the output, we look for uniqueness "up to a global scaling factor."

Previous research provided "near-optimal" bounds for how many measurements ($m$) are needed. This paper aims to close the gap and find the absolute mathematical floor for $m$ when the signals are either sparse or restricted to known low-dimensional subspaces.

Methods

The authors move away from purely probabilistic arguments and instead use algebraic geometry.

  1. Lifting: They treat the bilinear problem 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 aren't injective) as an algebraic variety. By using the intersection theorem for complex varieties, they calculate the dimensions of these sets.
  3. Genericity: They 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.

Datasets

Not discussed in the paper. This is a theoretical mathematical study focused on proving theorems and establishing fundamental information-theoretic limits. It does not use empirical datasets or training sets.

Key Insights and Ideas

  • The "Tightness" Breakthrough: The most significant insight is that the bounds provided are tight. While previous work suggested $m > 2(s_1 + s_2)$ was necessary for sparse signals, this paper proves that $m \ge 2(s_1 + s_2) - 2$ is the actual limit.
  • Subspaces vs. Sparsity: The paper reveals a subtle difference in the "cost" of constraints. For signals in fixed subspaces of dimension $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 sit within the larger space compared to fixed subspaces.
  • Strong vs. Weak Identifiability: The authors distinguish between "weak" identifiability (uniqueness for a specific signal given generic measurements) and "strong" identifiability (uniqueness for all possible signals in the model). They show that their techniques provide optimal bounds for both.

Key Results

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

  • For Sparse Signals: If the two input vectors have sparsities $s_1$ and $s_2$, you need: $$m \ge 2(s_1 + s_2) - 2$$
  • For Subspace Constraints: If the vectors lie in subspaces of dimensions $n_1$ and $n_2$, you need: $$m \ge 2(n_1 + n_2) - 4$$
  • Blind Deconvolution: These bounds apply directly to the blind deconvolution problem, improving upon the recent benchmarks set by Li et al. (2015).

Limitations and Future Work

  • Existence vs. Construction: The results are "existential" and "generic." They prove that almost all measurement matrices work, but they don't provide a way to construct a specific deterministic matrix that is guaranteed to work for all signals.
  • Stability and Noise: While the paper touches on "stable" injectivity, the primary focus is on the information-theoretic limit in a noiseless setting. Real-world applications with high noise levels might require significantly more measurements than these theoretical minimums.
  • Algorithmic Gap: The paper establishes when a solution is unique, but it doesn't provide a computationally efficient algorithm (like a convex optimization solver) to actually find that solution. Proving that a problem is identifiable is often the first step before developing the algorithms to solve it.

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, 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].
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},
}

Loading related content...

Figure