Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-8617
Main Title: Derandomizing Compressed Sensing With Combinatorial Design
Author(s): Jung, Peter
Kueng, Richard
Mixon, Dustin G.
Type: Article
Language Code: en
Abstract: Compressed sensing is the art of effectively reconstructing structured n-dimensional vectors from substantially fewer measurements than naively anticipated. A plethora of analytical reconstruction guarantees support this credo. The strongest among them are based on deep results from large-dimensional probability theory and require a considerable amount of randomness in the measurement design. Here, we demonstrate that derandomization techniques allow for a considerable reduction in the randomness required for such proof strategies. More precisely, we establish uniform s-sparse reconstruction guarantees for Cs log(n) measurements that are chosen independently from strength-4 orthogonal arrays and maximal sets of mutually unbiased bases, respectively. These are highly structured families of Ĉn2 vectors that imitate signed Bernoulli and standard Gaussian vectors in a (partially) derandomized fashion.
URI: https://depositonce.tu-berlin.de/handle/11303/9572
http://dx.doi.org/10.14279/depositonce-8617
Issue Date: 6-Jun-2019
Date Available: 1-Jul-2019
DDC Class: 510 Mathematik
Subject(s): compressed sensing
k-wise independence
orthogonal arrays
spherical design
derandomization
Sponsor/Funder: DFG, 414044773, Open Access Publizieren 2019 - 2020 / Technische Universität Berlin
License: https://creativecommons.org/licenses/by/4.0/
Journal Title: Frontiers in Applied Mathematics and Statistics
Publisher: Frontiers Media
Publisher Place: Lausanne
Volume: 5
Article Number: 26
Publisher DOI: 10.3389/fams.2019.00026
EISSN: 2297-4687
Appears in Collections:FG Theoretische Grundlagen der Kommunikationstechnik » Publications

Files in This Item:
File Description SizeFormat 
fams-05-00026.pdf737 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons