2013/05/03 by Sameer Pawar, Kannan Ramchandran, Pawar, Sameer +1 · 1 citation
Computer Science · Engineering · #VLSI and Analog Circuit Testing #Integrated Circuits and Semiconductor Failure Analysis #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1305.0870
Given an n-length input signal mbfx, it is well known that its\nDiscrete Fourier Transform (DFT), mbfX, can be computed in O(n \log n)\ncomplexity using a Fast Fourier Transform (FFT). If the spectrum mbfX is\nexactly k-sparse (where k<<n), can we do better? We show that\nasymptotically in k and n, when k is sub-linear in n (precisely, k\n\∝ n\δ where 0 < \δ <1), and the support of the non-zero DFT\ncoefficients is uniformly random, we can exploit this sparsity in two\nfundamental ways (i) bf sample complexity: we need only M=rk\ndeterministically chosen samples of the input signal mbfx (where r < 4\nwhen 0 < \δ < 0.99); and (ii) bf computational complexity: we can\nreliably compute the DFT mbfX using O(k \log k) operations, where the\nconstants in the big Oh are small and are related to the constants involved in\ncomputing a small number of DFTs of length approximately equal to the sparsity\nparameter k. Our algorithm succeeds with high probability, with the\nprobability of failure vanishing to zero asymptotically in the number of\nsamples acquired, M.\n