Complete algebraic reconstruction of piecewise-smooth functions from Fourier data

Batenkov, Dmitry

doi:10.1090/S0025-5718-2015-02948-2

Complete algebraic reconstruction of piecewise-smooth functions from Fourier data
HTML articles powered by AMS MathViewer

by Dmitry Batenkov PDF

Math. Comp. 84 (2015), 2329-2350 Request permission

Abstract:

In this paper we provide a reconstruction algorithm for piecewise-smooth functions with a priori known smoothness and a number of discontinuities, from their Fourier coefficients, possessing the maximal possible asymptotic rate of convergence—including the positions of the discontinuities and the pointwise values of the function. This algorithm is a modification of our earlier method, which is in turn based on the algebraic method of K. Eckhoff proposed in the 1990s. The key ingredient of the new algorithm is to use a different set of Eckhoff’s equations for reconstructing the location of each discontinuity. Instead of consecutive Fourier samples, we propose to use a “decimated” set which is evenly spread throughout the spectrum.

References

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
J. R. Auton, Investigation of Procedures for Automatic Resonance Extraction from Noisy Transient Electromagnetics Data. Volume III, Translation of Prony’s Original Paper and Bibliography of Prony’s Method. Technical report, Effects Technology Inc., Santa Barbara, CA, 1981.
Nana S. Banerjee and James F. Geer, Exponentially accurate approximations to periodic Lipschitz functions based on Fourier series partial sums, J. Sci. Comput. 13 (1998), no. 4, 419–460. MR 1676752, DOI 10.1023/A:1023289301743
A. Barkhudaryan, R. Barkhudaryan, and A. Poghosyan, Asymptotic behavior of Eckhoff’s method for Fourier series convergence acceleration, Anal. Theory Appl. 23 (2007), no. 3, 228–242. MR 2350105, DOI 10.1007/s10496-007-0228-0
Riccardo March and Piero Barone, Reconstruction of a piecewise constant function from noisy Fourier coefficients by Padé method, SIAM J. Appl. Math. 60 (2000), no. 4, 1137–1156. MR 1760030, DOI 10.1137/S0036139998333841
D. Batenkov, Decimated generalized Prony systems, preprint, 2013.
D. Batenkov, V. Golubyatnikov, and Y. Yomdin, Reconstruction of planar domains from partial integral measurements, Complex analysis and dynamical systems V, Contemp. Math., vol. 591, Amer. Math. Soc., Providence, RI, 2013, pp. 51–66. MR 3155677, DOI 10.1090/conm/591/11826
D. Batenkov and Y. Yomdin, Geometry and singularities of the Prony mapping, Journal of Singularities 10 (2014), 1–25, Proceedings of 12th International Workshop on Real and Complex Singularities.
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
Dmitry Batenkov and Yosef Yomdin, On the accuracy of solving confluent Prony systems, SIAM J. Appl. Math. 73 (2013), no. 1, 134–154. MR 3033143, DOI 10.1137/110836584
R. Bauer, Band filters for determining shock locations, PhD thesis, Department of Applied Mathematics, Brown University, Providence, RI, 1995.
Bernhard Beckermann, Ana C. Matos, and Franck Wielonsky, Reduction of the Gibbs phenomenon for smooth functions with jumps by the $\epsilon$-algorithm, J. Comput. Appl. Math. 219 (2008), no. 2, 329–349. MR 2441229, DOI 10.1016/j.cam.2007.11.011
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
Emmanuel J. Candès and Carlos Fernandez-Granda, Towards a mathematical theory of super-resolution, Comm. Pure Appl. Math. 67 (2014), no. 6, 906–956. MR 3193963, DOI 10.1002/cpa.21455
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
Saber Elaydi, An introduction to difference equations, 3rd ed., Undergraduate Texts in Mathematics, Springer, New York, 2005. MR 2128146
Shlomo Engelberg and Eitan Tadmor, Recovery of edges from spectral data with noise—a new perspective, SIAM J. Numer. Anal. 46 (2008), no. 5, 2620–2635. MR 2421050, DOI 10.1137/070689899
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
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 and Steven A. Orszag, Numerical analysis of spectral methods: theory and applications, CBMS-NSF Regional Conference Series in Applied Mathematics, No. 26, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1977. MR 0520152
Christian Guilpin, Jacques Gacougnolle, and Yvan Simon, The $\epsilon$-algorithm allows to detect Dirac delta functions, Appl. Numer. Math. 48 (2004), no. 1, 27–40. MR 2027820, DOI 10.1016/S0168-9274(03)00104-1
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
L. V. Kantorovich and V. I. Krylov, Approximate methods of higher analysis, Interscience Publishers, Inc., New York; P. Noordhoff Ltd., Groningen 1958. Translated from the 3rd Russian edition by C. D. Benster. MR 0106537
George Kvernadze, Approximating the jump discontinuities of a function by its Fourier-Jacobi coefficients, Math. Comp. 73 (2004), no. 246, 731–751. MR 2031403, DOI 10.1090/S0025-5718-03-01594-1
George Kvernadze, Approximation of the discontinuities of a function by its classical orthogonal polynomial Fourier coefficients, Math. Comp. 79 (2010), no. 272, 2265–2285. MR 2684364, DOI 10.1090/S0025-5718-10-02366-5
H. N. Mhaskar and J. Prestin, Polynomial frames for the detection of singularities, Wavelet analysis and multiresolution methods (Urbana-Champaign, IL, 1999) Lecture Notes in Pure and Appl. Math., vol. 212, Dekker, New York, 2000, pp. 273–298. MR 1777997
Arnak Poghosyan, Asymptotic behavior of the Eckhoff method for convergence acceleration of trigonometric interpolation, Anal. Theory Appl. 26 (2010), no. 3, 236–260. MR 2728116, DOI 10.1007/s10496-010-0236-3
Arnak Poghosyan, On an auto-correction phenomenon of the Krylov-Gottlieb-Eckhoff method, IMA J. Numer. Anal. 31 (2011), no. 2, 512–527. MR 2813182, DOI 10.1093/imanum/drp043
R. Prony, Essai experimental et analytique, J. Ecole Polytech. (Paris), no. 2, 24–76, 1795.
B. D. Rao and K. S. Arun, Model based processing of signals: A state space approach, Proceedings of the IEEE 80 (1992), no. 2, 283–309.
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
Alex Solomonoff, Reconstruction of a discontinuous function from a few Fourier coefficients using Bayesian estimation, J. Sci. Comput. 10 (1995), no. 1, 29–80. MR 1337448, DOI 10.1007/BF02087960
Eitan Tadmor, Filters, mollifiers and the computation of the Gibbs phenomenon, Acta Numer. 16 (2007), 305–378. MR 2417931, DOI 10.1017/S0962492906320016
Musheng Wei, Ana Gabriela Martínez, and Alvaro R. De Pierro, Detection of edges from spectral data: new results, Appl. Comput. Harmon. Anal. 22 (2007), no. 3, 386–393. MR 2311863, DOI 10.1016/j.acha.2006.10.002
Y. Yomdin, Singularities in algebraic data acquisition, Real and complex singularities, London Math. Soc. Lecture Note Ser., vol. 380, Cambridge Univ. Press, Cambridge, 2010, pp. 378–396. MR 2759050
A. Zygmund, Trigonometric series: Vols. I, II, Cambridge University Press, London-New York, 1968. Second edition, reprinted with corrections and some additions. MR 0236587