Compressed sensing with unknown sensor permutation

Valentin Emiya, Antoine Bonnefoy, Laurent Daudet, Rémi Gribonval

TL;DR

This paper tackles the challenging problem of compressed sensing when the order of sensors is unknown, a common issue in real-world applications. They introduce a novel branch-and-bound algorithm that effectively recovers the original sparse signal and the sensor permutation, outperforming traditional convex relaxation methods that often fail.

What Problem Does This Paper Address?

Compressed sensing allows us to reconstruct sparse signals from fewer measurements than traditionally required. However, this relies on knowing the measurement matrix precisely. This paper addresses a critical gap: what happens when the order of the sensors (which dictates the rows of the measurement matrix) is unknown or has been permuted? This "sensor permutation problem" is relevant in scenarios like signal transmission over channels that don't preserve order or in experimental setups with miswired sensors. The challenge lies in simultaneously identifying the correct sensor order and recovering the sparse signal, a problem that becomes computationally intractable with naive approaches.

Methods

The authors propose a branch-and-bound algorithm to solve the sensor permutation problem. This approach systematically explores the vast space of possible sensor permutations. The core idea is to:

  1. Relaxation and Lower Bounds: They start by relaxing the discrete permutation constraint to a continuous convex set (bistochastic matrices). This allows for efficient computation of lower bounds on the cost function for different subsets of permutations.
  2. Branching: The search space is divided (branched) by progressively adding constraints on specific sensor positions within the permutation matrix.
  3. Bounding and Pruning: Lower bounds are computed for each branched subset. If a subset's lower bound is worse than the best solution found so far (upper bound), that entire branch of possibilities is "pruned," significantly reducing the search space.
  4. Heuristic Splitting: A key heuristic is used to choose which sensor position to constrain next: they select the position with the largest value in the current best estimate of the permuted measurement matrix. This guides the search towards promising solutions.

This contrasts with a simpler "convex relaxation strategy" they also analyze, which involves solving a relaxed convex problem and then projecting the result back to a permutation. This simpler method, while computationally easier, is shown to be largely ineffective for this specific problem.

Datasets

The experiments in this paper use synthetic data. The dictionary matrix is generated with standard Gaussian entries, and the sparse signal matrix consists of columns with a fixed number of non-zero Gaussian components. Permutation matrices are drawn uniformly from the set of all possible permutations. No specific publicly available datasets are mentioned or used.

Key Insights and Ideas

  • The combinatorial nature of sensor permutation is the main hurdle: Simply relaxing the problem to a continuous domain and then projecting back doesn't work reliably because the projection often lands far from a valid permutation.
  • Branch-and-bound is a powerful tool for discrete optimization: By intelligently exploring the search space and pruning unpromising branches, this algorithm can overcome the combinatorial explosion of permutations.
  • Heuristics are crucial for efficiency: The choice of which constraint to add next (based on the largest element in the relaxed matrix) significantly speeds up convergence.
  • Sparsity acts as a strong regularizer: Even with an unknown permutation, the inherent sparsity of the signal helps guide the recovery process.

Key Results

  • Perfect Recovery: The proposed branch-and-bound algorithm consistently recovers the correct sensor permutation and the original sparse signal in their experiments.
  • Convex Relaxation Failure: The simpler convex relaxation strategy, while computationally cheaper, fails to identify the correct permutation in most cases, as evidenced by high error rates in their simulations.
  • Efficiency: The branch-and-bound algorithm explores only a tiny fraction of the total permutation space (e.g., 0.05% for M=10). The number of explored subproblems grows much slower than the factorial growth of the permutation space size (M!).
  • Scalability: The algorithm shows reasonable performance for moderate permutation sizes (up to M=14), with computational complexity increasing with M but remaining manageable compared to brute-force search.

Limitations and Future Work

  • Theoretical Convergence Guarantees: While the algorithm performs well in practice, the paper acknowledges that there are no theoretical guarantees on the speed of convergence for the branch-and-bound approach in the worst case.
  • Generalization of Objective Functions: The authors suggest extending the framework to other objective functions beyond L1-norm minimization, potentially including noise in the data fitting term or structured sparsity.
  • Other Discrete Problems: The branch-and-bound methodology could be applied to other discrete optimization problems in compressed sensing, such as recovering unknown sensor polarizations or identifying defective sensors.
  • Heuristic Improvements: Further research could focus on developing even more effective heuristics for branching and pruning to further enhance efficiency.
  • Early Stopping: For applications where perfect recovery is not strictly necessary, an "early stopping" mechanism could be implemented to control computational time at the cost of some accuracy.

Summary updated

Abstract

Compressed sensing is the ability to retrieve a sparse vector from a set of linear measurements. The task gets more difficult when the sensing process is not perfectly known. We address such a problem in the case where the sensors have been permuted, i.e., the order of the measurements is unknown. We propose a branch-and-bound algorithm that converges to the solution. The experimental study shows that our approach always retrieves the unknown permutation, while a simple convex relaxation strategy almost always fails. In terms of its time complexity, we show that the proposed algorithm converges quickly with respect to the combinatorial nature of the problem.
BibTeX
@inproceedings{emiya2014compressed,
  author = {Valentin Emiya and Antoine Bonnefoy and Laurent Daudet and Rémi Gribonval},
  title = {{Compressed sensing with unknown sensor permutation}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=6f1ptEgoUF7},
}
Figure