Generalized sampling and the stable and accurate reconstruction of piecewise analytic functions from their Fourier coefficients

Adcock, Ben; Hansen, Anders

doi:10.1090/S0025-5718-2014-02860-3

Generalized sampling and the stable and accurate reconstruction of piecewise analytic functions from their Fourier coefficients
HTML articles powered by AMS MathViewer

by Ben Adcock and Anders C. Hansen PDF

Math. Comp. 84 (2015), 237-270 Request permission

Abstract:

Suppose that the first $m$ Fourier coefficients of a piecewise analytic function are given. Direct expansion in a Fourier series suffers from the Gibbs phenomenon and lacks uniform convergence. Nonetheless, in this paper we show that, under very broad conditions, it is always possible to recover an $n$-term expansion in a different system of functions using only these coefficients. Such an expansion can be made arbitrarily close to the best possible $n$-term expansion in the given system. Thus, if a piecewise polynomial basis is employed, for example, exponential convergence can be restored. The resulting method is linear, numerically stable and can be implemented efficiently in only $\mathcal {O} \left (n m\right )$ operations.

A key issue is how the parameter $m$ must scale in comparison to $n$ to ensure such recovery. We derive analytical estimates for this scaling for large classes of polynomial and piecewise polynomial bases. In particular, we show that in many important cases, including the case of piecewise Chebyshev polynomials, this scaling is quadratic: $m=\mathcal {O}\left (n^2\right )$. Therefore, with a system of polynomials that the user is essentially free to choose, one can restore exponential accuracy in $n$ and root-exponential accuracy in $m$. This generalizes a result proved recently for piecewise Legendre polynomials.

References

