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

Обложка

Цитировать

Полный текст

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

Аннотация

Построены коды, позволяющие точно находить носитель неизвестного разреженного вектора, у которого модули всех ненулевых координат примерно равны, по результатам линейных измерений в присутствии шума с ограниченной сверху ℓ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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».