Sparse weighted Euclidean superimposed coding for integer compressed sensing

We address the problem of bounding the achievable rates of a new class of superimposed codes, termed weighted Euclidean superimposed codes (WESCs). WESCs generalize traditional Euclidean superimposed codes in so far that they allow for distinguishing bounded, integer-valued linear combinations of codewords. They can also be viewed as a bridge between superimposed coding and compressive sensing. In particular, we focus on sparse WESCs, for which one can devise low-complexity decoding algorithms and simple analytical constructions. Our results include a sufficient condition for meeting a minimum distance requirement of sparse WESCs, and a lower bound on the largest rate of sparse WESCs. Also included is a simple extension of DeVore's deterministic construction for sparse compressed sensing matrices that meets the derived lower bound.