Fast Partial Fourier Transform
Authors: Yong-chan Park
Jun-Gi Jang
U Kang
Venue:  (2021)
Keywords: Fourier transform
time series
signal processing
anomaly detection
machine learning

Abstract: Given a time-series vector, how can we efficiently compute a specified part of Fourier coefficients? Fast Fourier transform (FFT) is a widely used algorithm that computes the discrete Fourier transform in many machine learning applications. Despite the pervasive use, FFT algorithms do not provide a fine-tuning option for the user to specify one’s demand, that is, the output size (the number of Fourier coefficients to be computed) is algorithmically determined by the input size. Such a lack of flexibility is often followed by just discarding the unused coefficients because many applications do not require the whole spectrum of the frequency domain, resulting in an inefficiency due to the extra computation. 
In this paper, we propose a fast Partial Fourier Transform (PFT), an efficient algorithm for computing only a part of Fourier coefficients. PFT approximates a part of twiddle factors (trigonometric constants) using polynomials, thereby reducing the computational complexity due to the mixture of many twiddle factors. We derive the asymptotic time complexity of PFT with respect to input and output sizes, as well as its numerical accuracy. Experimental results show that PFT outperforms the current state-of-the-art algorithms, with an order of magnitude of speedup for sufficiently small output sizes without sacrificing accuracy.

Under review as a conference paper at ICLR 2021
FAST PARTIAL FOURIER TRANSFORM
Anonymous authors
Paper under double-blind review
ABSTRACT
Given a time-series vector, how can we efficiently compute specified part of Fourier coefficients? Fast Fourier transform (FFT) a widely used algorithm that computes the discrete Fourier transform in many machine learning applications. Despite the pervasive use, FFT algorithms do not provide fine-tuning option for the user to specify one's demand, that is, the output size (the number of Fourier coefficients to be computed) is algorithmically determined by the input size. Such a lack of flexibility is often followed by just discarding the unused coefficients because many applications do not require the whole spectrum of the frequency domain, resulting in an inefficiency due to the extra computation.
In this paper, we propose fast Partial Fourier Transform (PFT), an efficient algo- rithm for computing only part of Fourier coefficients. PFT approximates a part of twiddle factors (trigonometric constants) using polynomials, thereby reducing the computational complexity due to the mixture of many twiddle factors. We de- rive the asymptotic time complexity of PFT with respect to input and output sizes, as well as its numerical accuracy. Experimental results show that PFT outperforms the current state-of-the arrt algorithms, with an order of magnitude of speedup for sufficiently small output sizes without sacrificing accuracy.
INTRODUCTION
How can we efficiently compute a specified part of Fourier coefficients of a given time-series vector? Discrete Fourier transform (DFT) is a crucial task in several application areas, including anomaly detection (Hou & Zhang (007); Rasheed et al. (2009); Ren et al. (2019)), data center monitoring (Mueen et al. (2010)) and image processing (Shi et al. (2017)). Notably, in many such applications, it is well known that the DFT results in strong "energy- coangyyycomaattion or "sparsity" in the frequency domain. That is, the Fourier coefficients of data are mostly small or equal to zero, having much smaller support compared to the input size. Moreover, the support can often be specified in practice (e.g., few oow-frequeccy coefficients around the origin). These observations arouse great interest in an efficient algorithm capable of computing only a specified part of Fourier coefficients. Ac- cordingly, various approaches have been proposed to address the problem, which include Goertzel algorithm (Burrus & Parks (1985)) Subband DFT (Hossen et al. al.[ (1995)][Seentee)) et al. (1995)) ), and Pruned FFT (Markel (1971): Skinner
(9766]
Nagai (186)] Sorensen & Burrus (1993): Ailon &
Liberty (009)).
In this paper, we propose a fast Partial Fourier Transform (PFT), an efficient algorithm for com- puting part of Fourier coefficients. Specifically, we consider the following problem: given complex-valued vector a of size N, a non-negative integer M, and an integer J4, estimate the Fourier coefficients of a for the interval [μ M, yu + M). The resulting algorithm is of remarkably simple structure, composed several "smaller" FFTs combined with linear pre- and post- post-processing steps. Consequently, PFT reduces the number of operations to O(N + M log M), which is, to the best of our knowledge, the lowest arithmetic complexity achieved so far. Besides that, most subroutines of PFT are the already highly optimized algorithms (e.g., matrix multiplication and FFT), thus the arithmetic gains are readily turned into actual run-time improvements. Furthermore. PFT does not require the input size to be a power of 2, unlike many other competitors. This is because the idea of PFT derives from a modification of the Cooley-Tuker, algorithm (Cooley & Tukey 1965), which also makes it straightforward to extend the idea to a higher dimensionality.
Through experiments, we show that PFT outperforms the state-ofthhe of-the-art FFT libraries, FFTW by Frigo & Johnson (2005) and Intel Math Kernel Library (MKL) as well as Pruned FFTW, with an order of magnitude of speedup without sacrificing accuracy.

---

