Permutations Unlabeled Beyond Sampling Unknown
Permutations Unlabeled Beyond Sampling Unknown
复制标题
DOI：
10.1109/lsp.2019.2908505
复制
发表时间：
2018-12
影响因子：
3.9
通讯作者：
Ivan Dokmanić
中科院分区：
文献类型：
--
作者：
Ivan Dokmanić
Unnikrishnan，Haghighatshoar和Vetterli最近未标记的采样结果指出，具有IID条目的高斯随机矩阵A的概率，可以从$ y = a x $的未知允许中恢复任何$ x $ $的行至少是列的两倍。我们表明，$ a $上的这种条件意味着更强大的东西：当未知$ t $属于任意可逆的可逆性线性变换时，可以从测量$ y = t a x $中回收一个未知的向量$ x $ $ \ mathcal {t} $。集合$ \ MATHCAL {T} $可以是有限的，也可以是无限的。当它是$ M \ times m $置换矩阵时，我们会有经典的未标记采样问题。我们表明，几乎所有$ a $，至少是列的两倍，所有$ x $都可以独特地恢复，或者最多可根据$ \ natercal {t} $恢复到一个比例，而该条件是$ a $是必需的。我们的证明基于矢量空间几何形状。专门研究排列，我们获得了Unnikrishnan，Haghighatshoar和Vetterli的独特性结果的简化证明。在这封信中，我们只关心独特性。稳定性和算法将供将来的工作。
A recent unlabeled sampling result by Unnikrishnan, Haghighatshoar, and Vetterli states that with probability one over Gaussian random matrices A with iid entries, any $x$ can be uniquely recovered from an unknown permutation of $y = A x$ as soon as $A$ has at least twice as many rows as columns. We show that this condition on $A$ implies something much stronger: that an unknown vector $x$ can be recovered from measurements $y = T A x$, when the unknown $T$ belongs to an arbitrary set of invertible, diagonalizable linear transformations $\mathcal {T}$. The set $\mathcal {T}$ can be finite or countably infinite. When it is the set of $m \times m$ permutation matrices, we have the classical unlabeled sampling problem. We show that for almost all $A$ with at least twice as many rows as columns, all $x$ can be recovered either uniquely, or up to a scale depending on $\mathcal {T}$, and that the condition on the size of $A$ is necessary. Our proof is based on vector space geometry. Specializing to permutations, we obtain a simplified proof of the uniqueness result of Unnikrishnan, Haghighatshoar, and Vetterli. In this letter, we are only concerned with uniqueness; stability and algorithms are left for future work.