The exact recovery with sub-exponential measurement matrix

2025/06/22 by Tiankun, Dai Guozheng Diao
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2506.17965

Abstract

Let A be an m × n random matrix, where each entry is an i.i.d.sub-exponential random variable with mean 0 and variance (1)/(m²). We demonstrate that, with high probability, the sub-exponential matrix A can be used for the exact reconstruction of s-sparse vectors via ℓ₁-minimization, provided that m ≥ C₁ s log((C₂ n)/(s)). This improves upon the existing results by Adamczak et al.

Citations

• The Restricted Isometry Property of Block Diagonal Matrices for Group-Sparse Signal Recovery
• Suprema of Chaos Processes and the Restricted Isometry Property
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Decoding by Linear Programming
• Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information

Related

• Sublinear Time, Approximate Model-based Sparse Recovery For All
• Nonuniform Sparse Recovery with Subgaussian Matrices
• Recovery of sparsest signals via ℓ^q-minimization
• On the gap between RIP-properties and sparse recovery conditions
• Improved bounds for sparse recovery from subsampled random convolutions