Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing

Ahmed Ali Abbasi, Abiy Tasissa, Shuchin Aeron

TL;DR

This paper introduces an efficient Alternating Minimization (AltMin) algorithm to solve "unlabeled sensing"—a problem where you must recover a signal from measurements that have been shuffled. By providing a rigorous theoretical analysis of two novel initialization strategies, the authors show that their approach is not only fast and robust but also outperforms existing methods on real-world "linked linear regression" tasks.

What Problem Does This Paper Address?

In a standard linear regression, we assume our data points are neatly labeled: measurement $y_i$ corresponds to feature vector $b_i$. But what if the labels are lost? This is the unlabeled sensing problem. Mathematically, it’s expressed as $Y = P^*BX^* + W$, where $P^*$ is an unknown permutation matrix that "scrambles" the rows of the data.

This isn't just a theoretical headache; it happens in real-world scenarios like record linkage (merging two databases where unique IDs are missing) and sensor networks (where data packets might arrive out of order or without source tags). Solving this is notoriously difficult because it’s a non-convex, combinatorial problem—you have to find the best signal $X$ and the best shuffle $P$ simultaneously.

The authors focus on two specific, practical shuffling models:

  1. $k$-sparse (Partially Shuffled): Most data is in the right place, but $k$ entries have been swapped.
  2. $r$-local (Block Diagonal): Shuffling only happens within small, known groups or "blocks" (e.g., you know a record belongs to a specific city, but not which household).

Methods

The authors propose an Alternating Minimization (AltMin) framework. The logic is simple:

  1. Fix the permutation ($P$), solve for the signal ($X$): This is a standard least-squares problem.
  2. Fix the signal ($X$), solve for the permutation ($P$): This becomes a Linear Assignment Problem (LAP), which can be solved efficiently using algorithms like the Hungarian method.

The "make-or-break" component of AltMin is the initialization. If you start with a terrible guess, the algorithm gets stuck in a local minimum. The paper introduces two key initialization strategies:

  • Collapsed Initialization (for $r$-local): They sum the measurements within each block. Because the sum is invariant to the order of elements within that block, this "collapses" the effect of the shuffle, allowing for a decent first estimate of the signal.
  • Identity Initialization (for $k$-sparse): They simply assume $P$ is the identity matrix initially, which works surprisingly well when the number of shuffles $k$ is small relative to the total data size $n$.

Datasets

The researchers evaluated their algorithm on both synthetic data and several diverse real-world datasets used for linked linear regression:

  • Ames Housing: Predicting house prices in Ames, Iowa.
  • Beijing Air Quality (air-qty): Time-stamped environmental readings.
  • FTP, SCM, and SCS: Standard benchmarks for multivariate regression and record linkage.

Key Insights and Ideas

  • The Power of Collapsing: The most elegant "aha moment" is the use of block-sums for $r$-local permutations. By recognizing that $\mathbf{1}^\top P_i = \mathbf{1}^\top$ (summing a permuted vector is the same as summing the original), they effectively bypass the permutation problem to get a "clean" first look at the signal.
  • Theoretical Guarantees: The paper doesn't just say "it works"; it uses high-dimensional probability tools (like the Johnson-Lindenstrauss lemma and Hanson-Wright inequality) to prove that the initialization error stays small as long as the number of blocks $s$ is large enough or the number of shuffles $k$ is small enough.
  • Robustness to Matrix Choice: Many previous "spectral" methods for this problem only work if the measurement matrix $B$ is Gaussian. This paper demonstrates that AltMin is robust even when $B$ follows a uniform distribution.

Key Results

  • Superior Performance: In the air-qty and ames datasets, the proposed AltMin-r and AltMin-k methods consistently achieved higher $R^2$ values (coefficient of determination) and lower relative errors than baselines like RLUS or $\ell_2$-regularized regression.
  • Speed: The algorithm is remarkably fast. For a dataset with over 44,000 samples (scs), the MATLAB runtime on a standard laptop was less than one second.
  • Phase Transitions: Synthetic tests showed that the algorithm can perfectly recover the permutation $P^*$ up to a certain "breaking point" of shuffling (e.g., when the block size $r$ becomes too large or the number of shuffles $k$ approaches the total number of samples $n$).

Limitations and Future Work

While the paper provides a rigorous analysis of the initialization, it stops short of a full global convergence proof for the entire alternating sequence. In other words, we know we start in a good place, but we don't have a mathematical guarantee that every step after that is optimal (though the experimental results suggest it is).

The authors suggest that future research should focus on:

  1. Establishing formal conditions for provable global convergence.
  2. Analyzing the rate of convergence to understand exactly how many iterations are needed for different noise levels.

Summary updated

Abstract

The unlabeled sensing problem is to recover an unknown signal from permuted linear measurements. We propose an alternating minimization algorithm with a suitable initialization for the widely considered k-sparse permutation model. Assuming either a Gaussian measurement matrix or a sub-Gaussian signal, we upper bound the initialization error for the r-local and k-sparse permutation models in terms of the block size $r$ and the number of shuffles k, respectively. Our algorithm is computationally scalable and, compared to baseline methods, achieves superior performance on real and synthetic datasets.
BibTeX
@misc{abbasi2022alternating,
  author = {Ahmed Ali Abbasi and Abiy Tasissa and Shuchin Aeron},
  title = {{Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing}},
  year = {2022},
  eprint = {2211.07621},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.07621},
}
Figure