PULSE: Peelingbased UltraLow complexity algorithms for Sparse signal EstimationAn emerging challenge in recent years for engineers, researchers, and data scientists across the globe is to acquire, store, and analyze everincreasing amounts of data. In the past decade, a new paradigm in data acquisition called “compressedsensing” has emerged to cope with this data explosion. Compressed sensing exploits the fact that in many applications, although the signal of interest has a large ambient dimension, the relevant information resides in a significantly lower dimensional space. For example, the MagneticResonanceImaging (MRI) data is sparse in the waveletdomain. In this project, we consider the problem of computing a sparse DiscreteFourierTransform of a highdimensional signal from its timedomain samples, as a representative example of compressedsensing problems. We use this problem to investigate the tradeoff between the number of measurements, noise robustness, and the computational complexity of the recovery algorithm in compressed sensing problems. We propose a new family of deterministic sparse sensing matrices, obtained by blending together diverse ideas from sparse graph codes, digital signal processing, and numbertheoretic concepts like the Chineseremaindertheorem (CRT). The specific sparse structure of the proposed family of measurement matrices further enables a Peelingbased UltraLow complexity algorithms for Sparse signal Estimation, that are accordingly dubbed PULSE algorithms. Further, using the CRT, we establish an intimate connection between the problem of computing a sparse DFT of a signal and decoding over an appropriately designed sparse graph code. This connection is then exploited 1) to design a sample efficient measurement matrix and a lowcomplexity peelingstyle iterative recovery algorithm, and 2) to perform a rigorous analysis of the recovery algorithm by wielding powerful and wellestablished analytical tools like densityevolution, martingales, and expander graphs from the coding theory literature. In particular, we show that under some mild conditions a ksparse nlength DFT of a signal can be computed using (nearly optimal) 4k measurements and O(k log k) computations. As a concrete example, when k = 300, and n = 3.8 × 106, our algorithm achieves computational savings by a factor of more than 6000, and savings in the number of input samples by a factor of more than 3900 over the standard FastFourierTransform(FFT) algorithms. This can be a significant advantage in many existing applications and can enable new classes of applications that were not thought to be practical so far. Next, we extend these results to the case of noisecorrupted samples, computing sparse 2DDFTs as well as to interpolation of multivariate sparse polynomials over the complex field and finite fields. We also demonstrate an application of the proposed PULSE algorithm to acquire the MagneticResonanceImaging of the Brain. This provides some empirical evidence that PULSE algorithms are applicable for acquiring more realistic signals. The proposed sensing framework and the recovery algorithm are sample efficient and robust against observation noise. We believe that this framework provides a possible direction towards designing efficient and lowpower engineering solutions for sparse signal acquisition. Publications
