Permutations Unlabeled Beyond Sampling Unknown

Ivan Dokmanic

TL;DR

This paper generalizes the "unlabeled sensing" problem, showing that an unknown signal x can be recovered from measurements y = TAx even when T is an arbitrary invertible, diagonalizable linear transformation (not just a permutation), provided the measurement matrix A has sufficiently many rows. This offers a more robust framework for signal recovery in scenarios with unknown transformations beyond simple reordering.

What Problem Does This Paper Address?

Imagine you're recording a sound field with many microphones, but you forgot to label the cables. You end up with a jumble of recordings, and you don't know which microphone captured which spatial position. This is the essence of the "unlabeled sampling problem," where we receive measurements y = ΠAx, and we know A and y, but both the original signal x and the permutation Π are unknown. This problem arises in various fields, from signal processing and robotics (SLAM) to communication systems and even cryo-electron microscopy.

A recent breakthrough showed that if A is a random Gaussian matrix with at least twice as many rows as columns (m >= 2n), we can uniquely recover x from y = ΠAx with high probability. This paper tackles a more general version of this problem: what if the "jumbling" isn't just a simple reordering (permutation) but a more complex, unknown linear transformation T? The authors ask: can we still recover x from y = TAx when T is an arbitrary invertible, diagonalizable linear transformation from a finite or countably infinite set T?

Methods

The core of the paper's contribution lies in its elegant geometric proof. Instead of relying on complex coding theory arguments used in prior work on permutations, the authors leverage vector space geometry. They analyze the intersection of the range spaces of A and TA.

The key lemma (Lemma 1) focuses on the simplest non-trivial case: T = {I, T}, where I is the identity matrix and T is a single invertible, diagonalizable transformation. The proof hinges on showing that for almost all matrices A (with m >= 2n), the intersection of the range of A and the range of TA is constrained. Specifically, if y = Ax and y = TAx, then TAx must lie in the range of A. The authors show that this condition, combined with the properties of T's eigenvalues and their multiplicities, dictates whether x can be recovered uniquely or up to a scale.

This lemma is then generalized in Theorem 2 to an arbitrary finite or countably infinite set of transformations T. The proof cleverly uses the subadditivity of measure to show that the set of "bad" matrices A (for which recovery fails) is of measure zero, meaning recovery is possible for almost all A.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Generalization Beyond Permutations: The most significant insight is that the condition m >= 2n for recovery from y = TAx holds not just for permutations but for a much broader class of invertible, diagonalizable linear transformations T. This significantly expands the applicability of unlabeled sensing theory.
  • Geometric Intuition: The proof's reliance on vector space geometry provides a powerful and intuitive understanding of why recovery is possible. The idea that random n-dimensional subspaces in 2n-dimensional space intersect only at the origin is central.
  • Eigenvalue Multiplicity is Key: The multiplicity of the eigenvalue 1 in the transformation T plays a crucial role in determining whether recovery is unique or up to a scale.
  • Necessity of m >= 2n: The paper also provides a partial converse, showing that if m < 2n, there exist scenarios (even with permutations) where recovery is not guaranteed for almost all A.

Key Results

  • Theorem 2: For a known matrix A with m >= 2n rows, and an unknown transformation T from a finite or countably infinite set of invertible, diagonalizable transformations T, an unknown signal x can be recovered from y = TAx (where T and x are unknown) either uniquely or up to a scale, for almost all matrices A.
  • Specialization to Permutations: By setting T to be the set of all m x m permutation matrices, the paper recovers the known result for unlabeled sensing with permutations, providing a simpler, geometric proof.
  • Partial Converse: For m < 2n, there exist x and transformations T1, T2 such that T1Ax = T2Az for x != z, demonstrating that the m >= 2n condition is necessary for guaranteed recovery.

Limitations and Future Work

  • Uniqueness vs. Stability/Algorithms: This paper focuses solely on the uniqueness of recovery. Stability (how sensitive the recovery is to noise) and efficient algorithms for recovery are explicitly left for future work.
  • Diagonalizable and Invertible T: The proofs rely on T being diagonalizable and invertible. The authors suggest that relaxing these assumptions (e.g., to non-invertible T with controlled nullspaces, or even nonlinear transformations) would be interesting future directions.
  • Practical Implications: While the theoretical framework is powerful, translating these results into practical algorithms for real-world applications (like those mentioned in the introduction) remains a significant challenge.

Summary updated

Abstract

A recent unlabeled sampling result by Unnikrishnan, Haghighatshoar, and Vetterli states that with probability one over Gaussian random matrices A with iid entries, any x can be uniquely recovered from an unknown permutation of y = Ax as soon as A has at least twice as many rows as columns. We show that this condition on A implies something much stronger: that an unknown vector x can be recovered from measurements y = TAx, when the unknown T belongs to an arbitrary set of invertible, diagonalizable linear transformations T. The set T can be finite or countably infinite. When it is the set of m × m permutation matrices, we have the classical unlabeled sampling problem. We show that for almost all A with at least twice as many rows as columns, all x can be recovered either uniquely, or up to a scale depending on T, and that the condition on the size of A is necessary. Our proof is based on vector space geometry. Specializing to permutations, we obtain a simplified proof of the uniqueness result of Unnikrishnan, Haghighatshoar, and Vetterli. In this letter, we are only concerned with uniqueness; stability and algorithms are left for future work.
BibTeX
@article{dokmanic2019permutations,
  author = {Ivan Dokmanic},
  title = {{Permutations Unlabeled Beyond Sampling Unknown}},
  journal = {IEEE Signal Processing Letters},
  year = {2019},
  url = {https://openreview.net/forum?id=EC8g_K2d3Y5},
}
Figure