Coding-Theoretic Methods for Sparse Recovery. Cheraghchi, M. In Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing, pages 909–916, 2011. Link Paper doi abstract bibtex We review connections between coding-theoretic objects and sparse learning problems. In particular, we show how seemingly different combinatorial objects such as error-correcting codes, combinatorial designs, spherical codes, compressed sensing matrices and group testing designs can be obtained from one another. The reductions enable one to translate upper and lower bounds on the parameters attainable by one object to another. We survey some of the well-known reductions in a unified presentation, and bring some existing gaps to attention. New reductions are also introduced; in particular, we bring up the notion of minimum "L-wise distance" of codes and show that this notion closely captures the combinatorial structure of RIP-2 matrices. Moreover, we show how this weaker variation of the minimum distance is related to combinatorial list-decoding properties of codes.
@INPROCEEDINGS{ref:conf:Che11,
author = {Mahdi Cheraghchi},
title = {Coding-Theoretic Methods for Sparse Recovery},
year = 2011,
booktitle = {Proceedings of the 49th {Annual Allerton Conference
on Communication, Control, and Computing}},
pages = {909--916},
doi = {10.1109/Allerton.2011.6120263},
url_Link = {https://ieeexplore.ieee.org/document/6120263},
url_Paper = {https://arxiv.org/abs/1110.0279},
abstract = { We review connections between coding-theoretic
objects and sparse learning problems. In particular,
we show how seemingly different combinatorial
objects such as error-correcting codes,
combinatorial designs, spherical codes, compressed
sensing matrices and group testing designs can be
obtained from one another. The reductions enable one
to translate upper and lower bounds on the
parameters attainable by one object to another. We
survey some of the well-known reductions in a
unified presentation, and bring some existing gaps
to attention. New reductions are also introduced; in
particular, we bring up the notion of minimum
"L-wise distance" of codes and show that this notion
closely captures the combinatorial structure of
RIP-2 matrices. Moreover, we show how this weaker
variation of the minimum distance is related to
combinatorial list-decoding properties of codes. }
}
Downloads: 0
{"_id":"w73TFXnyh4WBwqbMW","bibbaseid":"cheraghchi-codingtheoreticmethodsforsparserecovery-2011","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]}],"title":"Coding-Theoretic Methods for Sparse Recovery","year":"2011","booktitle":"Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing","pages":"909–916","doi":"10.1109/Allerton.2011.6120263","url_link":"https://ieeexplore.ieee.org/document/6120263","url_paper":"https://arxiv.org/abs/1110.0279","abstract":"We review connections between coding-theoretic objects and sparse learning problems. In particular, we show how seemingly different combinatorial objects such as error-correcting codes, combinatorial designs, spherical codes, compressed sensing matrices and group testing designs can be obtained from one another. The reductions enable one to translate upper and lower bounds on the parameters attainable by one object to another. We survey some of the well-known reductions in a unified presentation, and bring some existing gaps to attention. New reductions are also introduced; in particular, we bring up the notion of minimum \"L-wise distance\" of codes and show that this notion closely captures the combinatorial structure of RIP-2 matrices. Moreover, we show how this weaker variation of the minimum distance is related to combinatorial list-decoding properties of codes. ","bibtex":"@INPROCEEDINGS{ref:conf:Che11,\n author =\t {Mahdi Cheraghchi},\n title =\t {Coding-Theoretic Methods for Sparse Recovery},\n year =\t 2011,\n booktitle =\t {Proceedings of the 49th {Annual Allerton Conference\n on Communication, Control, and Computing}},\n pages =\t {909--916},\n doi =\t\t {10.1109/Allerton.2011.6120263},\n url_Link =\t {https://ieeexplore.ieee.org/document/6120263},\n url_Paper =\t {https://arxiv.org/abs/1110.0279},\n abstract =\t { We review connections between coding-theoretic\n objects and sparse learning problems. In particular,\n we show how seemingly different combinatorial\n objects such as error-correcting codes,\n combinatorial designs, spherical codes, compressed\n sensing matrices and group testing designs can be\n obtained from one another. The reductions enable one\n to translate upper and lower bounds on the\n parameters attainable by one object to another. We\n survey some of the well-known reductions in a\n unified presentation, and bring some existing gaps\n to attention. New reductions are also introduced; in\n particular, we bring up the notion of minimum\n \"L-wise distance\" of codes and show that this notion\n closely captures the combinatorial structure of\n RIP-2 matrices. Moreover, we show how this weaker\n variation of the minimum distance is related to\n combinatorial list-decoding properties of codes. }\n}\n\n","author_short":["Cheraghchi, M."],"key":"ref:conf:Che11","id":"ref:conf:Che11","bibbaseid":"cheraghchi-codingtheoreticmethodsforsparserecovery-2011","role":"author","urls":{" link":"https://ieeexplore.ieee.org/document/6120263"," paper":"https://arxiv.org/abs/1110.0279"},"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T00:28:13.095Z","downloads":9,"keywords":[],"search_terms":["coding","theoretic","methods","sparse","recovery","cheraghchi"],"title":"Coding-Theoretic Methods for Sparse Recovery","year":2011,"dataSources":["YZqdBBx6FeYmvQE6D"]}