r-local sensing: Improved algorithm and applications

Ahmed Ali Abbasi, Abiy Tasissa, Shuchin Aeron

Abstract

The unlabeled sensing problem involves solving a noisy linear system of equations where the correspondence between measurements and sensing rows is unknown. This paper focuses on the $r$-local model, where permutations are restricted to local blocks. We propose a Proximal Alternating Minimization (PAM) algorithm that ensures convergence to a first-order stationary point. We demonstrate the algorithm's effectiveness on synthetic data, image restoration tasks, and the 1-D unassigned distance geometry problem (uDGP).

Introduction

In traditional sensing, a system is modeled as $Y = BX + W$. However, many modern applications—such as header-free communication, point cloud registration, and sampling with clock jitter—suffer from unknown data permutations. This leads to the unlabeled sensing problem: $Y = P^*BX^* + W$, where $P^*$ is an unknown permutation matrix. While previous work often assumed a "sparse" permutation model (where only a few entries are swapped), this work investigates the $r$-local model, where shuffling occurs within blocks of size $r$.

The $r$-Local Model vs. $k$-Sparse

The $r$-local model assumes $P^*$ is a block-diagonal permutation matrix. This structure is common in time-series data with local jitter. Entropy analysis suggests that $r$-local permutations represent a higher state of uncertainty than $k$-sparse models, making recovery more challenging.

Permutation models and recovery performance

As shown in Figure 1, the probability of failing to recover the correct permutation decreases as the Signal-to-Noise Ratio (SNR) increases, with the $r$-local model presenting a distinct performance profile compared to the $k$-sparse case.

The PAM Algorithm

To solve the non-convex optimization problem $\min_{P, X} \|Y - PBX\|^2$, we propose the PAM algorithm. Standard alternating minimization can easily stall in local minima. PAM introduces a proximal regularization term that penalizes the new estimate for being too far from the previous one, which mathematically guarantees that the algorithm will converge to a first-order stationary point under the Kurdyka-Łojasiewicz (KL) framework. Computationally, the $r$-local structure allows the $n \times n$ permutation estimation to be decomposed into $n/r$ independent $r \times r$ sub-problems, significantly improving efficiency.

Applications and Results

Image Restoration

The algorithm was tested on image "unscrambling" using the YALE B and MNIST datasets. Local patches of images were shuffled, and PAM was tasked with recovering the original signal.

Image restoration application

On the YALE B dataset (Figure 6), PAM achieved a Peak Signal-to-Noise Ratio (PSNR) of 28.30 dB, outperforming the state-of-the-art RLUS (Robust Local Unlabeled Sensing) algorithm, which achieved 26.43 dB.

Unassigned Distance Geometry (uDGP)

We formulated the 1-D uDGP—recovering point locations from unlabeled pairwise distances—as an unlabeled sensing problem. Despite the highly structured and deterministic nature of the resulting sensing matrix, PAM maintained low relative reconstruction error even under significant Gaussian noise.

Conclusion

The PAM algorithm provides a robust and efficient framework for $r$-local unlabeled sensing. By leveraging proximal regularization and local block structures, it achieves superior recovery performance in both synthetic and real-world applications. Future work will explore extensions to higher-dimensional distance geometry and the information-theoretic limits of $r$-local recovery.

Summary updated

Abstract

The unlabeled sensing problem is to solve a noisy linear system of equations under unknown permutation of the measurements. We study a particular case of the problem where the permutations are restricted to be r-local, i.e. the permutation matrix is block diagonal with r x r blocks. Assuming a Gaussian measurement matrix, we argue that the r-local permutation model is more challenging compared to a recent sparse permutation model. We propose a proximal alternating minimization algorithm for the general unlabeled sensing problem that provably converges to a first order stationary point. Applied to the r-local model, we show that the resulting algorithm is efficient. We validate the algorithm on synthetic and real datasets. We also formulate the 1-d unassigned distance geometry problem as an unlabeled sensing problem with a structured measurement matrix.
BibTeX
@inproceedings{abbasi2022r,
  author = {Ahmed Ali Abbasi and Abiy Tasissa and Shuchin Aeron},
  title = {{r-local sensing: Improved algorithm and applications}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  url = {https://openreview.net/forum?id=hqkZnSxSWM},
}
Figure