M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions. Dover, 1974.
Ben Adcock, Convergence acceleration of modified Fourier series in one or more dimensions, Math. Comp. 80 (2011), no. 273, 225–261. MR 2728978, DOI 10.1090/S0025-5718-2010-02393-2
Ben Adcock, Gibbs phenomenon and its removal for a class of orthogonal expansions, BIT 51 (2011), no. 1, 7–41. MR 2784651, DOI 10.1007/s10543-010-0301-5
B. Adcock and A. C. Hansen, Generalized sampling and infinite-dimensional compressed sensing, Technical report NA2011/02, DAMTP, University of Cambridge, 2011.
Ben Adcock and Anders C. Hansen, A generalized sampling theorem for stable reconstructions in arbitrary bases, J. Fourier Anal. Appl. 18 (2012), no. 4, 685–716. MR 2984365, DOI 10.1007/s00041-012-9221-x
Ben Adcock and Anders C. Hansen, Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon, Appl. Comput. Harmon. Anal. 32 (2012), no. 3, 357–388. MR 2892739, DOI 10.1016/j.acha.2011.07.004
Ben Adcock, Anders C. Hansen, Evelyn Herrholz, and Gerd Teschke, Generalized sampling: extension to frames and inverse and ill-posed problems, Inverse Problems 29 (2013), no. 1, 015008, 27. MR 3005700, DOI 10.1088/0266-5611/29/1/015008
Ben Adcock, Anders C. Hansen, and Clarice Poon, Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem, SIAM J. Math. Anal. 45 (2013), no. 5, 3132–3167. MR 3116643, DOI 10.1137/120895846
Ben Adcock, Anders C. Hansen, and Alexei Shadrin, A stability barrier for reconstructions from Fourier samples, SIAM J. Numer. Anal. 52 (2014), no. 1, 125–139. MR 3151387, DOI 10.1137/130908221
R. Archibald, K. Chen, A. Gelb, and R. Renaut, Improving tissue segmentation of human brain MRI through preprocessing by the Gegenbauer reconstruction method, NeuroImage, 20(1):489–502, 2003.
R. Archibald and A. Gelb, A method to reduce the Gibbs ringing artifact in MRI scans while keeping tissue boundary integrity, IEEE Transactions on Medical Imaging, 21(4):305–319, 2002.
D. Batenkov, Complete algebraic reconstruction of piecewise-smooth functions from Fourier data, Math. Comp. (accepted).
Dmitry Batenkov and Yosef Yomdin, Algebraic Fourier reconstruction of piecewise smooth functions, Math. Comp. 81 (2012), no. 277, 277–318. MR 2833496, DOI 10.1090/S0025-5718-2011-02539-1
Bernhard Beckermann, Valeriy Kalyagin, Ana C. Matos, and Franck Wielonsky, How well does the Hermite-Padé approximation smooth the Gibbs phenomenon?, Math. Comp. 80 (2011), no. 274, 931–958. MR 2772102, DOI 10.1090/S0025-5718-2010-02411-1
N. Borovykh and M. N. Spijker, Bounding partial sums of Fourier series in weighted $L^2$-norms, with applications to matrix analysis, J. Comput. Appl. Math. 147 (2002), no. 2, 349–368. MR 1933601, DOI 10.1016/S0377-0427(02)00441-7
Peter Borwein and Tamás Erdélyi, Polynomials and polynomial inequalities, Graduate Texts in Mathematics, vol. 161, Springer-Verlag, New York, 1995. MR 1367960, DOI 10.1007/978-1-4612-0793-1
J. P. Boyd, Chebyshev and Fourier Spectral Methods, Springer–Verlag, 1989.
John P. Boyd, Trouble with Gegenbauer reconstruction for defeating Gibbs’ phenomenon: Runge phenomenon in the diagonal limit of Gegenbauer polynomial approximations, J. Comput. Phys. 204 (2005), no. 1, 253–264. MR 2121910, DOI 10.1016/j.jcp.2004.10.008
John P. Boyd, Acceleration of algebraically-converging Fourier series when the coefficients have series in powers in $1/n$, J. Comput. Phys. 228 (2009), no. 5, 1404–1411. MR 2494223, DOI 10.1016/j.jcp.2008.10.039
C. Brezinski, Extrapolation algorithms for filtering series of functions, and treating the Gibbs phenomenon, Numer. Algorithms 36 (2004), no. 4, 309–329. MR 2108182, DOI 10.1007/s11075-004-2843-6
C. Canuto, M. Y. Hussaini, A. Quarteroni, and T. A. Zang, Spectral methods, Scientific Computation, Springer-Verlag, Berlin, 2006. Fundamentals in single domains. MR 2223552, DOI 10.1007/978-3-540-30726-6
V. Domínguez, I. G. Graham, and V. P. Smyshlyaev, Stability and error estimates for Filon-Clenshaw-Curtis rules for highly oscillatory integrals, IMA J. Numer. Anal. 31 (2011), no. 4, 1253–1280. MR 2846755, DOI 10.1093/imanum/drq036
Tobin A. Driscoll and Bengt Fornberg, A Padé-based algorithm for overcoming the Gibbs phenomenon, Numer. Algorithms 26 (2001), no. 1, 77–92. MR 1827318, DOI 10.1023/A:1016648530648
Knut S. Eckhoff, Accurate and efficient reconstruction of discontinuous functions from truncated series expansions, Math. Comp. 61 (1993), no. 204, 745–763. MR 1195430, DOI 10.1090/S0025-5718-1993-1195430-1
Knut S. Eckhoff, Accurate reconstructions of functions of finite regularity from truncated Fourier series expansions, Math. Comp. 64 (1995), no. 210, 671–690. MR 1265014, DOI 10.1090/S0025-5718-1995-1265014-7
Knut S. Eckhoff, On a high order numerical method for functions with singularities, Math. Comp. 67 (1998), no. 223, 1063–1087. MR 1459387, DOI 10.1090/S0025-5718-98-00949-1
John B. Garnett, Bounded analytic functions, 1st ed., Graduate Texts in Mathematics, vol. 236, Springer, New York, 2007. MR 2261424
A. Gelb and S. Gottlieb, The resolution of the Gibbs phenomenon for Fourier spectral methods, In A. Jerri, editor, Advances in The Gibbs Phenomenon, Sampling Publishing, Potsdam, New York, 2007.
Anne Gelb and Eitan Tadmor, Detection of edges in spectral data, Appl. Comput. Harmon. Anal. 7 (1999), no. 1, 101–135. MR 1699594, DOI 10.1006/acha.1999.0262
Anne Gelb and Jared Tanner, Robust reprojection methods for the resolution of the Gibbs phenomenon, Appl. Comput. Harmon. Anal. 20 (2006), no. 1, 3–25. MR 2200928, DOI 10.1016/j.acha.2004.12.007
D. Gottlieb and J. S. Hesthaven, Spectral methods for hyperbolic problems, J. Comput. Appl. Math. 128 (2001), no. 1-2, 83–131. Numerical analysis 2000, Vol. VII, Partial differential equations. MR 1820872, DOI 10.1016/S0377-0427(00)00510-0
David Gottlieb and Chi-Wang Shu, On the Gibbs phenomenon. III. Recovering exponential accuracy in a sub-interval from a spectral partial sum of a piecewise analytic function, SIAM J. Numer. Anal. 33 (1996), no. 1, 280–290. MR 1377254, DOI 10.1137/0733015
David Gottlieb and Chi-Wang Shu, On the Gibbs phenomenon and its resolution, SIAM Rev. 39 (1997), no. 4, 644–668. MR 1491051, DOI 10.1137/S0036144596301390
David Gottlieb, Chi-Wang Shu, Alex Solomonoff, and Hervé Vandeven, On the Gibbs phenomenon. I. Recovering exponential accuracy from the Fourier partial sum of a nonperiodic analytic function, J. Comput. Appl. Math. 43 (1992), no. 1-2, 81–98. Orthogonal polynomials and numerical methods. MR 1193295, DOI 10.1016/0377-0427(92)90260-5
Ben-Yu Guo, Jie Shen, and Li-Lian Wang, Optimal spectral-Galerkin methods using generalized Jacobi polynomials, J. Sci. Comput. 27 (2006), no. 1-3, 305–322. MR 2285783, DOI 10.1007/s10915-005-9055-7
Ben-Yu Guo, Jie Shen, and Li-Lian Wang, Generalized Jacobi polynomials/functions and their applications, Appl. Numer. Math. 59 (2009), no. 5, 1011–1028. MR 2495135, DOI 10.1016/j.apnum.2008.04.003
Anders C. Hansen, On the approximation of spectra of linear operators on Hilbert spaces, J. Funct. Anal. 254 (2008), no. 8, 2092–2126. MR 2402104, DOI 10.1016/j.jfa.2008.01.006
Anders C. Hansen, On the solvability complexity index, the $n$-pseudospectrum and approximations of spectra of operators, J. Amer. Math. Soc. 24 (2011), no. 1, 81–124. MR 2726600, DOI 10.1090/S0894-0347-2010-00676-5
Henry Helson and Gabor Szegö, A problem in prediction theory, Ann. Mat. Pura Appl. (4) 51 (1960), 107–138. MR 121608, DOI 10.1007/BF02410947
Jan S. Hesthaven, Sigal Gottlieb, and David Gottlieb, Spectral methods for time-dependent problems, Cambridge Monographs on Applied and Computational Mathematics, vol. 21, Cambridge University Press, Cambridge, 2007. MR 2333926, DOI 10.1017/CBO9780511618352
Tomasz Hrycak and Karlheinz Gröchenig, Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method, J. Comput. Phys. 229 (2010), no. 3, 933–946. MR 2566372, DOI 10.1016/j.jcp.2009.10.026
Richard Hunt, Benjamin Muckenhoupt, and Richard Wheeden, Weighted norm inequalities for the conjugate function and Hilbert transform, Trans. Amer. Math. Soc. 176 (1973), 227–251. MR 312139, DOI 10.1090/S0002-9947-1973-0312139-8
Bernie D. Shizgal and Jae-Hun Jung, Towards the resolution of the Gibbs phenomena, J. Comput. Appl. Math. 161 (2003), no. 1, 41–65. MR 2018574, DOI 10.1016/S0377-0427(03)00500-4
Jae-Hun Jung and Bernie D. Shizgal, Generalization of the inverse polynomial reconstruction method in the resolution of the Gibbs phenomenon, J. Comput. Appl. Math. 172 (2004), no. 1, 131–151. MR 2091135, DOI 10.1016/j.cam.2004.02.003
A. B. J. Kuijlaars, K. T.-R. McLaughlin, W. Van Assche, and M. Vanlessen, The Riemann-Hilbert approach to strong asymptotics for orthogonal polynomials on $[-1,1]$, Adv. Math. 188 (2004), no. 2, 337–398. MR 2087231, DOI 10.1016/j.aim.2003.08.015
J. N. Lyness, Computational techniques based on the Lanczos representation, Math. Comp. 28 (1974), 81–123. MR 334458, DOI 10.1090/S0025-5718-1974-0334458-6
Jacob Steinberg, Oblique projections in Hilbert spaces, Integral Equations Operator Theory 38 (2000), no. 1, 81–119. MR 1778180, DOI 10.1007/BF01192303
Daniel B. Szyld, The many proofs of an identity on the norm of oblique projections, Numer. Algorithms 42 (2006), no. 3-4, 309–323. MR 2279449, DOI 10.1007/s11075-006-9046-2
Eitan Tadmor, Filters, mollifiers and the computation of the Gibbs phenomenon, Acta Numer. 16 (2007), 305–378. MR 2417931, DOI 10.1017/S0962492906320016
Eitan Tadmor and Jared Tanner, Adaptive mollifiers for high resolution recovery of piecewise smooth data from its spectral information, Found. Comput. Math. 2 (2002), no. 2, 155–189. MR 1894374, DOI 10.1007/s102080010019
Wai-Shing Tang, Oblique projections, biorthogonal Riesz bases and multiwavelets in Hilbert spaces, Proc. Amer. Math. Soc. 128 (2000), no. 2, 463–473. MR 1626494, DOI 10.1090/S0002-9939-99-05075-3