An asymptotic existence result on compressed sensing matrices

DOI10.1016/J.LAA.2015.02.010MaRDI QIDQ2347356zbMATH OpenOpenAlexFDO

Authors Padraig Ó Catháin, Darryn Bryant

Publication date 27 May 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingpairwise balanced designs

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) General harmonic expansions, frames (42C15) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: For any rational number $h$ and all sufficiently large $n$ we give a deterministic construction for an $nimeslfloorhnfloor$ compressed sensing matrix with $(el{l}_1,t)$-recoverability where $t=O(sqrtn)$. Our method uses pairwise balanced designs and complex Hadamard matrices in the construction of $epsilon$-equiangular frames, which we introduce as a generalisation of equiangular tight frames. The method is general and produces good compressed sensing matrices from any appropriately chosen pairwise balanced design. The $(el{l}_1,t)$-recoverability performance is specified as a simple function of the parameters of the design. To obtain our asymptotic existence result we prove new results on the existence of pairwise balanced designs in which the numbers of blocks of each size are specified.

Recommendations

• Deterministic construction of compressed sensing matrices over finite sets
• Deterministic construction of compressed sensing matrices from constant dimension codes
• Deterministic constructions of compressed sensing matrices based on optimal codebooks and codes
• Deterministic constructions of compressed sensing matrices
• Deterministic construction of compressed sensing matrices from codes

Cites work

• Algebraic design theory
• An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
• Compressed sensing
• Compressive sampling
• Deterministic constructions of compressed sensing matrices
• Explicit constructions of RIP matrices and related problems
• Finite Fields and Applications
• scientific article; zbMATH DE number 3981181 (Why is no real title available?)
• scientific article; zbMATH DE number 1382769 (Why is no real title available?)
• List decomposition of graphs.
• Lower bounds on the maximum cross correlation of signals (Corresp.)
• On the existence of equiangular tight frames
• Percentages in pairwise balanced designs
• Representations and characters of groups.
• Sparse Approximate Solutions to Linear Systems
• Stable signal recovery from incomplete and inaccurate measurements
• Steiner equiangular tight frames
• Strengthening hash families and compressive sensing
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Uncertainty principles and ideal atomic decomposition

Cited in

(6)

• Approximately strongly regular graphs
• A geometrical stability condition for compressed sensing
• Deterministic bounds for restricted isometry in compressed sensing matrices
• Trades in complex Hadamard matrices
• Uniform Recovery Bounds for Structured Random Matrices in Corrupted Compressed Sensing
• Limiting laws of coherence of random matrices with applications to testing covariance structure and construction of compressed sensing matrices

This page was built for publication: An asymptotic existence result on compressed sensing matrices

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