Inferring Rankings Using Constrained Sensing
Inferring Rankings Using Constrained Sensing
复制标题
DOI：
10.1109/tit.2011.2165827
复制
发表时间：
2011-11-01
影响因子：
2.5
通讯作者：
Shah, Devavrat
中科院分区：
文献类型：
--
作者：
Jagabathula, Srikanth;Shah, Devavrat
我们考虑从给定的部分信息恢复n个元素上的置换空间(或对称群)上的函数的问题；我们考虑的部分信息与函数的群论傅里叶变换有关。这个问题自然会出现在几种设置中，例如分级选举、多目标跟踪、分级系统和推荐系统。受Donoho和Stark在离散时间函数背景下的工作的启发，我们专注于具有稀疏支集(支集大小无穷大)的非负函数。L(0)优化是计算困难的。因此，流行的压缩传感文献考虑求解凸松弛，L(1)优化，寻找最稀疏解。然而，我们证明了L(1)的优化不能恢复用随机模型产生的函数(即使在常稀疏性下)是n-无穷大的。为了克服这个问题，我们提出了一种新的迭代算法来恢复满足充分条件的函数。最后，利用信息论框架，我们研究了精确恢复可能的必要条件。
We consider the problem of recovering a function over the space of permutations (or, the symmetric group) over n elements from given partial information; the partial information we consider is related to the group theoretic Fourier Transform of the function. This problem naturally arises in several settings such as ranked elections, multi-object tracking, ranking systems, and recommendation systems. Inspired by the work of Donoho and Stark in the context of discrete-time functions, we focus on non-negative functions with a sparse support (support size infinity. l(0) optimization is computationally hard. Therefore, the popular compressive sensing literature considers solving the convex relaxation, l(1) optimization, to find the sparsest solution. However, we show that l(1) optimization fails to recover a function (even with constant sparsity) generated using the random model with a high probability as n -> infinity. In order to overcome this problem, we propose a novel iterative algorithm for the recovery of functions that satisfy the sufficient conditions. Finally, using an Information Theoretic framework, we study necessary conditions for exact recovery to be possible.