Quartic Samples Suce for Fourier Interpolation Zhao SongBaocheng SunOmri WeinsteinRuizhe Zhang Abstract

2025-04-29 0 0 1.54MB 112 页 10玖币

侵权投诉

Quartic Samples Suﬃce for Fourier Interpolation

Zhao Song∗Baocheng Sun†Omri Weinstein‡Ruizhe Zhang§

Abstract

We study the problem of interpolating a noisy Fourier-sparse signal in the time duration [0, T ]

from noisy samples in the same range, where the ground truth signal can be any k-Fourier-sparse

signal with band-limit [−F, F ]. Our main result is an eﬃcient Fourier Interpolation algorithm

that improves the previous best algorithm by [Chen, Kane, Price, and Song, FOCS 2016] in the

following three aspects:

•The sample complexity is improved from e

O(k51) to e

O(k4).

•The time complexity is improved from e

O(k10ω+40) to e

O(k4ω).

•The output sparsity is improved from e

O(k10) to e

O(k4).

Here, ωdenotes the exponent of fast matrix multiplication. The state-of-the-art sample com-

plexity of this problem is ∼k4, but was only known to be achieved by an exponential-time

algorithm. Our algorithm uses the same number of samples but has a polynomial runtime,

laying the groundwork for an eﬃcient Fourier Interpolation algorithm.

The centerpiece of our algorithm is a new suﬃcient condition for the frequency estimation

task—a high signal-to-noise (SNR) band condition—which allows for eﬃcient and accurate signal

reconstruction. Based on this condition together with a new structural decomposition of Fourier

signals (Signal Equivalent Method), we design a cheap algorithm to estimate each “signiﬁcant”

frequency within a narrow range, which is then combined with a signal estimation algorithm

into a new Fourier Interpolation framework to reconstruct the ground-truth signal.

∗zsong@adobe.com. Adobe Research.

†woafrnraetns@gmail.com. Weizmann Institute of Science.

‡omri@cs.columbia.edu. The Hebrew University and Columbia University.

§ruizhe@utexas.edu. The University of Texas at Austin.

arXiv:2210.12495v3 [cs.DS] 8 Feb 2023

Contents

1 Introduction 1

1.1 Relatedworks........................................ 2

2 Technical Overview 3

2.1 High-levelapproach .................................... 3

2.2 Our techniques for frequency estimation . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2.1 Two-level sampling for signiﬁcant samples generation . . . . . . . . . . . . . 8

2.2.2 Energy estimation and Signal Equivalent Method . . . . . . . . . . . . . . . . 9

2.2.3 Time-domain concentration of ﬁltered signals . . . . . . . . . . . . . . . . . . 11

2.3 Our techniques for Fourier Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Organization 13

A Preliminaries 15

B Energy Bounds of Fourier Sparse Signals 16

C Filter in Frequency Domain 17

C.1 Frequency domain ﬁlter construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

C.2 Frequency domain covering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

D Hashing the Frequencies 20

D.1 HashToBins procedure.................................. 20

D.2 Frequencyisolation..................................... 21

D.3 Largeoﬀsetevent...................................... 22

E Filter in Time Domain 24

E.1 Time domain ﬁlter construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

E.2 Normalization factor of the ﬁlter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

E.3 Fluctuationbound ..................................... 27

E.4 Energy preserving of the time domain ﬁlter . . . . . . . . . . . . . . . . . . . . . . . 30

F Ideal Filter Approximation 32

F.1 Swaptheorderofﬁltering................................. 33

F.2 Approximation error bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

G Concentration Property of the Filtered Signal 36

H Energy Bound for Filtered Fourier Sparse Signals 39

H.1 Energy bound for untruncated ideally ﬁltered signals . . . . . . . . . . . . . . . . . . 39

H.2 Energy bound for ﬁltered signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

H.3 Technicalclaim....................................... 42

I Local-Test Signal 43

I.1 Ideallocal-testsignal.................................... 43

I.2 Ideal post-truncated local-test signal . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

I.3 Energy bound for local-test signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

J Empirical Energy Estimation 50

J.1 Samplingandreweighing.................................. 50

J.2 Energy estimation for Fourier-sparse signals and ﬁltered signals . . . . . . . . . . . . 52

J.3 Partial energy estimation for ﬁltered signals and local-test signals . . . . . . . . . . . 54

