Compressed Sensing With Combinatorial Designs: Theory and Simulations

被引:11
|
作者
Bryant, Darryn [1 ]
Colbourn, Charles J. [2 ]
Horsley, Daniel [3 ]
Cathain, Padraig O. [4 ]
机构
[1] Univ Queensland, Sch Math & Phys, Brisbane, Qld 4072, Australia
[2] Arizona State Univ, Sch Comp Informat & Decis Syst Engn, Tempe, AZ 85287 USA
[3] Monash Univ, Sch Math Sci, Melbourne, Vic 3800, Australia
[4] Worcester Polytech Inst, Sch Math Sci, Worcester, MA 01609 USA
基金
美国国家科学基金会; 澳大利亚研究理事会;
关键词
Compressed sensing; combinatorial designs; signal recovery; SIGNAL RECOVERY; MATRICES; CONSTRUCTIONS;
D O I
10.1109/TIT.2017.2717584
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We use deterministic and probabilistic methods to analyze the performance of compressed sensing matrices constructed from Hadamard matrices and pairwise balanced designs, previously introduced by a subset of the authors. In this paper, we obtain upper and lower bounds on the sparsity of signals for which our matrices guarantee recovery. These bounds are tight to within a multiplicative factor of at most 4 root 2. We provide new theoretical results and detailed simulations, which indicate that the construction is competitive with Gaussian random matrices, and that recovery is tolerant to noise. A new recovery algorithm tailored to the construction is also given.
引用
收藏
页码:4850 / 4859
页数:10
相关论文
共 50 条
  • [1] Combinatorial algorithms for compressed sensing
    Cormode, Graham
    Muthukrishnan, S.
    2006 40TH ANNUAL CONFERENCE ON INFORMATION SCIENCES AND SYSTEMS, VOLS 1-4, 2006, : 198 - 201
  • [2] Combinatorial algorithms for compressed sensing
    Cormode, Graham
    Muthukrishnan, S.
    STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, PROCEEDINGS, 2006, 4056 : 280 - 294
  • [3] Flexible construction of measurement matrices in compressed sensing based on extensions of incidence matrices of combinatorial designs
    Liang, Junying
    Peng, Haipeng
    Li, Lixiang
    Tong, Fenghua
    Yang, Yixian
    APPLIED MATHEMATICS AND COMPUTATION, 2022, 420
  • [4] Derandomizing Compressed Sensing With Combinatorial Design
    Jung, Peter
    Kueng, Richard
    Mixon, Dustin G.
    FRONTIERS IN APPLIED MATHEMATICS AND STATISTICS, 2019, 5
  • [5] Encoder Blind Combinatorial Compressed Sensing
    Murray, Michael
    Tanner, Jared
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2022, 68 (12) : 8310 - 8341
  • [6] A Robust Parallel Algorithm for Combinatorial Compressed Sensing
    Mendoza-Smith, Rodrigo
    Tanner, Jared W.
    Wechsung, Florian
    IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2018, 66 (08) : 2167 - 2177
  • [7] Construction of Structured Random Measurement Matrices in Semi-Tensor Product Compressed Sensing Based on Combinatorial Designs
    Liang, Junying
    Peng, Haipeng
    Li, Lixiang
    Tong, Fenghua
    SENSORS, 2022, 22 (21)
  • [8] New designs of CT scanners and compressed sensing
    Kudo H.
    Kudo, Hiroyuki, 1600, Japan Society for Precision Engineering (82): : 506 - 512
  • [9] Blind Compressed Sensing: Theory
    Gleichman, Sivan
    Eldar, Yonina. C.
    LATENT VARIABLE ANALYSIS AND SIGNAL SEPARATION, 2010, 6365 : 386 - 393
  • [10] Simulations on the Combinatorial Structure of D-Optimal Designs
    Fontana, Roberto
    Rapallo, Fabio
    STATISTICS AND SIMULATION, IWS 8 2015, 2018, 231 : 343 - 353