An analog sub-linear time sparse signal acquisition framework based on structured matrices

Advances in compressed-sensing (CS) have sparked interest in designing information acquisition systems that process data at close to the information rate. Initial proposals for CS signal acquisition systems utilized random matrix ensembles in conjunction with convex relaxation based signal reconstruction algorithms. While providing universal performance bounds, random matrix based formulations present several practical problems due to: the difficulty in physically implementing key mathematical operations, and their dense representation. In this paper, we present a CS architecture which is based on a sub-linear time recovery algorithm (with minimum memory requirement) that exploits a novel structured matrix. This formulation allows the use of a reconstruction algorithm based on relatively simple computational primitives making it more amenable to implementation in a fully-integrated form. Theoretical recovery guarantees are discussed and a hypothetical physical CS decoder is described.