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.
