An asymptotic existence result on compressed sensing matrices
Bryant, DarrynORCID: 0000-0002-1605-5343 and Ó Catháin, PadraigORCID: 0000-0002-7963-9688
(2015)
An asymptotic existence result on compressed sensing matrices.
Linear Algebra and its Applications, 475
.
pp. 134-150.
ISSN 0024-3795
For any rational number h and all sufficiently large n we give a deterministic construction
for an n × bhnc compressed sensing matrix with (`1, t) -recoverability where t = O(√n).
Our method uses pairwise balanced designs and complex Hadamard matrices in the construction of �-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 (`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.