Under review as a conference paper at ICLR 2021
2 RELATED WORK
We describe various existing methods for computing partial Fourier coefficients.
Fast Fourier transform. One may consider just using Fast Fourier transform (FFT) and discarding the unnecessary coefficients, where FFT efficiently computes the full DFT, reducing the arithmetic cost from naïve O(N²) to ON log N).. Such an approach has two major advantages: (1) it is straightforward implement, and (2) the method often outperforms the competitors because it di- rectly employs FFT which has been highly optimized over decades. Therefore, we provide extensive comparisons of PFT and FFT both theoretically and through run-time evaluations. Experimental results in Section 4.2 show that PFT outperforms the FFT when the output size is small enough (< 10%) compared to the input size.
Goertzel algorithm. Goertzel algorithm (Burrus& & Parks 1985) is one of the first methods devised for computing only a part of Fourier coefficients. The technique is essentially the same as comput- ing the individual coefficients of DFT, thus requiring ((MN) operations for M coefficients of an input of size N. Specifically, theoretical analysis represents "the M at which the Goertzel algorithm advantageous over FFT as M < 2 log N (Sysel & Rajmic (012)). For example, with N = 2 the Goertzel algorithm becomes faster than FFT only when M < 44, while PFT outperforms FFT for .M- 219 524288 (Figure lb). A few variants which improve the Goertzel algorithm have been proposed (e.g.. Boncelet ). Nevertheless, the performance gain is only by a small con- stant factor, thus they are still limited to rare scenarios where a very few number of coefficients are required.
Subband DFT. Subband DFT (Hossen et al. (1995); Shentov et al. (1995)) consists of two stages of algorithm: Hadamard transform that decomposes the input sequence into set of smaller subse- quences, and correction stage for recombination. The algorithm approximates a part of coefficients by eliminating subsequences with small energy contribution, and manages to reduce the number of operations to O(N + M log N). Apart from the arithmetic gain, however, there is a substantial issue of low accuracy with the Subband DFT. Indeed, experimental results in Hossen al. (1995) show that the relative approximation error of the method is around 10-1 (only one significant figure) regardless of output size. Moreover, the Fourier coefficients can be evaluated arbitrary numerical precision with PFT, which is not the case for Subband DFT. Such limitations often preclude one from considering the Subband DFT in applications that require a certain degree of accuracy.
Pruned FFT. FFT pruning (Markel (197I); Skinner 1976);; Nagai (986);; Sorensen & Burrus [1993] Ailon & Liberty (2009) is another technique for the efficient computation of partial Fourier coefficients. The method modification of the standard split-radix FFT, where the edges (opera- tions) in flow graph are pruned away if they do not affect the specified range of frequency domain. Besides being almost optimized (it uses FFT as subroutine), the FFT pruning algorithm is exact and reduces the arithmetic cost to ONN log M). Thus, along with the full FFT, the pruned FFT is reasonably the most appropriate competitor of PFT. Through experiments (Section 4.2). we show that PFT consistently outperforms the pruned FFT, significantly extending the range of output sizes for which partial Fourier transform becomes practical.
Finally, we mention that there have been other approaches but with different settings. For example, Hassanich et al.] (2012a]b) and Indyk et al. (2014) propose Sparse Fourier transform, which esti- mates the top-k (the ls largest in magnitude) Fourier coefficients of a given vector. The algorithm is useful especially when there is prior knowledge of the number of non-zero coefficients in frequency domain. Note that our setting does not require any prior knowledge of the given data.
Applications of FFT. We outline various applications of Fast Fourier transform, to which partial Fourier transform can potentially be applied. FFT has been widely used for anomaly detection (Hou & Zhang (007): ;; Rasheed et al. (2009) et al. (201)). HHou & Zhang (2007) and Ren et al. (2019)
detect anomalous points of a given data by extracting compact representation with FFT, Rasheed et al. (2009) use FFT to detect local spatial outliers which have similar patterns within region but different patterns from the outside. Several works (Pagh 2013); Pham & Pagh (013)) Malik
& Becker (2018)) exploit FFT for efficient operations. Pagh (2013) leverages FTT to efficiently compute a polynomial kernel used with support vector machines (SVMs). Malik & Becker (2018) propose an efficient tucker decomposition method using FFT. In addition, FFT has been used for fast training of convolutional neural networks (Mathicu et al. (2014); Rippel et al. (2015) and an efficient recommendation model heterogeneous graph (Jin al. 2020)).
2

---

