S.V. Konyagin, A.Yu. Shadrin. On stable reconstruction of analytic functions from Fourier samples ... P. 182-195

Stability of reconstruction of analytic functions from the values of $2m+1$ coefficients of its Fourier series is studied. The coefficients can be taken from an arbitrary symmetric set $\delta_m \subset \mathbb Z$ of cardinality $2m+1$. It is known that, for $\delta_m=\{ j: |j| \le m\}$, i.e., if the coefficients are consecutive, the fastest possible convergence rate in the case of stable reconstruction is an exponential function of the square root of $m$. Any method with faster convergence is highly unstable. In particular, exponential convergence implies exponential ill-conditioning. In this paper, we show that, if we are free to choose any sets $(\delta_m)$, there exist reconstruction operators $(\phi_{\delta_m})$ that have exponential convergence rate and are almost stable; specifically, their condition numbers grow at most linearly: $\kappa_{\delta_m}<c \cdot m$. We also show that this result cannot be noticeably strengthened. More precisely, for any sets $(\delta_m)$ and any reconstruction operators $(\phi_{\delta_m})$, exponential convergence is possible only if $\kappa_{\delta_m} \ge c \cdot m^{1/2}$.

Keywords: Fourier coefficients, stable reconstruction, polynomial inequalities

Received June 29, 2020

Revised October 10, 2020

Accepted October 19, 2020

Funding Agency: The work of the first author was supported by a grant of the Government of the Russian Federation (project no. 14.W03.31.0031).

Sergey Vladimirovich Konyagin, Prof., Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow, 119991 Russia; Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, 119991 Russia, e-mail: konyagin@mi-ras.ru

Aleksey Yur’evich Shadrin, dr hab., DAMTP, Centre for Mathematical Sciences, University of Cambridge, UK, e-mail: A.Shadrin@damtp.cam.ac.uk

REFERENCES

1.   Adcock B., Hansen A.C. Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon. Appl. Comput. Harmon. Anal., 2012, vol. 32, no. 3, pp. 357–388. doi: 10.1016/j.acha.2011.07.004 

2.   Adcock B., Hansen A.C., Poon C. Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem. SIAM. J. Math. Anal., 2013, vol. 45, pp. 3132–3167. doi: 10.1137/120895846 

3.   Adcock B., Hansen A.C., Shadrin A. A stability barrier for reconstruction from Fourier samples. SIAM. J. Numer. Anal., 2014, vol. 52, pp. 125–139. doi: 10.1137/130908221 

4.   Platte R.B., Trefethen L.N., Kuijlaars A.B.J. Impossibility of fast stable approximation of analytic functions from equispaced samples. SIAM Rev., 2011, vol. 53, no. 2, pp. 308–318. doi: 10.1137/090774707 

5.   Hrycak T., Grochenig K. Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method. J. Comput. Phys., 2010, vol. 229, no. 3, pp. 933–946. doi: 10.1016/j.jcp.2009.10.026 

6.   Rivlin T.J. Chebyshev polynomials. From approximation theory to algebra and number theory. N Y: Wiley, 1990, 249 p. ISBN: 0471628964 .

Cite this article as: S.V. Konyagin, A.Yu. Shadrin. On the stable reconstruction of analytic functions from a sample of Fourier coefficients, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2020, vol. 26, no. 4, pp. 182–195; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 315, Suppl. 1, pp. S178–S191.