MIT新算法：sFFT，快速傅立叶变换的革命

5星 · 超过95%的资源需积分: 10 29 浏览量更新于2024-09-15 1 收藏 284KB PDF 举报

"sFFT by MIT: 一种由麻省理工学院(MIT)开发的快速傅立叶变换新算法，据称其效率比传统的快速傅立叶变换(FFT)提升了近百倍，尤其适用于处理稀疏傅立叶变换问题。" 本文摘要介绍了一种名为"sFFT"的新颖算法，专门用于解决稀疏傅立叶变换问题。在信号处理、音频/图像/视频压缩以及学习理论等多个领域，稀疏傅立叶变换都是核心问题。给定一个长度为n的复数向量x和一个参数k，sFFT的目标是估算x的傅立叶变换中振幅最大的k个系数。传统的处理方式通常是迭代的，逐步估计并减去大系数，然后对剩余部分进行递归。然而，sFFT算法采取了一种不同的策略，它借鉴了数字信号处理中的高斯滤波器和多尔夫-切比雪夫滤波器技术，一次性识别并估算出最大的k个系数，类似于数据流算法中的"sketching"方法。这种非迭代的方式使得算法结构更为简洁。由于算法设计的简化，sFFT能够扩展到更广泛的稀疏度（sparsity）范围，即对于更大的k值，算法仍能保持比传统方法更快的速度。这在实际应用中具有显著的优势，特别是在处理大规模、高稀疏性的数据时，sFFT可能提供前所未有的计算效率和性能提升。 sFFT算法的提出是对傅立叶变换领域的一大创新，它通过优化算法结构和利用特定的滤波器技术，成功地解决了传统方法在处理稀疏信号时的效率瓶颈。这一进展对于提高计算效率，尤其是对于需要实时处理大量复杂数据的现代应用来说，具有重要的理论和实践意义。

each iteration estimates the largest Fourier coeﬃc ient

(the one least impacted by leakage) and subtracts its

contribution to the time signal. The iterative update of

the time signal causes a large increase in runtime. The

algorithms in [GGI

02, Man92] perform t hi s update by

going through O(k) iterations each of which updates

at least O(k) time samples, resulting in an O(k

) term

in the runtime. The algorithm [GMS05], introd u ce d

a ”bulk sampling” algorithm that amortizes t hi s pro-

cess but it requires solving instances of a non-uniform

Fourier transform, which is expen s ive in practice.

Interpolation-based algorithms are less common

and limited to the design in [Iwe10a]. This approach

uses a leakage-free ﬁlter, G, to avoid the need for itera-

tion. Speciﬁcally, the algorithm in [Iwe 10a] uses for G a

ﬁlter in which G

= 1 iﬀ i mod n/p = 0 and G

= 0 oth-

erwise. The Fourier transform of this ﬁlter is a “spike

train” with period p. This ﬁlter does not leak: it is equal

to 1 on 1/p fraction of coordinates and is zero elsewhere.

Unfortunately, however, such a ﬁlter requires that p di-

vides n; moreover, the algorithm needs several diﬀerent

values of p. Since in general one cannot assume that n

is divisible by all numb er s p, the algorithm treats the

signal as a continuous function and interpolates it at

the required points. Interpolation introduces additional

complexity and increas es the exponents in the runtime.

Our appr oach. The key feature of our algorithm

is the use of a diﬀerent type of ﬁlter. In the simplest

case, we use a ﬁlter obtained by convolving a Gaussian

function with a box-car function. A more eﬃcient ﬁlter

can be obtained by replacing the Gaussian function

with a Dolph-Chebyshev function. (See Fig. 1 f or an

illustration.)

Because of this new ﬁlter, our algorithm does not

need to either iterate or interpolate. Speciﬁcally, the

frequency response of our ﬁlter

G is nearly ﬂat i ns id e

the pass region and has an exponential tail outside

it. This means that leakage from frequencies in other

buckets is negligible, and hence, our algorithm need

not iterate. Also, ﬁltering can be performed using the

existing input samples x

