Toeplitz Unlabeled Sensing

Unlabeled sensing is the problem of finding the solution to a linear system of equations, for which the entries of the right-hand-side vector are possibly given out of order. While most of the existing theory treats the case of generic or randomly sampled coefficient matrices, it is matrices with special structure that tend to occur most often in applications. In this paper, we present new algebraic recovery theory for the unlabeled sensing problem where the coefficient matrix is Toeplitz, a common matrix structure throughout signal processing. The theory certifies that existing unlabeled sensing algorithms based on solving polynomial systems of equations for generic coefficient matrices are in fact applicable to the Toeplitz case, and we demonstrate this via computational experiments in the context of system identification.