nach oben

Problems of Information Transmission

Erschienen in:

01.01.2023 | CODING THEORY

Codes for Exact Support Recovery of Sparse Vectors from Inaccurate Linear Measurements and Their Decoding

verfasst von: M. Fernandez, G. A. Kabatiansky, S. A. Kruglik, Y. Miao

Erschienen in: Problems of Information Transmission | Ausgabe 1/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We construct codes that allow to exactly recover the support of an unknown sparse vector with almost equal absolute values of all nonzero coordinates given results of linear measurements in the presence of noise with \(\ell_p\)-norm bounded from above. We propose a decoding algorithm with asymptotically minimum complexity.

Vorheriger Artikel Series of Formulas for Bhattacharyya Parameters in the Theory of Polar Codes

Nächster Artikel Design and Decoding of Polar Codes with Large Kernels: A Survey

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Egorova, E., Fernandez, M., Kabatiansky, G., and Lee, M.H., Signature Codes for Weighted Noisy Adder Channel, Multimedia Fingerprinting and Compressed Sensing, Des. Codes Cryptogr., 2019, vol. 87, no. 2–3, pp. 455–462. https://doi.org/10.1007/s10623-018-0551-9MathSciNetCrossRefMATH

Egorova, E.E., Fernandez, M., Kabatiansky, G.A., and Miao, Y., Existence and Construction of Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise, Probl. Peredachi Inf., 2020, vol. 56, no. 4, pp. 97–108 [Probl. Inf. Transm. (Engl. Transl.), 2000, vol. 56, no. 4, pp. 388–398]. https://doi.org/10.1134/S0032946020040080MathSciNetMATH

Fan, J., Gu, Y., Hachimori, M., and Miao, Y., Signature Codes for Weighted Binary Adder Channel and Multimedia Fingerprinting, IEEE Trans. Inform. Theory, 2021, vol. 67, no. 1, pp. 200–216. https://doi.org/10.1109/TIT.2020.3033445MathSciNetCrossRefMATH

Egorova, E.E. and Kabatiansky, G.A., Separable Collusion-Secure Multimedia Codes, Probl. Peredachi Inf., 2021, vol. 57, no. 2, pp. 90–111 [Probl. Inf. Transm. (Engl. Transl.), 2021, vol. 57, no. 2, pp. 178–198]. https://doi.org/10.1134/S003294602102006XMathSciNetMATH

Janabekova, A., Kabatiansky, G.A., Kamel, I., and Rabie, T.F., Nonoverlapping Convex Polytopes with Vertices in a Boolean Cube and Other Problems in Coding Theory, Probl. Peredachi Inf., 2022, vol. 58, no. 4, pp. 50–61 [Probl. Inf. Transm. (Engl. Transl.), 2022, vol. 58, no. 4, pp. 341–351]. https://www.mathnet.ru/eng/ppi2383MathSciNetMATH

Fernandez, M., Kabatiansky, G., and Miao, Y., A Novel Support Recovery Algorithms and Its Applications to Multiple-Access Channels in Proc. 2022 IEEE Int. Multi-Conf. on Engineering, Computer and Information Sciences (SIBIRCON), Yekaterinburg, Russian Federation, Nov. 11–13, 2022, pp. 170–173. https://doi.org/10.1109/SIBIRCON56155.2022.10017094

Polyanskiy, Y., A Perspective on Massive Random-Access, in Proc. 2017 IEEE Int. Symp. on Information Theory (ISIT’2017), Aachen, Germany, June 25–30, 2017, pp. 2523–2527. https://doi.org/10.1109/ISIT.2017.8006984

Donoho, D.L., Compressed Sensing, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 4, pp. 1289–1306. https://doi.org/10.1109/TIT.2006.871582MathSciNetCrossRefMATH

Candès, E.J. and Tao, T., Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 12, pp. 5406–5425. https://doi.org/10.1109/TIT.2006.885507MathSciNetCrossRefMATH

10.

