  In its most elementary form, compressed sensing studies the design of
decoding algorithms to recover a sufficiently sparse vector or code from a
lower dimensional linear measurement vector. Typically it is assumed that the
decoder has access to the encoder matrix, which in the combinatorial case is
sparse and binary. In this paper we consider the problem of designing a decoder
to recover a set of sparse codes from their linear measurements alone, that is
without access to encoder matrix. To this end we study the matrix factorisation
task of recovering both the encoder and sparse coding matrices from the
associated linear measurement matrix. The contribution of this paper is a
computationally efficient decoding algorithm, Decoder-Expander Based
Factorisation, with strong performance guarantees. In particular, under mild
assumptions on the sparse coding matrix and by deploying a novel random encoder
matrix, we prove that Decoder-Expander Based Factorisation recovers both the
encoder and sparse coding matrix at the optimal measurement rate with high
probability and from a near optimal number of measurement vectors. In addition,
our experiments demonstrate the efficacy and computational efficiency of our
algorithm in practice. Beyond compressed sensing our results may be of interest
for researchers working in areas such as linear sketching, coding theory and
matrix compression.
