A Robust Parallel Algorithm for Combinatorial Compressed Sensing

DOI10.1109/TSP.2018.2806359MaRDI QIDQ4622104zbMATH OpenOpenAlexFDO

Authors Rodrigo Mendoza-Smith, Jared Tanner, Florian Wechsung

Publication date 12 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.09012

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: In previous work two of the authors have shown that a vector $xinmathbb{R}^n$ with at most $k<n$ nonzeros can be recovered from an expander sketch $Ax$ in $mathcalO(mathrmnnz(A)logk)$ operations via the Parallel-$el{l}_0$ decoding algorithm, where $mathrmnnz(A)$ denotes the number of nonzero entries in $Ainmathbb{R}^{mimesn}$. In this paper we present the Robust-$el{l}_0$ decoding algorithm, which robustifies Parallel-$el{l}_0$ when the sketch $Ax$ is corrupted by additive noise. This robustness is achieved by approximating the asymptotic posterior distribution of values in the sketch given its corrupted measurements. We provide analytic expressions that approximate these posteriors under the assumptions that the nonzero entries in the signal and the noise are drawn from continuous distributions. Numerical experiments presented show that Robust-$el{l}_0$ is superior to existing greedy and combinatorial compressed sensing algorithms in the presence of small to moderate signal-to-noise ratios in the setting of Gaussian signals and Gaussian additive noise.

Cited in

(1)

• Facets of high-dimensional Gaussian polytopes

This page was built for publication: A Robust Parallel Algorithm for Combinatorial Compressed Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4622104)