On Stable Reconstruction of Analytic Functions from Fourier Samples

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 the sets $(\delta_m)$ are chosen freely, 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\,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\,m^{1/2}$.