The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

Youssef Chaabouni, David Gamarnik · 2025

Read The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements by Youssef Chaabouni, David Gamarnik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01809.txt.

Description

Youssef Chaabouni and David Gamarnik study when a sparse signal can be recovered from few noisy measures. A sparse signal has only a few nonzero parts among many slots. Their measures use sparse random matrices, where each row touches few slots. They find conditions on how many measures suffice for best likelihood recovery when noise is low.

Paired with known lower bounds, their result gives a sharp threshold for the needed sample count. One regime stands out: sparsity costs only a modest factor in samples but gains nearly proportional savings in computation. They also study thinning a dense design after data are taken. Even heavy thinning still allows recovery with a stated sample size in their proof.

Catalog record

CREATORYoussef Chaabouni, David Gamarnik
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-01809

Browse the full library · About the Tower of Babel