  The problem of how to find a sparse representation of a signal is an
important one in applied and computational harmonic analysis. It is closely
related to the problem of how to reconstruct a sparse vector from its
projection in a much lower-dimensional vector space. This is the setting of
compressed sensing, where the projection is given by a matrix with many more
columns than rows. We introduce a class of random matrices that can be used to
reconstruct sparse vectors in this paradigm. These matrices satisfy the
restricted isometry property with overwhelming probability. We also discuss an
application in dimensionality reduction where we initially discovered this
class of matrices.