, and hence our algorithm need

not interpolate the signal at new points. Avoiding both

iteration and interpolation is the key feature that makes

our algorithm eﬃcient.

Further, once a large coeﬃcient is isolated in a

bucket, one needs to identify its frequency. In contrast

to p ast work which typically uses binary search for this

task, we adopt an idea from [PS10] and tailor it to

our problem. Speciﬁcally, we simply select the set of

“large” bins which are likely to contain large coeﬃcients,

and directly estimate all frequencies in those bins. To

balance the cost of the bin selection and estimation

steps, we make the numbe r of bins s omewhat larger than

the typical value of O(k). Speciﬁcally, we use B ≈

√

nk,

which leads t o the stated runtime.

2 Notation

Transform-Related Notations. For an input

signal x ∈ C

, its Fourier spectrum is denoted by ˆx.

We will use x ∗ y to denote the convolution of x and y,

and x·y to denote the coordinate-wise product of x and

y. Recall that

x · y = ˆx ∗ ˆy. We deﬁne ω = e

2π i/ n

to be

a primitive nth root of u n ity (h er e i =

√

−1, but in the

rest of the paper, i is an index).

Indices-Related Notations. All operations on

indices in this paper are taken modu lo n. Therefore

we might r efe r to an n-dimensional vector as having

coordinates {0, 1, . . . , n − 1} or {0, 1, . . . , n/2, − n/2 +

1, . . . , −1}. interchangeably. Finally, [s] refers to the set

of indices {0, . . . , s − 1}, whereas supp(x) refers to th e

support of vector x, i.e., the set of non-zero coordinates.

In this paper we assume that n is an integer power

of 2.

3 Basics

(a) Window Functions. In digital signal pro-

cessing [OSB99] one deﬁnes window functions in the

followin g manner:

Definition 3.1. We deﬁne a (ǫ, δ, w) standard win-

dow function to be a symmetric vector F ∈ R

with

supp(F ) ⊆ [−w/2, w/2] such that

= 1,

> 0 for all

i ∈ [−ǫn, ǫn], and |

| < δ for all i /∈ [−ǫn, ǫn].

Claim 3.2. For any ǫ and δ, there exists an

(ǫ, δ, O(

log(1/δ))) standard window function.

Proof. This is a well known fact [Smi11]. For ex-

ample, for any ǫ and δ, one can obtain a stan-

dard window by taking a Gaussian with standard de-

viation Θ(

log(1/δ)/ǫ) and truncating it at w =

log(1/δ))). The Dolph-Chebyshev window function

also has the claimed property but with minimal big-O h

constant [Smi11] (in partic ul ar, half the constant of the

truncated Gaussian). 

The above deﬁnition shows that a standard window

function acts like a ﬁlter, allowing us to focus on a subset

of the Fourier coeﬃcients. Ideally, however, we would

like the pass region of our ﬁlter to be as ﬂat as possible.

Although it is plausible that one could combine our ﬁlters

with the binary search technique of [GMS05] and achieve an

algorithm with a O(k log

n) runtime, our preliminary analysis

indicates that the resulting algorithm would be slower. Intuitively,

observe that for n = 2

and k = 2

, the values of

√

nk = 2

16.5

≈

92681 and k log

n = 45056 are quite close to each other.

剩余11页未读，继续阅读

zhiyii

粉丝: 5
资源: 5

MIT新算法：sFFT，快速傅立叶变换的革命

sfft算法程序

sfft-modified-master_sfft3.0_Modified_MIT_

SFFT-master_SFFT_SFFT算法

sfft的matlab

sfft matlab程序

DCT和SFFT的区别

SFFT 特征选择matlab

mit-bih arrhythmia FFT

function y = OTFS_demodulation(N,M,r) %% OTFS demodulation: 1. Wiegner transform, 2. SFFT r_mat = reshape(r,M,N); Y = fft(r_mat)/sqrt(M); % Wigner transform Y = Y.'; y = ifft(fft(Y).').'/sqrt(N/M); % SFFT end

matlab sfft

最新资源