Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909424895918080 |
|---|---|
| author | Abbasi, Ahmed Aeron, Shuchin Tasissa, Abiy |
| author_facet | Abbasi, Ahmed Aeron, Shuchin Tasissa, Abiy |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_07621 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing Abbasi, Ahmed Aeron, Shuchin Tasissa, Abiy Signal Processing Information Theory Machine Learning Probability 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. |
| title | Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing |
| topic | Signal Processing Information Theory Machine Learning Probability |
| url | https://arxiv.org/abs/2211.07621 |