On the accuracy of Prony's method for recovery of exponential sums with closely spaced exponents
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913316105879552 |
|---|---|
| author | Katz, Rami Diab, Nuha Batenkov, Dmitry |
| author_facet | Katz, Rami Diab, Nuha Batenkov, Dmitry |
| contents | In this paper we establish accuracy bounds of Prony's method (PM) for recovery of sparse measures from incomplete and noisy frequency measurements, or the so-called problem of super-resolution, when the minimal separation between the points in the support of the measure may be much smaller than the Rayleigh limit. In particular, we show that PM is optimal with respect to the previously established min-max bound for the problem, in the setting when the measurement bandwidth is constant, with the minimal separation going to zero. Our main technical contribution is an accurate analysis of the inter-relations between the different errors in each step of PM, resulting in previously unnoticed cancellations. We also prove that PM is numerically stable in finite-precision arithmetic. We believe our analysis will pave the way to providing accurate analysis of known algorithms for the super-resolution problem in full generality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_05883 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the accuracy of Prony's method for recovery of exponential sums with closely spaced exponents Katz, Rami Diab, Nuha Batenkov, Dmitry Numerical Analysis 15A18, 42A70 In this paper we establish accuracy bounds of Prony's method (PM) for recovery of sparse measures from incomplete and noisy frequency measurements, or the so-called problem of super-resolution, when the minimal separation between the points in the support of the measure may be much smaller than the Rayleigh limit. In particular, we show that PM is optimal with respect to the previously established min-max bound for the problem, in the setting when the measurement bandwidth is constant, with the minimal separation going to zero. Our main technical contribution is an accurate analysis of the inter-relations between the different errors in each step of PM, resulting in previously unnoticed cancellations. We also prove that PM is numerically stable in finite-precision arithmetic. We believe our analysis will pave the way to providing accurate analysis of known algorithms for the super-resolution problem in full generality. |
| title | On the accuracy of Prony's method for recovery of exponential sums with closely spaced exponents |
| topic | Numerical Analysis 15A18, 42A70 |
| url | https://arxiv.org/abs/2302.05883 |