Коды для точного нахождения носителя разреженного вектора по ошибочным линейным измерениям и их декодирование

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Построены коды, позволяющие точно находить носитель неизвестного разреженного вектора, у которого модули всех ненулевых координат примерно равны, по результатам линейных измерений в присутствии шума с ограниченной сверху ℓp-нормой. Предложен алгоритм декодирования, имеющий асимптотически минимальную сложность.

Об авторах

Марсель Фернандес

Политехнический университет Каталонии

Email: marcelf@entel.upc.edu
Барселона, Испания

Григорий Анатольевич Кабатянский

Сколковский институт науки и технологий (Сколтех)

Email: g.kabatyansky@skoltech.ru
Москва, Россия

Станислав Александрович Круглик

Наньянский технологический университет

Email: stanislav.kruglik@ntu.edu.sg
Сингапур

Ин Мяо

Университет Цукубы

Email: miao@sk.tsukuba.ac.jp
Цукуба, префектура Ибараки, Япония

Список литературы

  1. 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
  2. Егорова Е.Е., Фернандес М., Кабатянский Г.А., Мяо И. Существование и конструкции мультимедийных кодов, способных находить полную коалицию при атаке усреднения и шуме // Пробл. передачи информ. 2020. Т. 56. № 4. С. 97-108. https://doi.org/10.31857/S0555292320040087
  3. 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
  4. Егорова Е.Е., Кабатянский Г.А. Разделимые коды для защиты мультимедиа от нелегального копирования коалициями // Пробл. передачи информ. 2021. Т. 57. № 2. С. 90-111. https://doi.org/10.31857/S0555292321020066
  5. Джанабекова А., Кабатянский Г.А., Камель И., Рабие Т.Ф. Неперекрывающиеся выпуклые многогранники с вершинами из булева куба и другие задачи теории кодирования // Пробл. передачи информ. 2022. Т. 58. № 4. С. 50-61. https://www.mathnet.ru/rus/ppi2383
  6. 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
  7. 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
  8. Donoho D.L.Compressed Sensing // IEEE Trans. Inform. Theory. 2006. V. 52. № 4. P. 1289-1306. https://doi.org/10.1109/TIT.2006.871582
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. Влэдуц С.Г., Кабатянский Г.А., Ломаков В.В. Об исправлении ошибок при искажениях в канале и синдроме // Пробл. передачи информ. 2015. Т. 51. № 2. С. 50-56. http://mi.mathnet.ru/ppi2169
  15. 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
  16. 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
  17. 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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2023