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.
Among these works, the most recent progress in this direction is the sFFT (Sparse FFT) algorithm developed in the series of papers @cite_2 @cite_0 @cite_19 . Most of these algorithms are based on first isolating (i.e., hashing) the non-zero DFT coefficients into different bins, using specific filters or windows that have good' (concentrated) support in both time and frequency. The non-zero DFT coefficients are then recovered iteratively, one at a time. The filters or windows used for the binning operation are typically of length @math . As a result, the sample complexity is typically @math or more, with potentially large big-Oh constants as demonstrated in @cite_1 . Then, @cite_19 further improved the @math -D DFT algorithm for the special case of @math , which reduces the sample complexity to @math and the computational complexity to @math , albeit with a constant failure probability that does not vanish as the signal dimension @math grows. On this front, the deterministic algorithm in @cite_26 is shown to guarantee zero errors but with complexities of @math . More recently, @cite_4 develops a deterministic algorithm for computing a sparse WHT in time @math with an arbitrary constant @math .
@cite_26 @cite_4 @cite_1 @cite_0 @cite_19 @cite_2
2031425559 2950308398 1999763281 2107625832 2112094394 1501755821
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). For every fixed constant @math , we design an algorithm for computing the @math -sparse Walsh-Hadamard transform of an @math -dimensional vector @math in time @math . Specifically, the algorithm is given query access to @math and computes a @math -sparse @math satisfying @math , for an absolute constant @math , where @math is the transform of @math and @math is its best @math -sparse approximation. Our algorithm is fully deterministic and only uses non-adaptive queries to @math (i.e., all queries are determined and performed in parallel when the algorithm starts). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan, JACM 2009). Moreover, we design a deterministic and non-adaptive @math compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time @math (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk, Karloff, Strauss (Allerton 2008). Our methods use linear lossless condensers in a black box fashion; therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to @math reconstruction time with a reduced exponent in the poly-logarithmic factor, and eliminating the extra parameter @math ). Finally, by allowing the algorithm to use randomness, while still using non-adaptive queries, the running time of the algorithm can be improved to @math . A plug (20) has a base (22) in which a plurality of plug-side terminal fittings (50) are mounted and a lid portion (23) openably and closably mountable on the base (22). The base portion (22) includes a base-side shell (30) and a resin-made base-side housing (60) integrally formed with the base-side shell (30) by insert molding. Since the base-side housing (60) and the base-side shell (30) support each other while being held in close contact, a sufficient strength can be secured. Further, since it is not necessary to assemble the base-side housing (60) and the base-side shell (30), an assembling process can be simplified. We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: An O(k log n)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and An O(k log n log(n k))-time randomized algorithm for general input signals. Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k=o(n). They are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = nΩ(1). We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least Ω(k log (n k) log log n) signal samples, even if it is allowed to perform adaptive sampling. We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional √n × √n grid. Our algorithms are analyzed for the average case signals. For signals whose spectrum is exactly sparse, we present algorithms that use O(k) samples and run in O(k log k) time, where k is the expected sparsity of the signal. For signals whose spectrum is approximately sparse, we have an algorithm that uses O(k log n) samples and runs in O(k log2 n) time, for k = Θ(√n). All presented algorithms match the lower bounds on sample complexity for their respective signal models. We consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coefficients of the Fourier transform of x. The problem is of key interest in several areas, including signal processing, audio image video compression, and learning theory. We propose a new algorithm for this problem. The algorithm leverages techniques from digital signal processing, notably Gaussian and Dolph-Chebyshev filters. Unlike the typical approach to this problem, our algorithm is not iterative. That is, instead of estimating "large" coefficients, subtracting them and recursing on the reminder, it identifies and estimates the k largest coefficients in "one shot", in a manner akin to sketching streaming algorithms. The resulting algorithm is structurally simpler than its predecessors. As a consequence, we are able to extend considerably the range of sparsity, k, for which the algorithm is faster than FFT, both in theory and practice.