Iterative subspace pursuit decoding of weighted Euclidean superimposed codes

We propose a new iterative algorithm, termed subspace pursuit (SP), for decoding of weighted Euclidean superimposed codes (WESCs). WESCs allow for unique identification of small subsets of codewords based on their superposition, and therefore can be viewed as a specialization of compressive sensing schemes. Motivated by various algorithms for compressive sensing reconstruction, we propose the SP algorithm that has both small computational complexity and high decoding accuracy. Our analysis shows that accurate decoding is guaranteed as long as the codeword matrix satisfies the restricted isometry property with a constant parameter. Also presented is an upper bound on the computational complexity of the algorithm.