Gkagkos, M., Pradhan, A.K., Amalladinne, V., Narayanan, K., Chamberland, J-F., and Georghiades, C.N., Approximate Support Recovery Using Codes for Unsourced Multiple Access, in Proc. 2021 IEEE Int. Symp. on Information Theory (ISIT’2021), Melbourne, Australia, July 12–20, 2021, pp. 2948–2953. https://doi.org/10.1109/ISIT45174.2021.9517995

11.

Wen, J., Zhou, Z., Wang, J., Tang, X., and Mo, Q., A Sharp Condition for Exact Support Recovery with Orthogonal Matching Pursuit, IEEE Trans. Signal Process., 2017, vol. 65, no. 6, pp. 1370–1382. https://doi.org/10.1109/TSP.2016.2634550MathSciNetCrossRefMATH

12.

Mehrabi, M. and Tchamkerten, A., Error-Correction for Sparse Support Recovery Algorithms, in Proc. 2021 IEEE Int. Symp. on Information Theory (ISIT’2021), Melbourne, Australia, July 12–20, 2021, pp. 1754–1759. https://doi.org/10.1109/ISIT45174.2021.9518027

13.

Ericson, T. and Levenshtein, V.I., Superimposed Codes in the Hamming Space, IEEE Trans. Inform. Theory, 1994, vol. 40, no. 6, pp. 1882–1893. https://doi.org/10.1109/18.340463CrossRefMATH

14.

Vlǎduţ, S.G., Kabatiansky, G.A., and Lomakov, V.V., On Error Correction with Errors in Both the Channel and Syndrome, Probl. Peredachi Inf., 2015, vol. 51, no. 2, pp. 50–56 [Probl. Inf. Transm. (Engl. Transl.), 2015, vol. 51, no. 2, pp. 132–138]. https://doi.org/10.1134/S0032946015020040MathSciNetMATH

15.

Sipser, M. and Spielman, D.A., Expander Codes, IEEE Trans. Inform. Theory, 1996, vol. 42, no. 6, part 1, pp. 1710–1722. https://doi.org/10.1109/18.556667MathSciNetCrossRefMATH

16.

Spielman, D., Linear-Time Encodable and Decodable Error-Correcting Codes, IEEE Trans. Inform. Theory, 1996, vol. 42, no. 6, pp. 1723–1731. https://doi.org/10.1109/18.556668MathSciNetCrossRefMATH

17.

Vorobyev, I., Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate, Des. Codes Cryptogr., 2023, vol. 4, no. 4, pp. 1183–1191. https://doi.org/10.1007/s10623-022-01144-xMathSciNetCrossRefMATH

Titel: Codes for Exact Support Recovery of Sparse Vectors from Inaccurate Linear Measurements and Their Decoding
verfasst von: M. Fernandez
G. A. Kabatiansky
S. A. Kruglik
Y. Miao
Publikationsdatum: 01.01.2023
Verlag: Pleiades Publishing
Erschienen in: Problems of Information Transmission / Ausgabe 1/2023
Print ISSN: 0032-9460
Elektronische ISSN: 1608-3253
DOI: https://doi.org/10.1134/S0032946023010027

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Die Gewinner und Laudatoren des Sustainability Award in Automotive 2024/© Uli Regenscheit | ATZlive, Search Icon, Banner Hanser, Suresh Vittal/© Alteryx, Additiv gefertigte Teile/© Marina_Skoropadskaya | Getty Images | iStock, Warnschild "Land unter"/© Bluedesign / Fotolia, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade, chassis.tech plus 2023/© [M] ATZlive / TÜV SÜD PRODUCT SERVICE GMBH, adäsion-Webinar-Matinee/© krystiannawrocki_ Getty Images

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2023

Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements

Design and Decoding of Polar Codes with Large Kernels: A Survey

Batch Poissonian Arrival Models of Multiservice Network Traffic

Overparameterized Maximum Likelihood Tests for Detection of Sparse Vectors

Series of Formulas for Bhattacharyya Parameters in the Theory of Polar Codes

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.