PREPRINT 1 Decimated Pronys method for stable super-resolution

2025-05-02 0 0 656.61KB 5 页 10玖币

侵权投诉

PREPRINT 1

Decimated Prony’s method for stable

super-resolution

Rami Katz, Nuha Diab, and Dmitry Batenkov

Abstract—We study recovery of amplitudes and nodes of a

ﬁnite impulse train from noisy frequency samples. This problem

is known as super-resolution under sparsity constraints and

has numerous applications. An especially challenging scenario

occurs when the separation between Dirac pulses is smaller than

the Nyquist-Shannon-Rayleigh limit. Despite large volumes of

research and well-established worst-case recovery bounds, there

is currently no known computationally efﬁcient method which

achieves these bounds in practice. In this work we combine

the well-known Prony’s method for exponential ﬁtting with

a recently established decimation technique for analyzing the

super-resolution problem in the above mentioned regime. We

show that our approach attains optimal asymptotic stability in

the presence of noise, and has lower computational complexity

than the current state of the art methods.

Index Terms—Prony’s method, decimation, sparse super-

resolution, direction of arrival, sub Nyquist sampling, ﬁnite rate

of innovation

I. INTRODUCTION

VARIOUS problems of signal reconstruction in multiple

basic and applied settings can be reduced to recovering

the amplitudes {αk}n

k=1 and nodes {xk}n

k=1 of a ﬁnite impulse

train f(x) = Pn

k=1 αkδ(x−xk)from band-limited and noisy

spectral measurements

g(ω) =

k=1

αke2πjxkω+e(ω), ω ∈[−Ω,Ω],(1)

where Ω>0and kek∞≤for some  > 0. Due to

its widespread applications, this problem has been studied

under various guises including tauberian approximation [1],

parametric spectrum estimation and direction of arrival [2],

[3], time-delay estimation [4], sparse deconvolution [5], super-

resolution (SR) [6], [7] and ﬁnite-rate-of-innovation sampling

[8], [9]. Beyond the theoretical modelling, recent advances

have shown (1) to be the work-horse for emerging areas such

as super-resolution tomography and spectroscopy [10], [11],

ultra-fast time-of-ﬂight imaging [12] and unlimited sensing

[13]; in such cases, efﬁcient and robust solutions to (1) entail

pushing real-world capabilities beyond the possibilities of

conventional hardware.

Despite the theoretical advances on this topic (works cited

above and follow-up literature), there are still fundamental

Submitted for review on March 24th, 2023. N. Diab and D. Batenkov are

supported by the Israel Science Foundation Grant 1793/20 and a collaborative

grant from the Volkswagen Foundation.

R. Katz is with the School of Electrical Engineering, Tel Aviv

University, Tel Aviv, Israel (e-mail: ramikatz@mail.tau.ac.il). N. Diab and

D. Batenkov are with the Department of Applied Mathematics, School

of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail:

nuhadiab@tauex.tau.ac.il, dbatenkov@tauex.tau.ac.il).

research gaps that arise due to ill-posedness and instability

of (1) in the presence of noise. In particular, an especially

challenging regime occurs when the separation ∆between two

or more nodes is smaller than the Nyquist-Shannon-Rayleigh

(NSR) limit 1/Ω. Recently, min-max error bounds for SR

in the noisy regime were derived in the case when some

nodes form a dense cluster [14], [15], [16], establishing the

fundamental limits of recovery in the SR problem (cf. Sect. II).

However, a tractable and provably optimal algorithm has been

missing from the literature.

In this work we develop a reconstruction algorithm inspired

by the decimation approach [17], [18] (cf.[19], [14], [16],

[15] and also [20], [21]). Our procedure (Sect. III) relies

on sampling g(ω)at 2nequispaced and maximally separated

frequencies, followed by solving the SR problem thus obtained

by applying the classical Prony’s method for exponential

ﬁtting [22], whose accuracy has been recently established

in [23]. For success of the approach, care needs to be

taken to avoid node aliasing and collisions. Inspired by

[15], this is achieved by considering sufﬁciently many

decimated sub-problems. The result is a tractable algorithm,

dubbed the Decimated Prony’s method (DPM), which has

lower computational complexity than the well-established and

frequently used ESPRIT algorithm (see e.g. [24]). We further

provide theoretical and numerical evidence which show that

DPM achieves the optimal asymptotic stability and noise

tolerance guaranteed in the literature. We believe that our

results pave the way to developing robust procedures for

optimal solution of problems derived from (1).

II. TOWARDS OPTIMAL ALGORITHMS

Throughout the paper we consider the number of nodes

(resp. amplitudes) n∈ {1,2, . . . }in (1) to be ﬁxed. We

assume that the nodes satisfy {xk}n

k=1 ⊆−1

2,1

2. By

rescaling the data (1), this assumption poses no loss of

generality (see Section 4 in [15]). Let {˜xk}n

k=1 and {˜αk}n

k=1

be the approximated parameters obtained via a reconstruction

algorithm using the data (1).

Deﬁnition 1 ([15]).Let {(αk, xk)}n

k=1 ⊆U. Given  > 0, the

min-max recovery rates are

Λx,j

,U,Ω= inf

A:g7→{˜αj,˜xj}sup

{αj,xj}

sup

kek∞≤

|xj−˜xj|,

Λα,j

,U,Ω= inf

A:g7→{˜αj,˜xj}sup

{αj,xj}

sup

kek∞≤

|αj−˜αj|.

Here Uis some ﬁxed subset in the parameter space, whereas

the inﬁmum is over the set of all reconstruction algorithms A

which employ the data (1).

arXiv:2210.13329v4 [math.NA] 27 Mar 2023

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

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

10 玖币 0人已下载

立即下载

摘要：

PREPRINT1DecimatedProny'smethodforstablesuper-resolutionRamiKatz,NuhaDiab,andDmitryBatenkovAbstractWestudyrecoveryofamplitudesandnodesofaniteimpulsetrainfromnoisyfrequencysamples.Thisproblemisknownassuper-resolutionundersparsityconstraintsandhasnumerousapplications.Anespeciallychallengingscenarioo...

展开>> 收起<<

PREPRINT 1 Decimated Pronys method for stable super-resolution.pdf

共5页,预览1页

还剩页未读，继续阅读

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

PREPRINT 1 Decimated Pronys method for stable super-resolution

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: