On the doubly sparse compressed sensing problem

Grigory Kabatiansky, Serge Vlǎduţ, Cedric Tavernier

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


A new variant of the Compressed Sensing problem is investigated when the number of measurements corrupted by errors is upper bounded by some value l but there are no more restrictions on errors. We prove that in this case it is enough to make 2(t+l) measurements, where t is the sparsity of original data. Moreover for this case a rather simple recovery algorithm is proposed. An analog of the Singleton bound from coding theory is derived what proves optimality of the corresponding measurement matrices.

Original languageEnglish
Title of host publicationCryptography and Coding - 15th IMA International Conference, IMACC 2015, Proceedings
EditorsJens Groth
PublisherSpringer Verlag
Number of pages6
ISBN (Print)9783319272382
Publication statusPublished - 2015
Externally publishedYes
Event15th IMA International Conference on Cryptography and Coding, IMACC 2015 - Oxford, United Kingdom
Duration: 15 Dec 201517 Dec 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th IMA International Conference on Cryptography and Coding, IMACC 2015
Country/TerritoryUnited Kingdom


Dive into the research topics of 'On the doubly sparse compressed sensing problem'. Together they form a unique fingerprint.

Cite this