Inferring rankings using constrained sensing
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73523 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1826215374581923840 |
|---|---|
| author | Jagabathula, Srikanth |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Jagabathula, Srikanth |
| author_sort | Jagabathula, Srikanth |
| collection | MIT |
| description | 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 <;<; domain size). Our recovery method is based on finding the sparsest solution (through l[subscript 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 l[subscript 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 n → ∞. ℓ0 optimization is computationally hard. Therefore, the popular compressive sensing literature considers solving the convex relaxation, ℓ[subscript 1] optimization, to find the sparsest solution. However, we show that ℓ[subscript 1] optimization fails to recover a function (even with constant sparsity) generated using the random model with a high probability as n → ∞. 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. |
| first_indexed | 2024-09-23T16:26:18Z |
| format | Article |
| id | mit-1721.1/73523 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:26:18Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/735232022-10-02T07:58:45Z Inferring rankings using constrained sensing Jagabathula, Srikanth Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat Jagabathula, Srikanth Shah, Devavrat 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 <;<; domain size). Our recovery method is based on finding the sparsest solution (through l[subscript 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 l[subscript 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 n → ∞. ℓ0 optimization is computationally hard. Therefore, the popular compressive sensing literature considers solving the convex relaxation, ℓ[subscript 1] optimization, to find the sparsest solution. However, we show that ℓ[subscript 1] optimization fails to recover a function (even with constant sparsity) generated using the random model with a high probability as n → ∞. 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. 2012-10-01T18:07:32Z 2012-10-01T18:07:32Z 2011-11 2011-11 Article http://purl.org/eprint/type/JournalArticle 0018-9448 http://hdl.handle.net/1721.1/73523 Jagabathula, S.; Shah, D.; , "Inferring Rankings Using Constrained Sensing," Information Theory, IEEE Transactions on , vol.57, no.11, pp.7288-7306, Nov. 2011 https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/ 10.1109/tit.2011.2165827 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Jagabathula, Srikanth Inferring rankings using constrained sensing |
| title | Inferring rankings using constrained sensing |
| title_full | Inferring rankings using constrained sensing |
| title_fullStr | Inferring rankings using constrained sensing |
| title_full_unstemmed | Inferring rankings using constrained sensing |
| title_short | Inferring rankings using constrained sensing |
| title_sort | inferring rankings using constrained sensing |
| url | http://hdl.handle.net/1721.1/73523 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT jagabathulasrikanth inferringrankingsusingconstrainedsensing |