Inferring Rankings Using Constrained Sensing

DOI10.1109/TIT.2011.2165827MaRDI QIDQ5272233zbMATH OpenOpenAlexFDO

Authors Srikanth Jagabathula, Devavrat Shah

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.0895

Mathematics Subject Classification ID

Almost periodic functions on groups and semigroups and their generalizations (recurrent functions, distal functions, etc.); almost automorphic functions (43A60) Application of orthogonal and other special functions (94A11)

Abstract: 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 $ll$ domain size). Our recovery method is based on finding the sparsest solution (through $el{l}_0$ optimization) that is consistent with the available information. As the main result, we derive sufficient conditions for functions that can be recovered exactly from partial information through $el{l}_0$ optimization. Under a natural random model for the generation of functions, we quantify the recoverability conditions by deriving bounds on the sparsity (support size) for which the function satisfies the sufficient conditions with a high probability as $noinfty$. $el{l}_0$ optimization is computationally hard. Therefore, the popular compressive sensing literature considers solving the convex relaxation, $el{l}_1$ optimization, to find the sparsest solution. However, we show that $el{l}_1$ optimization fails to recover a function (even with constant sparsity) generated using the random model with a high probability as $noinfty$. 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.

Cited in

(10)

• The convex geometry of linear inverse problems
• Uncovering the riffled independence structure of ranked data
• High-dimensional change-point estimation: combining filtering with convex optimization
• Online collaborative filtering on graphs
• Geometric inference for general high-dimensional linear inverse problems
• scientific article; zbMATH DE number 5364205 (Why is no real title available?)
• A Fourier-theoretic approach for inferring symmetries
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Inferring Sparse Preference Lists from Partial Information
• Stochastically Constrained Ranking and Selection via SCORE

This page was built for publication: Inferring Rankings Using Constrained Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272233)