J.4 Technicallemmas...................................... 57

K Generate Signiﬁcant Samples 59

K.1 Energy estimation for noisy signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

K.2 Signiﬁcant sample generation for a single bin . . . . . . . . . . . . . . . . . . . . . . 62

K.3 Signiﬁcant sample generation for multiple bins . . . . . . . . . . . . . . . . . . . . . 63

K.4 Technicalclaims ...................................... 66

L Frequency Estimation 69

L.1 Frequency estimation via signiﬁcant samples . . . . . . . . . . . . . . . . . . . . . . . 69

L.2 Simultaneously estimate frequencies for diﬀerent bins . . . . . . . . . . . . . . . . . . 72

L.3 Vote distributions in ArySearch ............................ 77

M Signal Reconstruction 84

M.1 Preliminary ......................................... 85

M.2Heavycluster........................................ 86

M.3Fouriersetquery ...................................... 87

M.4 High signal-to-noise ratio band approximation . . . . . . . . . . . . . . . . . . . . . . 89

M.5 Fourier interpolation with constant success probability . . . . . . . . . . . . . . . . . 92

M.6 Min-of-medians signal estimator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

M.7 Main algorithm for Fourier interpolation . . . . . . . . . . . . . . . . . . . . . . . . . 100

N Structure of Our Fourier Interpolation Algorithm 106

1 Introduction

Fourier transforms are the backbone of signal processing and engineering, with profound impli-

cations to nearly every ﬁeld of scientiﬁc computing and technology. This is primarily due to the

discovery of the well-known Fast Fourier Transform (FFT) algorithm [CT65], which is ubiquitous

in engineering applications, from image and audio processing to fast integer multiplication and op-

timization. The classic FFT algorithm of [CT65] computes the Discrete Fourier Transform (DFT)

of a length-nvector x, where both the time and frequency domains are assumed to be discrete. This

algorithm takes O(n) samples in the time domain, and constructs bx= DFT(x) in O(nlog(n)) time.

The discrete setting of DFT limits its applicability in two main aspects: The ﬁrst one is that many

real-world signals are continuous (analog) by nature; Secondly, many real-world applications (such

as image processing) involve signals which are sparse in the frequency domain (i.e., kbxk0=kn)

[ITU92,Wat94,Rab02]. This feature underlies the compressed sensing paradigm [CRT06], which

leverages sparsity to obtain sublinear algorithms for signal reconstruction, with time and sample

complexity depending only on the sparsity k. Unfortunately, the continuous case cannot simply be

reduced to the discrete case via standard discretization (i.e., using a sliding-window function), as

it “smears out” the frequencies and blows up the sparsity, which motivates a more direct approach

for the continuous problem [PS15].

The study of Fourier-sparse signals dates back to the work of Prony in 1795 [dP95], who studied

the problem of exact recovery of the “ground-truth” signal xin the vanilla noiseless setting. By

contrast, the realistic setting of reconstruction from noisy-samples [PS15] is a diﬀerent ballgame,

and exact recovery is generally impossible [Moi15]. In the Fourier Interpolation problem, the

ground-truth signal

x∗(t) =

j=1

vje2πifjt, vj∈C, fj∈[−F, F ]∀j∈[k],

is a k-Fourier-sparse signal with bandlimit F. Given noisy access to the ground truth x(t) = x∗(t)+

g(t) in limited time duration t∈[0, T ] (which means that we need to recover x∗(t) by taking samples

from x(t)), the goal is to reconstruct a e

k-Fourier-sparse signal y(t) (i.e., y(t) = Pe

j=1 evje2πi

fjtfor

some evj∈C,e

fj∈[−F, F ] for all j∈[e

k]) such that

ky(t)−x∗(t)k2

