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

arXiv: https://arxiv.org/abs/2211.07621 · HTML: https://mlsanity.com/paper/2211.07621/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 54 references that are in the map.
- First posted on arXiv 14 Nov 2022.

## Builds on (most cited first, 15 of 15)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Denoising Linear Models with Permuted Data](https://mlsanity.com/paper/1704.07461/) (2017)
- [Linear Regression without Correspondences via Concave Minimization](https://mlsanity.com/paper/2003.07706/) (2020)
- [Signal Recovery from Unlabeled Samples](https://mlsanity.com/paper/1701.08701/) (2017)
- [Spherical Regression under Mismatch Corruption with Application to Automated Knowledge Translation](https://mlsanity.com/paper/1810.05679/) (2018)
- [Permutations Unlabeled beyond Sampling Unknown](https://mlsanity.com/paper/1812.00498/) (2018)
- [The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors](https://mlsanity.com/paper/1909.02496/) (2019)
- [Probabilistic Record Linkage and Deduplication after Indexing, Blocking, and Filtering](https://mlsanity.com/paper/1603.07816/) (2016)
- [r-local sensing: Improved algorithm and applications](https://mlsanity.com/paper/2110.14034/) (2021)
- [R-local unlabeled sensing: A novel graph matching approach for multiview unlabeled sensing under local permutations](https://mlsanity.com/paper/1911.06382/) (2019)
- [Regularization for Shuffled Data Problems via Exponential Family Priors on the Permutation Group](https://mlsanity.com/paper/2111.01767/) (2021)
- [Quickest Anomaly Detection in Sensor Networks With Unlabeled Samples](https://mlsanity.com/paper/2209.01525/) (2022)

## Abstract (arXiv)

Unlabeled sensing is a linear inverse problem with permuted measurements. We propose an alternating minimization (AltMin) algorithm with a suitable initialization for two widely considered permutation models: partially shuffled/k-sparse permutations and r-local/block diagonal permutations. Key to the performance of the AltMin algorithm is the initialization. For the exact unlabeled sensing problem, assuming either a Gaussian measurement matrix or a sub-Gaussian signal, we bound the initialization error in terms of the number of blocks s and the number of shuffles k. Experimental results show that our algorithm is fast, applicable to both permutation models, and robust to choice of measurement matrix. We also test our algorithm on several real datasets for the linked linear regression problem and show superior performance compared to baseline methods.