Under review as a conference paper at ICLR 2021
3 PROPOSED METHOD
3.1 OVERVIEW
We propose PFT, an efficient algorithm for computing a specified part of Fourier coefficients. The main challenges and our approaches are as follows:
1.
How can we extract essential information for specified output? Considering that only a specified part of Fourier coefficients should be computed, we need to find an algorithm requiring fewer operations than the direct use of conventional FFT. This is achievable by carefully modifying the Cooley-Tukey algorithm, finding twiddle factors (trigonometric factors) with small oscillations, and approximating them via polynomials (Section 3.2.I).
2. How can we reduce approximation cost? The approach given above involves an approx- imating process, which would be computationally demanding. We propose using base exponential function, by which all data-independent factors can be precomputed, enabling to bypass the approximation problem during the run-time (Sections 3.2.2 (...2 and 3.3)
3. How can we further reduce numerical computation? We carefully reorder operations and factorize terms in order alleviate the complexity of PFT. Such techniques separate all lata-independent factors from data-dependent factors, allowing further precomputation. The arithmetic cost of the resulting algorithm O(N + M log M). where N and M are input and output size descriptors, respectively (Sections 3.4 and 3.5.1.
3.2 APPROXIMATION OF TWIDDLE FACTORS
The key of our algorithm is approximate a part of twiddle factors with small oscillations by using polynomial functions, reducing the computational complexity of DFT due to the mixture of many twiddle factors. Using polynomial approximation also allows one to carefully control the degree of polynomial (or the number of approximating terms), enabling fine-tuning the output range and the approximation bound of the estimation. Our first goal is to find a collection of twiddle factors with small oscillations. This can be achieved by slightly adjusting the summand of DFT and splitting the summation as in the Cooley-Tukey algorithm (Section 3.2.1). Next, using a proper base exponential function, we give an explicit form of approximation to the twiddle factors (Section 3.2.2
3.2.1 TWIDDLE FACTORS WITH SMALL OSCILLATIONS
Recall that the DFT of a complex-valued vector a of size N is defined as follows:
am
Σ
age -2mimm/N
(1)
nE[N]
where [r] denotes {0, , -V- 1} for a positive integer v (in this paper, we follow the convention of viewing a vector = (vo, 01 ... 11--1 of size v as a finite sequence defined on [v)). Assume
that N = pq for two integers p, q > 1. The Cooley-Tukey algorithm re-expresses (I) as
am Σ>
agk+1e 2rim(gh+0//N
-EX Σ
O 2mimt/NN e -2rimk/p
AE(P) 4E(0)
yielding two collections of twiddle factors, namely {e- 2o--mmmm// sider the problem of computing åm for -M S negative integer. In this case, note that the exponent of e -2rimi/N ranges from -2riM 1)/N to +2TiM 1)/N and that the exponent of e 22rimk/p ranges from -2riM 1)/p to +2riM - 1)/p. Here (g-1)/ (p-1)/p J. meaning that the first collection contains twiddle factors with smaller oscillations compared to the second one. Typically, a function with smaller oscillation results in better approximation via polynomials. In this sense, it reasonable approximate the first collection of twiddle factors in (2) with polynomial functions, thereby reducing the complexity of the computation due the mixture two collections of twiddle factors. Indeed, one can further reduce the complexity of approximation: we slightly adjust the summand in (2) as follows.
Jelll and {e (e-2mimk/pp kelp)- Con- M, where M S N/2 is
dm = e wim/p
ΣX Σ
agk+ze 21imml (omml1g//2) g/2)/N -2rimk//p
KE(P! LE
In 3b, we observe that the range of exponents of the first collection (c-2rtm((-o/2)// ( of twiddle factors is [ MiMM M/pl contraction by factor of around when compared with 22 1)/N, +2riM 1)/N] hence the twiddle factors with even smaller oscillations. There is an extra twiddle factor e sim/p in 3). Note that, however, it depends on neither & nor I, so the amount of the additional computation is relatively small.
3

---

Under review as a conference paper at ICLR 2021
3.2.2 BASE EXPONENTIAL FUNCTION
The first collection of twiddle factors in (3) consists of q distinct exponential functions. One can apply approximation process for each function in the collection; however, this would be time- consuming. A more plausible approach to I) choose a base exponential function e for fixed R. 2) approximate euiar using polynomial, and 3) exploit a property of exponential functions: the laws of exponents. Specifically, suppose that we obtained a polynomial P(x) that approximates euiz |x|| S [g], where u, & IR {0). Consider another exponential function e where * O. Since ~ e eui(v//u), the re-sed polynomial P(ez/// uu) approximates evir on |a|| S |ug/u]. This observation indicates that once we find an approximation P to e on |a|| I [E] for properly se- lected u and Ç. all elements belonging to {e 2ximm( hEly) can be approximated by re-scaling P. Fixing base exponential function also enables precomputing a polynomial that approximates it, so that one can bypass the approximation problem during the run-time. We further elaborate this idea in rigorous manner after giving few definitions (see Definitions
3.1 and 3.2
Let || || be the uniform norm (or supremum norm) restricted to a set R S IR that is, ||l sf) x E R} and P. be the set of polynomials on R of degree at most a.
Definition 3.1. Given non-negative integer a and non-zero real numbers &, u, we define a polyno- mial Pa.ç,u as the best approximation to e e out of the space Pa under the restriction |x:| S [g]:
Pa.g. == arg min P(x)) - e 2 |||
PEP.
and P Pa.g.u = when { = 0r =
Smirnov Smirnov (1999) proved the unique existence of Pa..... A few techniques called minimax approximation algorithms for computing the polynomial are reviewed in Fraser (1965).
Definition 3.2. Given a tolerance > 0 and a positive integer 2 1. we define g(c, r) to be the scope about the origin such that the exponential function eir can be approximated by a polynomial of degree less than r with approximation bound
E(c,r) == sup 2 0: [IP--1e,- e || S c).
We express the corresponding polynomial as Pr-1, = ΣjE(r) werr-1,j .
In Definition 3.2
we choose wi as base exponential function. The rationale behind is as fol- lows. First, using a minimax approximation algorithm, we precompute E(E,r) and (wer-1s)jem for several tolerance e's (e.g. 10-1, 10-2 10- )) and positive integer r's (typically 1 S r I 25). .....) When N, M, p and are given, we find the minimum r satisfying E(e, 2 M/p. Then, by the pre- ceding argument, it follows that the re-scaled polynomial function P P)-1.g(e.m),a (-2x(1 - 2/2)/N) M for each / [q] (note that if 9/2
approximates 22rin(1g/////N on |x|| S
120
N
9/2)
ش M| > M for all ( E [g]. Therefore, obtain a polynomial approximation on (ml & M for each twiddle factor in {e 20/mmm(11//2)/ )((())
have 2/2) E co). Here 2[[-q/2
-
namely (Pr- (- - q/2)/N))ee) Then, it follows from (3) that
am -mim/p
ΣΣ agk+t P Pr- (-2m(1 q/2)/N) 2ximk/p,
(4)
kE(p)
which gives an estimation of the coefficient åm for - -M S S M.
3.3 ARBITRARILY CENTERED TARGET RANGES
In the previous section, we have focused on the problem of calculating âm for m belonging to [-M, M). We now consider more general case: let us use the term target range to indicate the range where the Fourier coefficients should be calculated, and Ry.M to denote [μ M, M] Z, where μ E Z. Note that the previously given method works only when our target range is centered at
a 0. A slight modification of the algorithm allows the target range to be arbitrarily centered. One possible approach is as follows: given a complex-valued vector æ of size N, we define y as yn
In e 2.ripnnNN Then, the Fourier coefficients of x and y satisfy the following relationship: fm+pp
Om
Σ In -
2ripp/NN 2wimnn/N
Σ In 2ri(m=+))//N
RE[N]
RE(N]
Thus, the problem of calculating &.n for m E Ry M is equivalent to calculating 9.. for m E Ro to which previous method can be applied. This technique, however, requires extra N multiplica-
4

---

Under review as a conference paper at ICLR 2021
tions due to the computation of y. A better approach, where one bypass the extra process during the run run-time, is to exploit the following lemma (see Appendix A.1 for the proof).
Given non-negative integer a, non-zero real numbers E, u, and a real number je, the following equality holds:
Lemma 1.
mip Paggul - (4) arg min [| - e uir 11
PEP.
This observation implies that, in order to obtain polynomial approximating exénn on la: pu| S [c), we first find polynomial P approximating e eui on |a]| < (E), then translate P by -1 and multiply it with the scalar uip Applying this process to the previously obtained approximation polynomi-
als (see Section 3.2.2) yields (e-2aiu(l-a/2/// ( (-2(m 12) g/2)/N) We
substitute these polynomials for the twiddle factors {e (e-2nim(-q/22//> ]et 3 which gives the
following estimation of am for m E Ry,M where [p], E [q]. and j E [r]:
wommp
ayk++ e 2/2)(1 Pr-I,E(er)) ( (-2(m - (1) /N)) 2wimk/p
xim/p
Og e 9/2//N
Σ We (-2(m - 10-mm-1){
- //22)//)/1)))) 2nimk/p
(5)
-imm/p
ΣΣ
Wer--1 ((m- - u)/p)) (1-21/))) . 2nink/p
agk+t e
3.4 EFFICIENT SUMMATIONS
We have found that three main summation steps (each being over j. k and 1) take place when com- puting the partial Fourier coefficients. Note that ( the innermost summation E, is moved to the outermost position, and the term -2(m - (1) //2)/N factorized into two independent terms, (m 4)/p and 1 21/g. Interchanging the order of summations and factorizing the term result in a significant computational benefit; we elucidate what operator we should utilize for each summation and how
save the arithmetic costs from it. As we will see, the innermost I corresponds to a matrix multiplication, the second sum over & can be viewed as multiple DFTs, and the outermost over is an inner product. For the first sum, let A (ax,)) ag and B- (br_)) 22rpp(1 (acip((l//21]) 4/2//N Wer-11 (1 21/9)", so that (5) can be written as follows:
over
-xim/p
Σ
-2romm//p
Σ ag.bb...
kEIP!
LElg]
Here, note that the matrix B is data-independent (not dependent on a). and thus can be precom- puted. Indeed, we have already seen that (werr-1.h can be precomputed. The other fac- tors e e2rrj((1-//2// and (1 21/q)² composing the elements of B also be precomputed if LN,M,, p. p.p.p) is known in advance. Thus, as long as the setting (NV M, μ. p, e) is unchanged, we reuse the matrix B for any input data once the configuration phase of PFT is completed (Algorithm Th. We shall denote the multiplication x B as = (Ck.j):
Tim/p Σ
((m-H))pp)
Σ Ck. E 22rimk/p.
(6)
JEI
kE(P)
For each j [r]. the summation Cmj = EkE(n) CR. 22rimk/p is DFT of size p. We perform FFT r times for this computation, which yields the following estimation of âm for m Ry,M:
e -wimmp Σ(mm ((m-))/p) -mm.j-
jEIr]
Note that Em.j is a periodic function of period p with respect to m, so we use the coefficient m modulo p if m product of (m p)) p)/p)² and Čm. with respect to j. followed by a multiplication with the extra twiddle factor e c-mm (we also precompute ((m /)/p)" and e e-mim/v). The full computation is outlined in Algorithm 2 By these summation techniques, the arithmetic complexity reduced to O(N + M log M) from naïve O(MN), as described in Section 3.5
m 2 p. Thus, the mh Fourier coefficient of a can be estimated by the inner
3.5 THEORETICAL ANALYSIS
We present theoretical analysis the time complexity of PFT and its approximation bound.
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1:
Configuration phase of PFT
input Input size N, output descriptors M and p. divisor p. and tolerance
output: Matrix B, divisor p. and numbers of rows and columns, g and
4 N/p
are < minfr E E:: [(c,r) M/p)
Use precomputed f(e,r)
for (1, E [g] x [r] do
B[,j]] t 2:sp(t- wer-1i (1- 21/4)/ // Use precomputed w
end
Algorithm 2: Computation phase of PFT
input Vector a of size N. output descriptors M and j., and configuration results B, p.P. q,
output: Vector E()) of estimated Fourier coefficients of a for [e M, 1 + M]
A[K, f- tgg+t1 for & [p) and E [4]
C A B
for j [r] do
Cl:5] FFT((C]:.))
11 FFT of j-th column of C
end
for
E -u- M₁ M] do [m]][m] e mim//p (mm Om.
end
3.5.1 TIME COMPLEXITY
We analyze the time complexity of PFT. Theorem 2 (see Appendix A.2 for the proof) shows that the time cost T(N, M) of PFT, where N and M are input and output size descriptors, respectively, bounded by Ó(N + M log M). Note that the theorem presumes that all prime factors N have fixed upper bound. Yet, in practice, this necessity is not big concern because control the input size with basic techniques such as zero-past vero-padding or re-sampling. Moreover, we empirically find that (see Section (.2). In Theorem 2 note that a positive integer called b-smooth none of its prime factors is greater than For example, the 2-smooth integers are equivalent the powers 2.
readily
if N has large prime factor, PFT still shows promising performance
Theorem 2. Fix tolerance > O and an integer b 2 2. If N is b-smooth, then the time complexity T(N, M) of PFT has an asymptotic upper bound O(N M log M).
3.5.2 APPROXIMATION BOUND
We now give a theoretical approximation bound the estimation via the polynomial P. We denote the estimated Fourier coefficient of a E(a). Theorem (see Appendix A.33 for the proof) states that the approximation bound over the target range is data-dependent of the total weight |al|] of the original vector and the given tolerance e, where
(A.3
denotes the & norm.
Theorem 3. Given a tolerance > 0, the following inequality holds for PFT:
la E())ll I ||aal1
4 EXPERIMENTS
Through experiments, the following questions should be answered:
Q1. Run-time cost (Section 4.2). How quickly does PFT compute part of Fourier coef-
ficients compared to other competitors without sacrificing accuracy?
Q2. Effect of hyper-parameter (Section 4.3). How do the different choices of divisor of input size N affect the overall performance PFT?
Q3. Effect of different precision (Section 4.4). How do the different precision settings
affect the run-time of PFT?
Q4. Anomaly detection (Section4, 4.5). How well does PFT work for a practical application employing FFT (anomaly detection)?
4.1 EXPERIMENTAL SETUP
Machine. machine with Intel Core 17-6700HQ @ 2.60GHz and 8GB of RAM is used.
Datasets. We use both synthetic and real-world datasets listed in Table

---

Under review as a conference paper at ICLR 2021
Table 1: Detailed information of datasets.
Dataset
Type
Size
Description
{S |
Synthetic
2
Vectors of random real numbers between and 1
Urban Sound
Real-world
32000
Various sound recordings in urban environment
Air Condition
Real-world
19735
Time-series vectors of air condition information
Competitors. We compare PFT with two state-of-the-arr FFT algorithms, FFTW and MKL, as well as Pruned FFTW. All of them are implemented in C++.
1. FFTW: FFTW is one of the fastest public implementation for FFT, offering a hardware-
specific optimization. We use the optimized version of FFTW 3.3.5, and do not include the pre- pre-processing for the optimization as the run- run-time cost.
2. MKL: Intel Math Kernel Library
a library of optimized math routines including FFT, and often shows a better run time result than the FFTW. All the experiments are conducted with an Intel processor for the best performance.
(MKL) (MKLL)
3. pFFT: pFFT is pruned version of FFTW designed for fast computation of a subset of the outputs. The algorithm uses the optimized FFTW as a subroutine.
4. PFT (proposed): we use MKL BLAS routines for the matrix multiplication, MKL DFTI functions for the batch FFT computation, and Intel Integrated Performance Primitives (IPP) library for the post-processing steps such inner product and element-wise multiplication.
Measure. In all experiments, we use single-precision floating-point format, and the parameters p and are chosen so that the relative lg error is strictly less than 10 which ensures that the overall estimated coefficients have at least 6 significant figures. Explicitly,
EmER Jām E(
Relative l Error
10-6
ΣMER iām 1
where à is the actual coefficient, E(a) ()) is the estimation of â, and R is the target range. Section 4.4 an exception, where we investigate different settings, varying the precision to 10 or 10-2.
4.2 RUN-TIME COST
Run time vs. input size. We fix the target range Ro and evaluate the run time of PFT vs. input sizes N 22 228 2 Figure[Ia[showe how the four competitive algorithms scale with varying input size, wherein PFT outperforms the others if the output size is sufficiently smaller (< 10%) than the input size. Consequently, PFT achieves up 19x speedup compared to its competitors. Due to the overhead of the O(N) pre- and ((M) post-processing steps, PFT runs slower than FFT when M close to N so the time complexity tends to O(N + N log N).
Run time vs. output size. We fix the input size to N = 22 and evaluate the run time of PFT vs. target ranges 2,,25, Ro,210, .... Ro,21s The result is illustrated as a run time vs. output size plot (recall that [ 2M) in Figure Ib] Note that the run times of FFTW and MKL do not benefit from the information of output size. We also observe that the pruned FFT (pFFT) shows only a modest improvement compared to the full FFTs, while PFT significantly extends the range of output sizes for which partial Fourier transform becomes practical.
Real-world data. When comes to real-world data, it is not generally the case that the size of an input vector is a power of 2. Notably, PFT still shows promising performance regardless of the fact that the input size is not a power of 2 or even has large prime factor: a strong indication that proposed technique is robust for many different applications in real-world. Urban Sound dataset contains various sound recording vectors of size N 32000 = 2 x 53. We evaluate the run time of PFT vs. output size ranging from 100 to 6400. Figure 2a illustrates the result, wherein PFT outperforms the competitors if the output size is small enough compared to the input size. On the other hand, Air Condition dataset composed of time-scries vectors of size N 19735 x 3947. Note that N has only two non-trivial divisors, namely 5 and 3947, forcing one to choose p 3947 in any practical settings; if we choose p 5, the ratio M/p often turns out to be too large, which
http://ww..fw..rr//neeex.
http://offfarre.nteel..o///
http://ww..Foo.orrr/omnned

---

Under review as a conference paper at ICLR 2021
(a)
Run time Input size (Target range: Ro.2*)
(b)
Run time Output size (Input size: 203)
PFT (proposed)
PFFT
18
Run time (ms)
X: FFTW
Run time (ms)
MKL
19
0.1
10.2x
PFT
pFFT
0.01
FFTW
MKL
2
2
26
2
2
2
2
2
24
25
2
2
2
2
2
Input size
Output size
Figure 1: (a) Run time vs. input size for target range R0 with {S,) n== datasets, and (b) run time vs. output size for S22. PFT runs faster than the competitors if the output size small enough (< 10%) compared to the imput size. Note that PFT consistently outperforms the pruned FFT.
(a)
Run time vs. Output size (N=32000)
(b)
Run time vs. Output size (N=19735)
2
Run time (ms)
2-
Run time (mm)
2-
2-a
8.8
PFT
2-
5.2x
PFT
2'
pFFT
FFTW
FFTW
2-
0
MKL
2a
MKL
100
200
400
800
1800
3200
8400
125
250
500
1000
2000
4000
8000 16000
Output
Output size
Figure 2: Run time vs. output size results for (a) Urban Sound dataset and (b) Air Condition dataset. PFT outperforms the competitors regardless of the fact that the input size is not power of 2 (N = 2 x 58) or even it has a large prime factor (N = 5 x 3947).
results in a poor performance (see Section 4.3 for more discussion of the optimal choice of p). The run time of PFT vs. output size ranging from 125 to 16000 is evaluated in Figure 2b (pFFT is not included in the figure since it consistently runs slower than FFTW). is noteworthy that PFT still outperforms its competitors even in such pathological examples, implying the robustness of our algorithm for various real-world situations.
4.3 EFFECT OF EYPER-PARAMETER P
To investigate the effect of different choices of we fix N = 222 and vary the ratio M/p from 1 1/32 to 4 for target ranges Ra ...22,,.....Ro. the bold highlights the best choice of M/p for each M, and the missing entries performance than FFT. One crucial observation is as follows: with the increase of output size, the best choice of M/p also increases or, equivalently, the optimal value of p tends to remain stable. Intuitively, this is the consequence of "balancing" the three summation steps (Section 3.4): when M < N, the most computationally expensive operation the matrix multiplication with OrrN) time cost, and thus, M/p should be small so that the decreases, despite sacrifice in the batch FFT step requiring O(rp p) operations (Appendix (..)). As the M becomes larger, however, more concern is needed regarding the batch FFT and post-processing steps, so the parameter p should not change rapidly. This observation indicates the possibility that the optimal value of p can be algorithmically auto-selected given setting (N, (), which we leave as future work.
2 shows the resulting run times, where
due to worse
4.4 EFFECT OF DIFFERENT PRECISION
We investigate the trade-off between accuracy and running time of PFT. To do this, we fix N = 2 and change the precision goal from 10 to 10-4 or 1 2 for target ranges Ro,29. Rg,210, Ro Table shows the results, where the parenthesized number is the ratio of run times of each setting to 10 Note that the run time of PFT is reduced by up to 17% or 27% when the precision goal is set to 10 10-4 4 10 respectively. This observation indicates that one may readily benefit from the trade-off, especially when the fast evaluation is of utmost importance albeit with slight sacrifice in accuracy.
8

---

Under review as a conference paper at ICLR 2021
Table 2: Average run time (ms) of PFT for N 22 with different settings of M/p p and M.
M
M/p
2
2
2
212
2
2
2
2
2
2
1/32
1.273
1.394
1.634
2.303
5.659
14.121
1/8
2.674
1.608
1.332
1.491
1.860
3.020
7.711
1/2
2.627
3.738
2.717
1.678
1.526
1.881
2.707
5.740
14.715
2.677
2.685
3.805
2.808
1.687
1.692
2.164
3.530
7.749
2
4.005
2.723
2.731
3.533
2.878
1.949
1,940
2.821
5,556
12.534
4.090
4.295
2.986
2.983
4.108
3.275
2.365
2.929
5.411
11.924
Table Average run time (ms) of PFT for N
222 with different precision settings.
M
Precision
2
2
2
212
2
2
2
2
2
2
10 6
1.273
1.295
1.332
1.491
1.526
1.692
1.940
2.821
5,411
11.924
10-4
1.249
1.278
1.293
1,329
1.400
1.607
1.872
2,469
4.590
9.927
(998)
(999)
(.97)
(.89)
(.92)
(.95)
(.96)
(.88)
(.85)
(.83)
10
1.238
1.244
1,251
1.277
1.343
1.512
1.740
2.297
4.058
8.733
(.97)
(966)
(.94)
(.86)
(.88)
(.89)
(.90)
(.81)
(.75)
(.73)
Top-20 anomalous points
24
Air condition index
22
20
-8
16
2500
5000
7500
10000
12500
15000
17500
20000
Time index
Figure 3: Top-20 anomalous points detected in Air Condition time-series data, where each red dot denotes a detected anomaly position. Note that replacing FFT with PFT does not change the result of the detection, still reducing the overall time complexity.
4.5 ANOMALY DETECTION
We demonstrate an example of how PFT is applied to practical applications. Here one simple but fundamental principle: replace the "perform FFT and discard unused coefficients" procedure with "just perform PFT". Considering the anomaly detection method proposed in Rasheed et al.) (2009), where one first performs FFT and then inverse FFT with only few low-frequency coefficients to obtain an estimated fitted curve, we can directly apply the principle to the method. To verify this experimentally,
time-series vector from Air Condition dataset, and set the target range as Ro,125 (< 250 low-frequency coefficients). Note that, in this setting, PFT results in around 8x speedup compared the conventional FFT (see Figure 2b). The top-20 anomalous points detected from the data are presented in Figure 3 In particular, we found that replacing FFT with PFT does change the result of top-20 anomaly detection, with all its computational benefits.
CONCLUSIONS
In this paper, we propose PFT (fast Partial Fourier Transform), an efficient algorithm for computing a part of Fourier coefficients. PFT approximates some of twiddle factors with relatively small os- cillations using polynomials, reducing the computational complexity of DFT due to the mixture of many twiddle factors. Experimental results show that PFT outperforms the state-of-the-arr FFTs as well as pruned FFT, with an order of magnitude of speedup without accuracy loss, significantly ex- tending the range of applications where partial Fourier transform becomes practical. Future works include optimizing the implementation of PFT; for example, the optimal divisor of input size N might can be algorithmically auto-selected. We also believe that hardware-specifi optimizations would further increase the performance of PFT.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Nir Ailon and Edo Liberty. Fast dimension reduction using rademacher series on dual bch codes.
Discrete Computational Geometry, 42(4))615, 2009,
C Boncelet. A rearranged dft algorithm requiring 2/6 multiplications. IEEE transactions on acoustics, speech, and signal processing, 34(6): 1986.
C Sidney Burrus and TW Parks. and Convolution Algorithms. Citeseer, 1985.
James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):2973311 1965.
W. Fraser. A survey of methods of computing minimax and near-minimax polynomial approx- imations for functions of a single independent variable. ACM, 12(3):295-311 314, 1965. doi: 10.1145/32128/ 22111121882222
11..1...111222221 321282
M. Frigo and G. Johnson. The design and implementation of fftw3. Proceedings of the IEEE, 93 (2):216-231, 2005.
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Simple and practical algorithm for sparse fourier transform. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pp. 1 1183-1192 SIAM, 2012a.
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Nearly optimal sparse fourier trans- form. In Proceedings of the forty-fourth annual ACM symposium Theory of computing, pp- 563-578, 2012b.
AN Hossen, Ulrich Heute, OV Shentov, and SK Mitra. Subband dft -tr-ttrttti i:: accuracy, complexity and applications. Signal Processing, 41(3):279-2944 1995.
Xiaodi Hou and Liqing Zhang. Saliency detection: spectral residual approach. In CVPR. IEEE Computer Society, 2007.
Piotr Indyk, Michael Kapralov, and Eric Price. (nearly) sample-optimal sparse fourier transform. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 480- 499. SIAM, 2014.
Jiarui Jin, Jiarui Qin, Yuchen Fang, Kounianhua Du, Weinan Zhang, Yong Yu, Zheng Zhang, and Alexander J. Smola. An efficient neighborhood- based interaction model for recommendation on heterogeneous graph. CoRR, 0tss/2007.00216, 2020.
Osman Asif Malik and Stephen Becker. Low-rank tucker decomposition of large tensors using tensorsketch. In NeurIPS, pp. 10117-10127, 2018.
J Markel. Fft pruning. IEEE transactions on Audio and Electroacoustics, 19(4):305 1971.
Michaël Mathieu, Mikael Henaff, and Yann LeCun. Fast training convolutional networks through ffts.. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Abdullah Mueen, Suman Nath, and Jie Liu. Fast approximate correlation for massive time-series data. In SIGMOD, pp. 171-182, ACM, 2010.
Keinosuke Nagai. Pruning the decimation in- in-time fft algorithm with frequency shift. IEEE transac- tions on acoustics, speech, and signal processing. (144)1008--010, 1986.
Rasmus Pagh. Compressed matrix multiplication. ACM Trans. Comput. Theory, 5(3):911-9:17, 2013.
Ninh Pham and Rasmus Pagh. Fast and scalable polynomial kernels via explicit feature maps. In KDD, pp. 239-247. ACM, 2013.
10

---

Under review as a conference paper at ICLR 2021
Faraz Rasheed, Peter Peng, Reda Alhajj and Jon G. Rokne. Fourier transform based spatial outlier mining. In Intelligent Data Engineering and Automated Learning IDEAL 2009, 10th Interna- tional Conference, Burgos, Spain, September 23-26, 2009. Proceedings, volume 5788 of Lecture Notes in Computer Science, pp. 317-324. Springer, 2009.
Hansheng Ren, Bixiong Xu, Yujing Wang, Chao Yi, Congrui Huang, Xiaoyu Kou, Tony Xing, Mao Yang, Jie Tong, and Qi Zhang. Time-series anomaly detection service at microsoft. In KDD, pp. 3009-3017. ACM, 2019.
Oren Rippel, Jasper Snoek, and Ryan P Adams. Spectral representations for convolutional neural networks, Advances in neural information processing systems, pp. 2449-2457, 2015.
OV Shentov, SK Mitra, Ulrich Heute, and AN Hossen. Subband dft-part i: Definition, interpreta- tion and extensions. Signal Processing, 41(3):261-277, 1995.
Sheng Shi, Runkai Yang, and Haihang You. new two-dimensional fourier transform algorithm based on image sparsity. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2017, New Orleans, LA, USA, March 5-9, 2017, pp. 1373-1377. IEEE, 2017.
Skinner. Pruning the decimation in-time fft algorithm. IEEE Transactions on Acoustics, Speech, and Signal Processing, 24(2):933-19,, 1976.
Georgey S Smirnov and Roman G Smirnov. Best uniform approximation of complex-valued func- tions by generalized polynomials having restricted ranges. Journal of approximation theory, 100 (2):8443033, 1999.
Henrik V Sorensen and C Sidney Burrus. Efficient computation of the dft with only subset of input or output points. IEEE transactions on signal processing. 41(3):1184 184-1200, 1993.
Petr Sysel and Pavel Rajmic. Goertzel algorithm generalized to non-integer multiples of fundamental frequency. EURASIP Journal on Advances in Signal Processing, 2012(II:56, 2012.
11

---

Under review as a conference paper at ICLR 2021
A PROOFS
A.1 PROOF OF LEMMA
Proof. Let Q = arg min per.
P( uix 11 [s-11ls We first observe the following equation:
Q = arrg P(x)) e"1111 [1~
PEP.
arg min P(r + (t) cui(att)) [| ||||
PeP.
arg min ||e-uiu uip P(x + p1) eui [|
Per.
le- 1. Recall that the polynomial Pa.g, is defined by | ((x) E Pa. it is clear that e -uigg Q(x + (1) E Pa because translation and non-zero scalar multiplication on polynomial do not change its degree. Therefore,
where the third equality holds since
arg pe [P((x) "
by the uniqueness of the best approximation (Smirnov & Smirnov 1999), we have
Q(x + (1) Pa.g.
which yields Q(x) = exi Pareal - 14), and hence the proof.
A.2 PROOF OF THEOREM 2
Proof. We first claim that the following statement holds: let 2 2; if is b-smooth and M < N is a positive integer, then there exists a positive divisor p of N satisfying M/ S < vbM. Indeed, suppose that none of N's divisors belongs to [M/vb, vbM). Let 1 = Pı < P2 < < Pa = N be the enumeration of all positive divisors of N in increasing order. It is clear that P1 < VBM and M/Vb Pa since b > and < M S N. Then, there exists an i 2, ... dd - 1} that p. < M/ and P.+1 2 VbM. Since N is b-smooth and p; N, at least one of 2p,, 3p:: bp, must be divisor of N. However, this is contradiction because we have Pi+1/p; (VbM)(M/V)) so none of 2p,, 3p, 6,, can be a divisor of N, which completes the proof.
b.
Exploiting the above property, we manage to reduce the time complexity of PFT to functional form dependent of only N and M. We follow the convention in counting FFT operations, assuming that all inta-inndeendeet elements such as configuration results B, r and twiddle factors are precomputed, and thus not included in the run-time cost. We begin with the construction of the matrix A. For this, we merely interpret in Algorithm 2). Also, recall that the matrix B can be precomputed as descrihed in Section [.4 For the two matrices A of size q and B of size q has rumning time of O(pqr) = O(r N) (line 2 in Algorithm 2). Next, the expression (6) contains r DFTs of size p. namely Em.j = ΣkE(p) Ck.j e
an array representation for A of size
N (line
standard matrix multiplication algorithm
e 22rimk/p for each j E [r]. We use FFT r times for the computation, then it is easy to see that the time cost is given by Ofr-plogy) (lines 3-5 in Algorithm
2b. Finally, there are 2M + coefficients
be calculated in (7). each requiring Orr) operations,
giving an upper bound O .)) for the running time (lines 6-8 in Algorithm 2 Combining the three upper bounds, we formally express the time complexity TNN, of PFT as
T(N, .) = O(r (N + p plogp+ + +M))
Note that r is only dependent of and M/p by its definition (Algorithm 1. Therefore, when is fixed, T(N, M) is dependent of the choice of p. By the preceding argument, we can always find divisor p of N such that M/VB < p VbM, implying that M p is tightly bounded, and thus, so r. It follows that p ((M) and r = ((1). which leads to the following asymptotic upper bound for T(N, M) with respect to N and M: T(N, M) O(N + M log M),
hence the proof.
12

---

Under review as a conference paper at ICLR 2021
A.3 PROOF OF THEOREM 3
Proof. Let v = -2(1 q/2)/N. By the estimation in 5). the following holds:
|| - R( = Ae - Tip Pr- (v(m -w])) 2nimk/pe
2 -xim/p m R
Σ
- - P ( ( 2wink/ xim/ I I 1agkt (e
R,
Σ |ogh+ll [1e -Pr -P--1 (m)mmmmmmm
since we have le 2wimm//p/ = le le- mimms/// = le vipj E(c,r). We extend the domain of the function @Te(m--)) R) -P------ -P--,,((..))- (1(.mm pi) from m E Ry,M = u+
sivyy = 1. If ranges from O to q 1, then |u| <
2(g/2)/N 1/p, and thus, M/ul I M/p
to x [n-M, (note that extending domain never decreases the uniform norm), and replace v(æ u1) with x', from which it follows that
à =())ll
Σ
ag&+tl
||e (emin((=)) Pr- ( - -1)1l=--sMM
k,l
Σ
agk+tl
||e
-Pr- (x') (1))s1a))
agk+tl
|
-Pr- (17736o))))
k,
ag0+2
C
kd
where the second inequality holds since Mlu| < ((G,T, hence the desired result.
13


Reviews:
[{"review_id": "Qb1Vl4OB3MZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper suggests a method for quickly computing a \"partial Fourier transform\", which basically means that we want only a small range of output frequencies.  The main technique is an approximation of so called \"twiddle functions\" (which are basically trigonometric functions, or, exponents of complex units if viewed in the complex plane) using polynomials.   The resulting algorithms run in time O(N + M log M) where M is the size of the required frequency range, and N is the input.  This should be compared with Cooley and Tukey's FFT, which is O(N log N).  In fact, the main idea in the paper uses Cooley and Tukey's decomposition of the expression for Fourier transform.\n\nThe first thing I must note is, that the authors seem not to be aware of existing literature on partial Fourier transforms.  For example, Ailon and Liberty show in their paper [1] that whenever you are only interested in M Fourier frequencies then you can do exact FFT in time O(N log M).  This is done by pruning Cooley Tukey's FFT.  It is not as good as O(N + M log M), but it is EXACT, and it doesn't require the M frequencies to be in a single consecutive range.  (In fact, [1] does this for the Hadamard transform, but I am quite certain that it works for the DFT as well because the argument depends on the computational graph only, which is identical for both cases).  \n\nAdditionally, Indyk et al have written many papers on fast computation of Fourier when you know a priori that only M frequencies are nonzeros (and the rest are 0).  This setting is different from the one in this paper, but it is definitely relevant.\n\nFinally, I am inclined to say that the subject of this paper is only loosely related to the scope if ICLR.  I mean, computing Fourier coefficients is definitely a way to get a useful representation of the data, but I don't know if ICLR is the correct venue for this kind of paper.\n\nOtherwise, the paper is well written, and I assume it is correct.\n\n[1] Ailon, Liberty, \"Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes. \" (Discrete and Computational Geometry, 2009)\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "APlRKoYyXAm", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall this is an interesting paper. The paper proposes a few approximations in the computation of the DFT that enable to compute the DTFT of a signal at uniform grid of 2M+1 frequency points around a certain midpoint $\\mu$. While this is easy and straightforward using the direct computation or Goertzel's algorithm, these have complexity O(NM). While I did not check the math fully for correctness, the development appears correct. \n\nHaving said that, the paper completely discounts fair comparisons with the Goertzel algorithm. When M is small compared to N ($o(\\log N)$), complexity of O(NM) is not much of a problem, and Goertzel's algorithm has very favorable hidden constants and is exact. If M is $O(N)$ then the proposed approach has the same complexity with the FFT, which is also exact and has favorable constants. A discussion and an experimental study of the performance of the method compared to the Goertzel algorithm or the direct implementation would demonstrate the benefits of the algorithm.\n\nMy main objection to this paper is one of scope. I do not see how the paper fits in learning conference. It would be a much better fit in a signal processing conference/journal or in a theoretical computer science one. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "5c_lkFdvl7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a fast approximate algorithm for partial discrete Fourier transform. Given the input signal $a_0...a_N$ in the time domain the algorithm approximately computes the first $O(M)$ frequencies. The running time is $O(r (N + M \\log M))$, where $r$ a parameter that controls the accuracy of the output. The algorithm itself proceeds by applying polynomial approximation to the twiddle coefficients in FFT, which makes it possible to reduce the running time.\n\nPros:\n+ Well-motivated problem: in many applications, most of the signal energy is present in the first few coefficients  and this algorithm computes them faster (albeit approximately)\n+ To the best of my knowledge the algorithm is new, although cannot tell for sure given a large body of prior work on this topic (see below)\n+ Experimental evaluation shows one order of magnitude improvement in the running time, while keeping the relative error to $10^{-6}$.\n\nCons:\n- The papers omits a significant body of prior work on computing the first few DFT coefficients faster. For example:\n  * Pruned FFT: the algorithm evaluates the first M coefficients in O(N log M) time; here, the results are *exact*. See e.g., http://www.fftw.org/pruned.html\n  * Subband FFT: this method is approximate; see e.g., these papers:\nSubband DFT—part II: accuracy, complexity and applications, AN Hossen, U Heute, OV Shentov, SK Mitra - Signal Processing, 1995 - Elsevier\n Subband DFT—Part I: Definition, interpretation and extensions, OV Shentov, SK Mitra, U Heute, AN Hossen - Signal Processing, 1995 - Elsevier\n Subband DFT-interpretation, accuracy, and computational complexity, OV Shentov, AN Hossen, SK Mitra… - Conference Record of the …, 1991 - computer.org\n\n  There are also other methods cited in those articles. \n\n- I could not find any analysis of the trade-off between the accuracy and the values of parameters r and p. As a result, it is not clear what the runtime dependence on those parameters is. \n\nThe above two points make it impossible to compare the proposed algorithm relative to what was known before, either in theory or in practice. \n\nAdditional comments:\n- One can  assume (essentially) without loss of generality that the target frequencies lie in the interval centered at zero (i.e., that $\\mu$ is zero), as otherwise one can use Shift Theorem to shift the frequencies by multiplying each coefficient of the time signal by a phase term. This should simplify the presentation.\n\n\nOverall: the paper has interesting (and potentially very useful) ideas. However, it needs a very substantial rewrite, as per the comments above. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The major complaint about this paper was the lack of a proper comparison to previous work, both theoretically and empirically. Also, a study of the tradeoff between the accuracy and running time would significantly help this paper. Ultimately these were the main reasons for deciding to not accept the paper. The reviewers did think the algorithm was new and interesting, and so hopefully by addressing the complaints above, a future version of the paper could be more influential.
Decision: Reject