"Encoder Blind Combinatorial Compressed Sensing"Murray, MichaelIn 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 recovering a set of sparse codes from their measurement vectors, each generated using the same sparse, binary encoder matrix, but using a decoder which does not have access to the encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrix 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. |
| http://univie.ac.at/projektservice-mathematik/e/talks/Murray_2021-07_ICCHA_mmurray.pdf |
« back