T≤c(kgk2

T+δkx∗(t)k2

holds for some c=O(1), where the T-norm of any function f:R→Cis deﬁned as

kf(t)k2

T:= 1

TZT

0|f(t)|2dt.

We note that it is not necessary for y(t)’s frequencies and magnitudes ( e

fj,evj) being close to the

ground-truth signal x∗(t)’s frequencies and magnitudes (fj0, vj0).

Prior to this work, the state-of-the-art algorithm for the Fourier interpolation problem was given

by [CKPS16], which achieves e

O(k51) sample complexity, e

O(k10ω+40) running time, e

O(k10) output

sparsity, and c≥2000 approximation ratio. In [SSWZ22], the approximation ratio was improved to

≈1 + √2, but the sample complexity remained large, and runtime remained slow. For calibration,

we note that o(k4) sample complexity for Fourier interpolation is not known to be achievable even

with exponential decoding time. In this work, we focus on improving the eﬃciency of [CKPS16]’s

algorithm across all aspects: (i) runtime, (ii) sample complexity, and (iii) output-sparsity. Our

main result is:

References Samples Time Output Sparsity

[CKPS16]e

O(k51)e

O(k10ω+40)e

O(k10)

[CP19a,SSWZ22]e

O(k4) exp(k3)k

Ours (Theorem 1.1)e

O(k4)e

O(k4ω)e

O(k4)

Table 1: Summary of the results. All the algorithms obtain O(1) approximation ratio. We use ω

to denote the exponent of matrix multiplication, currently ω≈2.373 [Wil12,AW21].

Theorem 1.1 (Main Theorem).Let x(t) = x∗(t) + g(t), where x∗(t)is k-Fourier-sparse signal

with frequencies in [−F, F ]. Given samples of x(t)over [0, T ], there is an algorithm that uses

k4log(F T )·poly log(k, 1/δ, 1/ρ)

samples, runs in

k4ωlog(F T )·poly log(k, 1/δ, 1/ρ)

time, and outputs a k4·poly log(k/δ)-Fourier-sparse signal y(t)s.t with probability at least 1−ρ,

ky(t)−x∗(t)kT.kg(t)kT+δkx∗(t)kT.

1.1 Related works

Sparse Fourier transform in the discrete setting The Fourier transform bx∈CNis a vector

of length N. The goal of a sparse DFT algorithm is, given a bunch of samples xiin the time domain

and the sparsity parameter k, to output a k-Fourier-sparse signal x0with the `2/`2-guarantee

kbx0−bxk2.min

k-sparse zkz−bxk2.

There are two diﬀerent lines of work solving the above problem. One line [GMS05,HIKP12a,

HIKP12b,IKP14,IK14,Kap16,Kap17] is carefully choosing samples (via hash function) and

obtaining sublinear sample complexity and running time. The other line [CT06,RV08,Bou14,

HR17,NSW19] is taking random samples (via RIP property [CT06] or others) and paying sublinear

sample complexity but nearly linear running time.

Sparse Fourier transform in the continuous setting [PS15] deﬁned the sparse Fourier trans-

form in the continuous setting. It shows that as long as the sample duration Tis large enough

compared to the frequency gap η, then there is a sublinear time algorithm that recovers all the fre-

quencies up to certain precision and further reconstructs the signal. [JLS23] improves and generalize

several results in [PS15]. In particular, [PS15] only works for one-dimensional continuous Fourier

transform, and [JLS23] generalizes it to d-dimensional Fourier transform. In order to convert the

tone estimation guarantee to signal estimation guarantees, [PS15] provides a positive result which

shows T=O(log2(k)/η) is suﬃcient, and [Moi15] shows a lower bound result where T= Ω(1/η).

[Son19] asked an open question about whether this gap can be closed. [JLS23] made positive

progress on that problem by providing a new upper bound which is T=O(log(k)/η).

From the negative side, [Moi15] shows that in order to show tone estimation1, we have to pay

a lower bound in sample duration T. In [PS15], it shows that once we have tone estimation, we

1Tone refers to a (frequency, coeﬃcient) pair in [PS15]. E.g., (fi, vi) is a tone of the signal x(t) = Pk

i=1 vie2πifit.

And tone estimation means estimating each (fi, vi) precisely.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

QuarticSamplesSuceforFourierInterpolationZhaoSong*BaochengSunOmriWeinsteinRuizheZhang§AbstractWestudytheproblemofinterpolatinganoisyFourier-sparsesignalinthetimeduration[0;T]fromnoisysamplesinthesamerange,wherethegroundtruthsignalcanbeanyk-Fourier-sparsesignalwithband-limit[F;F].Ourmainresultisan...

展开>> 收起<<

Quartic Samples Suce for Fourier Interpolation Zhao SongBaocheng SunOmri WeinsteinRuizhe Zhang Abstract.pdf

共112页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Quartic Samples Suce for Fourier Interpolation Zhao SongBaocheng SunOmri WeinsteinRuizhe Zhang Abstract

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: