In signal processing, it is typically assumed that the correspondence between measurements and the underlying model is perfectly known. However, real-world scenarios often involve shuffled data, flipped signs, or missing entries. This paper introduces Homomorphic Sensing, a powerful framework that unifies these chaotic scenarios and provides a theoretical and algorithmic path to recovery, even when the system is underdetermined.
Introduction
This work presents a unified framework to solve linear inverse problems where measurements have undergone an unknown linear transformation. The authors provide tight theoretical conditions for unique recovery and introduce an algorithm capable of "unlabeled compressed sensing"—recovering sparse signals even when there are fewer equations than unknowns and the data is completely out of order.
The Problem: Unlabeled and Homomorphic Sensing
Consider solving a system of linear equations $y = Ax$, but the entries of the output vector $y$ have been shuffled. This is known as unlabeled sensing (or shuffled linear regression), a common challenge in fields like record linkage, multi-target tracking, and distributed sensing.
While previous research established that one generally needs more equations than variables ($m \geq 2n$) to guarantee a unique solution for unlabeled data, this paper pushes the boundaries in two major ways:
- Generalization: It moves beyond simple permutations to Homomorphic Sensing, where the unknown transformation $T$ can be any map from a finite set $\mathcal{T}$ (e.g., sign flips in phase retrieval or data erasures).
- Sparsity: It tackles the "compressed sensing" regime. By assuming the underlying signal $x$ is sparse, the authors show that recovery is possible even in underdetermined systems ($m < n$), a scenario previously considered intractable for unlabeled data.
Theoretical Framework and Methods
The authors combine tools from algebraic geometry with iterative optimization to bridge the gap between theory and practice.
Theoretical Uniqueness
They derive two primary conditions for a set of maps $\mathcal{T}$ and a measurement matrix $A$ to guarantee a unique solution for a $k$-sparse signal:
- The Rank Constraint: The rank of the maps must be sufficiently high (at least $2k$).
- The Quasi-variety Constraint: Using the Zariski topology, they prove that for a "generic" (randomly chosen) matrix $A$, the set of ambiguous solutions has a lower dimension than the space itself, making ambiguity almost impossible.
The Algorithm: Unlabeled HTP
To solve the unlabeled compressed sensing problem, they propose an iterative algorithm inspired by Hard Thresholding Pursuit (HTP). Instead of trying to find the exact permutation (which is NP-hard), they treat the shuffling as a form of sparse error and solve a relaxed optimization: $$\min_x \|y - Ax\|_1 \text{ s.t. } \|x\|_0 \leq k$$ The use of the $\ell_1$ norm makes the algorithm robust to the "outliers" created by the unknown shuffling. The algorithm alternates between identifying the support of the signal and updating its values using an ADMM-based solver.
Experimental Validation and Results
The paper validates its findings using synthetic datasets comprising a random Gaussian matrix $A$, a $k$-sparse signal $x^*$, a $p$-sparse permutation $\Pi^*$ (where $p$ represents the number of shuffled rows), and additive Gaussian noise.
The experimental results demonstrate that the proposed algorithm is highly effective, even when the data is heavily corrupted:
- Sample Complexity: As shown in the results, the number of samples $m$ required for success grows linearly with sparsity $k$. For a signal of length $n=2000$ with $k=25$ non-zeros, the algorithm succeeds with only $m=1400$ samples—well below the $m=n$ limit of traditional linear algebra.
- Noise Robustness: The estimation error drops predictably as the Signal-to-Noise Ratio (SNR) increases, validating the "local stability" theory.
- Shuffling Tolerance: Phase transition analysis reveals that for very sparse signals ($k=5$), the algorithm can tolerate up to 45% of the data being shuffled and still achieve a reasonable estimate.
Key Insights
- The $2k$ Information Limit: Remarkably, for generic matrices, the threshold for unique recovery in unlabeled sensing is $m \geq 2k$. This is the exact same threshold as standard compressed sensing where the order is known. Shuffling doesn't fundamentally change the information limit; it just makes the computation harder.
- A Unified Framework: By framing problems like real phase retrieval (unknown signs) and missing data recovery as homomorphic sensing, the authors provide a single theoretical umbrella for diverse inverse problems.
- Local Stability: The authors prove that if a solution is unique in a noiseless world, it remains stable under small amounts of noise—a critical requirement for any practical application.
Limitations and Future Directions
- Known Sparsity: The current algorithm assumes the sparsity level $k$ is known beforehand. Future versions would need to estimate this from the data.
- The High-Sparsity Wall: While efficient for small $k$, the problem becomes significantly harder as the signal becomes less sparse or the shuffling ratio $p/m$ increases.
- Algorithmic Guarantees: While the uniqueness conditions are proven, a full theoretical proof of convergence for this specific iterative HTP algorithm remains an open challenge.
Summary updated