The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing From Multiple Measurement Vectors
The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing From Multiple Measurement Vectors
复制标题
DOI：
10.1109/tit.2021.3127072
复制
发表时间：
2022-04
影响因子：
2.5
通讯作者：
Hang Zhang;M. Slawski;Ping Li
中科院分区：
文献类型：
--
作者：
Hang Zhang;M. Slawski;Ping Li
在“未标记感测”中，人们观察到一组潜在信号的线性测量，其中关于它们的排序的信息不完整或缺失，这可以根据未知的排列来建模。先前关于单个噪声测量向量的情况的工作已经暴露了两个主要挑战：1）关于信噪比（$\mathsf {\mathbf {n}}$）的高要求，即，近似为$n^{5}$的数量级，以及2）一般而言，鉴于NP-困难，大量的计算负担。在本文中，我们研究的情况下，多个嘈杂的测量向量（MMVs）导致从一个共同的置换和调查到什么程度的MMVs的数量m$有利于置换恢复“借用强度”。在我们的工作中，上述两个挑战至少部分得到了解决。首先，我们表明，一个大的稳定秩的信号显着降低所需的可从多项式在$n$为$m = 1$下降到一个常数为$m = \Omega（\log n）$，其中$m$表示MMV的数量和$n$表示每个MV的测量数。这种约束被证明是尖锐的，并与相变现象。其次，我们提出了计算方法来恢复未知的置换。对于已知信号的“预言情形”，极大似然估计归结为一个线性分配问题，其全局最优解可以有效地获得。如果信号和置换都是未知的，这个问题就变成了一个二次分配问题;虽然这样的问题通常是NP-困难的，因此构成了一个重大的挑战，我们建议通过投影梯度下降与非凸约束集来解决它，并建立这个方案的单调下降属性。基于所提出的计算方法的数值实验证实了我们的理论分析的严密性。
In “Unlabeled Sensing”, one observes a set of linear measurements of an underlying signal with incomplete or missing information about their ordering, which can be modeled in terms of an unknown permutation. Previous work on the case of a single noisy measurement vector has exposed two main challenges: 1) a high requirement concerning the signal-to-noise ratio ( $\mathsf {\mathbf {snr}}$ ), i.e., approximately of the order of $n^{5}$ , and 2) a massive computational burden in light of NP-hardness in general. In this paper, we study the case of multiple noisy measurement vectors (MMVs) resulting from a common permutation and investigate to what extent the number of MMVs $m$ facilitates permutation recovery by “borrowing strength”. The above two challenges have at least partially been resolved within our work. First, we show that a large stable rank of the signal significantly reduces the required snr which can drop from a polynomial in $n$ for $m = 1$ to a constant for $m = \Omega (\log n)$ , where $m$ denotes the number of MMVs and $n$ denotes the number of measurements per MV. This bound is shown to be sharp and is associated with a phase transition phenomenon. Second, we propose computational methods for recovering the unknown permutation. For the “oracle case” with known signal, the maximum likelihood (ML) estimator reduces to a linear assignment problem whose global optimum can be obtained efficiently. If both the signal and the permutation are unknown, the problem becomes a quadratic assignment problem; while such a problem is generally NP-hard and hence poses a significant challenge, we propose to tackle it via projected gradient descent with a non-convex constraint set, and establish a monotonic descent property of this scheme. Numerical experiments based on the proposed computational approach confirm the tightness of our theoretical analysis.