Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
From MaRDI portal
Publication:5396950
DOI10.1137/120896773zbMath1321.94122arXiv1207.1140OpenAlexW2569444610MaRDI QIDQ5396950
Mahdi Cheraghchi, Ameya Velingker, Venkatesan Guruswami
Publication date: 4 February 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.1140
Gaussian processes (60G15) Linear codes (general theory) (94B05) Bounds on codes (94B65) Decoding (94B35) Sampling theory in information and communication theory (94A20)
Related Items
Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery ⋮ Derandomizing restricted isometries via the Legendre symbol ⋮ Sigma delta quantization with harmonic frames and partial Fourier ensembles ⋮ Compressive Sensing with Redundant Dictionaries and Structured Measurements ⋮ Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class ⋮ Interpolation via weighted \(\ell_{1}\) minimization ⋮ An Introduction to Compressed Sensing ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Fast binary embeddings with Gaussian circulant matrices: improved bounds ⋮ Unnamed Item ⋮ Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs ⋮ Fast and RIP-optimal transforms ⋮ The Restricted Isometry Property of Subsampled Fourier Matrices ⋮ Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing
