The unlabeled sensing problem is to solve a noisy linear system of equations under unknown permutation of the measurements. We study a particular case of the problem where the permutations are restricted to be r-local, i.e. the permutation matrix is block diagonal with r x r blocks. Assuming a Gaussian measurement matrix, we argue that the r-local permutation model is more challenging compared to a recent sparse permutation model. We propose a proximal alternating minimization algorithm for the general unlabeled sensing problem that provably converges to a first order stationary point. Applied to the r-local model, we show that the resulting algorithm is efficient. We validate the algorithm on synthetic and real datasets. We also formulate the 1-d unassigned distance geometry problem as an unlabeled sensing problem with a structured measurement matrix.
翻译:未贴标签的感测问题是,在测量结果不明的变异下,解决一个噪音的线性方程系统。我们研究了一个特定的问题,即变异限于r-local,也就是说,变异矩阵是带 r x r 区块的对角矩阵。假设高斯测量矩阵,我们认为,与最近的稀疏变异模型相比,r-local变异模型更具挑战性。我们建议对一般的无标签感测问题采用一种快速交替最小化算法,这种非标签感测问题可以与第一个顺序固定点汇合。我们应用到 r-local 模型,我们证明由此产生的算法是有效的。我们验证了合成和真实数据集的算法。我们还用结构化的测量矩阵将1d的无标记距离几度问题作为无标记的感测问题。