Practical compressed sensing with log-of-prime projections

In this paper, we propose a new approach for compressed sensing of integer-valued signals using prime numbers. In particular, we utilize the logarithmic values of prime numbers to construct projection matrices that are capable of significant reductions in the number of observations (m) needed for the recovery of integer-valued signals when compared to leading compressed-sensing methods. At one extreme, and under ideal conditions, the proposed Log of Prime-numbers (LoP) projection enables single-observation compressed sensing, where one sample (m = 1) can be used for the recovery of a sparse signal with N original integer samples. More importantly, we design a practical LoP projection system and a corresponding low-complexity solver that only requires m = k observations, where k is the sparsity of the signal S in some space psi. We compare the performance of the proposed LoP system with popular Basis Pursuit (BP) and Orthogonal Matching Pursuit (OMP) methods, and demonstrate the significant improvements that can be achieved by utilizing LoP projection matrices.