Homomorphic Sensing: Sparsity and Noise

Liangzu Peng, Boshi Wang, Manolis C. TsakirisICML 2021 · OpenReview

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:

  1. 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).
  2. 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.

Performance of the algorithm on synthetic data, showing sample complexity, error distribution, noise robustness, and phase transitions.

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

Abstract

emph{Unlabeled sensing} is a recent problem encompassing many data science and engineering applications and typically formulated as solving linear equations whose right-hand side vector has undergone an unknown permutation. It was generalized to the \emph{homomorphic sensing} problem by replacing the unknown permutation with an unknown linear map from a given finite set of linear maps. In this paper we present tighter and simpler conditions for the homomorphic sensing problem to admit a unique solution. We show that this solution is locally stable under noise, while under a sparsity assumption it remains unique under less demanding conditions. Sparsity in the context of unlabeled sensing leads to the problem of \textit{unlabeled compressed sensing}, and a consequence of our general theory is the existence under mild conditions of a unique sparsest solution. On the algorithmic level, we solve unlabeled compressed sensing by an iterative algorithm validated by synthetic data experiments. Finally, under the unifying homomorphic sensing framework we connect unlabeled sensing to other important practical problems.
BibTeX
@inproceedings{peng2021homomorphic,
  author = {Liangzu Peng and Boshi Wang and Manolis C. Tsakiris},
  title = {{Homomorphic Sensing: Sparsity and Noise}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=vPIN32iyB77},
}
Figure