We consider the problem of computing the Walsh-Hadamard Transform (WHT) of some @math -length input vector in the presence of noise, where the @math -point Walsh spectrum is @math -sparse with @math scaling sub-linearly in the input dimension @math for some @math . Over the past decade, there has been a resurgence in research related to the computation of Discrete Fourier Transform (DFT) for some length- @math input signal that has a @math -sparse Fourier spectrum. In particular, through a sparse-graph code design, our earlier work on the Fast Fourier Aliasing-based Sparse Transform (FFAST) algorithm computes the @math -sparse DFT in time @math by taking @math noiseless samples. Inspired by the coding-theoretic design framework, proposed the Sparse Fast Hadamard Transform (SparseFHT) algorithm that elegantly computes the @math -sparse WHT in the absence of noise using @math samples in time @math . However, the SparseFHT algorithm explicitly exploits the noiseless nature of the problem, and is not equipped to deal with scenarios where the observations are corrupted by noise. Therefore, a question of critical interest is whether this coding-theoretic framework can be made robust to noise. Further, if the answer is yes, what is the extra price that needs to be paid for being robust to noise? In this paper, we show, quite interestingly, that there is no extra price that needs to be paid for being robust to noise other than a constant factor. In other words, we can maintain the same sample complexity @math and the computational complexity @math as those of the noiseless case, using our SParse Robust Iterative Graph-based Hadamard Transform (SPRIGHT) algorithm.
Due to the similarities between the DFT and the WHT, we give a brief account of previous work on reducing the sample and computational complexity of obtaining a @math -sparse @math -point DFT. The most related research thread in the literature is the computation of sparse DFT using theoretical computer science techniques such as sketching and hashing (see @cite_13 @cite_17 @cite_26 @cite_16 @cite_20 ). Most of these algorithms aim at minimizing the approximation error of the DFT coefficients using an @math -norm metric instead of exact support recovery (i.e., @math -norm).
@cite_26 @cite_16 @cite_13 @cite_20 @cite_17
2031425559 2113204179 2012365979 2146509513 2589910859
We study the problem of estimating the best k term Fourier representation for a given frequency sparse signal (i.e., vector) A of length N≫k. More explicitly, we investigate how to deterministically identify k of the largest magnitude frequencies of @math , and estimate their coefficients, in polynomial(k,log N) time. Randomized sublinear-time algorithms which have a small (controllable) probability of failure for each processed signal exist for solving this problem ( in ACM STOC, pp. 152–161, 2002; Proceedings of SPIE Wavelets XI, 2005). In this paper we develop the first known deterministic sublinear-time sparse Fourier Transform algorithm which is guaranteed to produce accurate results. As an added bonus, a simple relaxation of our deterministic Fourier result leads to a new Monte Carlo Fourier algorithm with similar runtime sampling bounds to the current best randomized Fourier method ( in Proceedings of SPIE Wavelets XI, 2005). Finally, the Fourier algorithm we develop here implies a simpler optimized version of the deterministic compressed sensing method previously developed in (Iwen in Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA’08), 2008). We present a randomized algorithm that interpolates a sparse polynomial in polynomial time in the bit complexity model. The algorithm can be also applied to approximate polynomials that can be approximated by sparse polynomials (the approximation is in the @math norm). (MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N, such that @math is within the factor (1 +e) of best possible @math . Our algorithm can access A by reading its values on a sample set T ⊆[0,N), chosen randomly from a (non-product) distribution of our choice, independent of A. That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log(N)log(M)e (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples. This article describes a computational method, called the Fourier sampling algorithm. The algorithm takes a small number of (correlated) random samples from a signal and processes them efficiently to produce an approximation of the DFT of the signal. The algorithm offers provable guarantees on the number of samples, the running time, and the amount of storage. As we will see, these requirements are exponentially better than the FFT for some cases of interest.