Коды для точного нахождения носителя разреженного вектора по ошибочным линейным измерениям и их декодирование
- Авторы: Фернандес М.1, Кабатянский Г.А.2, Круглик С.А.3, Мяо И.4
-
Учреждения:
- Политехнический университет Каталонии
- Сколковский институт науки и технологий (Сколтех)
- Наньянский технологический университет
- Университет Цукубы
- Выпуск: Том 59, № 1 (2023)
- Страницы: 17-24
- Раздел: Статьи
- URL: https://archivog.com/0555-2923/article/view/667574
- DOI: https://doi.org/10.31857/S0555292323010023
- EDN: https://elibrary.ru/JDHVDR
- ID: 667574
Цитировать
Аннотация
Построены коды, позволяющие точно находить носитель неизвестного разреженного вектора, у которого модули всех ненулевых координат примерно равны, по результатам линейных измерений в присутствии шума с ограниченной сверху ℓp-нормой. Предложен алгоритм декодирования, имеющий асимптотически минимальную сложность.
Об авторах
Марсель Фернандес
Политехнический университет Каталонии
Email: marcelf@entel.upc.edu
Барселона, Испания
Григорий Анатольевич Кабатянский
Сколковский институт науки и технологий (Сколтех)
Email: g.kabatyansky@skoltech.ru
Москва, Россия
Станислав Александрович Круглик
Наньянский технологический университет
Email: stanislav.kruglik@ntu.edu.sg
Сингапур
Ин Мяо
Университет Цукубы
Email: miao@sk.tsukuba.ac.jp
Цукуба, префектура Ибараки, Япония
Список литературы
- Egorova E., Fernandez M., Kabatiansky G., Lee M.H. Signature Codes for Weighted Noisy Adder Channel, Multimedia Fingerprinting and Compressed Sensing // Des. Codes Cryptogr. 2019. V. 87. № 2-3. P. 455-462. https://doi.org/10.1007/s10623-018-0551-9
- Егорова Е.Е., Фернандес М., Кабатянский Г.А., Мяо И. Существование и конструкции мультимедийных кодов, способных находить полную коалицию при атаке усреднения и шуме // Пробл. передачи информ. 2020. Т. 56. № 4. С. 97-108. https://doi.org/10.31857/S0555292320040087
- Fan J., Gu Y., Hachimori M., Miao Y. Signature Codes for Weighted Binary Adder Channel and Multimedia Fingerprinting // IEEE Trans. Inform. Theory. 2021. V. 67. № 1. P. 200-216. https://doi.org/10.1109/TIT.2020.3033445
- Егорова Е.Е., Кабатянский Г.А. Разделимые коды для защиты мультимедиа от нелегального копирования коалициями // Пробл. передачи информ. 2021. Т. 57. № 2. С. 90-111. https://doi.org/10.31857/S0555292321020066
- Джанабекова А., Кабатянский Г.А., Камель И., Рабие Т.Ф. Неперекрывающиеся выпуклые многогранники с вершинами из булева куба и другие задачи теории кодирования // Пробл. передачи информ. 2022. Т. 58. № 4. С. 50-61. https://www.mathnet.ru/rus/ppi2383
- Fernandez M., Kabatiansky G., Miao Y. A Novel Support Recovery Algorithms and Its Applications to Multiple-Access Channels // Proc. 2022 IEEE Int. Multi-Conf. on Engineering, Computer and Information Sciences (SIBIRCON). Yekaterinburg, Russian Federation. Nov. 11-13, 2022. P. 170-173. https://doi.org/10.1109/SIBIRCON56155.2022.10017094
- Polyanskiy Y. A Perspective on Massive Random-Access // Proc. 2017 IEEE Int. Symp. on Information Theory (ISIT'2017). Aachen, Germany. June 25-30, 2017. P. 2523-2527. https://doi.org/10.1109/ISIT.2017.8006984
- Donoho D.L.Compressed Sensing // IEEE Trans. Inform. Theory. 2006. V. 52. № 4. P. 1289-1306. https://doi.org/10.1109/TIT.2006.871582
- Candès E.J., Tao T. Near-Optimal Signal Recovery from Random Projections: Universal Encoding Strategies? // IEEE Trans. Inform. Theory. 2006. V. 52. № 12. P. 5406-5425. https://doi.org/10.1109/TIT.2006.885507
- Gkagkos M., Pradhan A.K., Amalladinne V., Narayanan K., Chamberland J-F., Georghiades C.N. Approximate Support Recovery Using Codes for Unsourced Multiple Access // Proc. 2021 IEEE Int. Symp. on Information Theory (ISIT'2021). Melbourne, Australia. July 12-20, 2021. P. 2948-2953. https://doi.org/10.1109/ISIT45174.2021.9517995
- Wen J., Zhou Z., Wang J., Tang X., Mo Q. A Sharp Condition for Exact Support Recovery with Orthogonal Matching Pursuit // IEEE Trans. Signal Process. 2017. V. 65. № 6. P. 1370-1382. https://doi.org/10.1109/TSP.2016.2634550
- Mehrabi M., Tchamkerten A. Error-Correction for Sparse Support Recovery Algorithms // Proc. 2021 IEEE Int. Symp. on Information Theory (ISIT'2021). Melbourne, Australia. July 12-20, 2021. P. 1754-1759. https://doi.org/10.1109/ISIT45174.2021.9518027
- Ericson T., Levenshtein V.I. Superimposed Codes in the Hamming Space // IEEE Trans. Inform. Theory. 1994. V. 40. № 6. P. 1882-1893. https://doi.org/10.1109/18.340463
- Влэдуц С.Г., Кабатянский Г.А., Ломаков В.В. Об исправлении ошибок при искажениях в канале и синдроме // Пробл. передачи информ. 2015. Т. 51. № 2. С. 50-56. http://mi.mathnet.ru/ppi2169
- Sipser M., Spielman D.A. Expander Codes // IEEE Trans. Inform. Theory. 1996. V. 42. № 6. Part 1. P. 1710-1722. https://doi.org/10.1109/18.556667
- Spielman D. Linear-Time Encodable and Decodable Error-Correcting Codes // IEEE Trans. Inform. Theory. 1996. V. 42. № 6. P. 1723-1731. https://doi.org/10.1109/18.556668
- Vorobyev I.Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate // Des. Codes Cryptogr. 2023. V. 4. № 4. P. 1183-1191. https://doi.org/10.1007/s10623-022-01144-x
Дополнительные файлы
