On the doubly sparse compressed sensing problem

Grigory Kabatiansky, Serge Vlǎduţ, Cedric Tavernier

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

Abstract

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
Pages184-189
Number of pages6
ISBN (Print)9783319272382
DOIs
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)
Volume9496
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th IMA International Conference on Cryptography and Coding, IMACC 2015
Country/TerritoryUnited Kingdom
CityOxford
Period15/12/1517/12/15

Fingerprint

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

Cite this