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

Author: Dmitry Batenkov
Journal: Math. Comp. 84 (2015), 2329-2350
MSC (2010): Primary 65T40; Secondary 65D15
DOI: https://doi.org/10.1090/S0025-5718-2015-02948-2
Published electronically: February 19, 2015
MathSciNet review: 3356028
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

[1] 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, https://doi.org/10.1137/130908221
[2] 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.
[3] 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, https://doi.org/10.1023/A:1023289301743
[4] 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, https://doi.org/10.1007/s10496-007-0228-0
[5] 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, https://doi.org/10.1137/S0036139998333841
[6] D. Batenkov, Decimated generalized Prony systems,
preprint, 2013.
[7] 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, https://doi.org/10.1090/conm/591/11826
[8] 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.
[9] Dmitry Batenkov and Yosef Yomdin, Algebraic Fourier reconstruction of piecewise smooth functions, Math. Comp. 81 (2012), no. 277, 277–318. MR 2833496, https://doi.org/10.1090/S0025-5718-2011-02539-1
[10] 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, https://doi.org/10.1137/110836584
[11] R. Bauer,
Band filters for determining shock locations,
PhD thesis, Department of Applied Mathematics, Brown University, Providence, RI, 1995.
[12] Bernhard Beckermann, Ana C. Matos, and Franck Wielonsky, Reduction of the Gibbs phenomenon for smooth functions with jumps by the 𝜀-algorithm, J. Comput. Appl. Math. 219 (2008), no. 2, 329–349. MR 2441229, https://doi.org/10.1016/j.cam.2007.11.011
[13] John P. Boyd, Acceleration of algebraically-converging Fourier series when the coefficients have series in powers in 1/𝑛, J. Comput. Phys. 228 (2009), no. 5, 1404–1411. MR 2494223, https://doi.org/10.1016/j.jcp.2008.10.039
[14] C. Brezinski, Extrapolation algorithms for filtering series of functions, and treating the Gibbs phenomenon, Numer. Algorithms 36 (2004), no. 4, 309–329. MR 2108182, https://doi.org/10.1007/s11075-004-2843-6
[15] 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, https://doi.org/10.1002/cpa.21455
[16] 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, https://doi.org/10.1023/A:1016648530648
[17] Knut S. Eckhoff, Accurate and efficient reconstruction of discontinuous functions from truncated series expansions, Math. Comp. 61 (1993), no. 204, 745–763. MR 1195430, https://doi.org/10.1090/S0025-5718-1993-1195430-1
[18] 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, https://doi.org/10.1090/S0025-5718-1995-1265014-7
[19] Knut S. Eckhoff, On a high order numerical method for functions with singularities, Math. Comp. 67 (1998), no. 223, 1063–1087. MR 1459387, https://doi.org/10.1090/S0025-5718-98-00949-1
[20] Saber Elaydi, An introduction to difference equations, 3rd ed., Undergraduate Texts in Mathematics, Springer, New York, 2005. MR 2128146
[21] 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, https://doi.org/10.1137/070689899
[22] Anne Gelb and Eitan Tadmor, Detection of edges in spectral data, Appl. Comput. Harmon. Anal. 7 (1999), no. 1, 101–135. MR 1699594, https://doi.org/10.1006/acha.1999.0262
[23] David Gottlieb and Chi-Wang Shu, On the Gibbs phenomenon and its resolution, SIAM Rev. 39 (1997), no. 4, 644–668. MR 1491051, https://doi.org/10.1137/S0036144596301390
[24] David Gottlieb and Steven A. Orszag, Numerical analysis of spectral methods: theory and applications, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1977. CBMS-NSF Regional Conference Series in Applied Mathematics, No. 26. MR 0520152
[25] Christian Guilpin, Jacques Gacougnolle, and Yvan Simon, The 𝜀-algorithm allows to detect Dirac delta functions, Appl. Numer. Math. 48 (2004), no. 1, 27–40. MR 2027820, https://doi.org/10.1016/S0168-9274(03)00104-1
[26] 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, https://doi.org/10.1016/j.jcp.2009.10.026
[27] L. V. Kantorovich and V. I. Krylov, Approximate methods of higher analysis, Translated from the 3rd Russian edition by C. D. Benster, Interscience Publishers, Inc., New York; P. Noordhoff Ltd., Groningen, 1958. MR 0106537
[28] George Kvernadze, Approximating the jump discontinuities of a function by its Fourier-Jacobi coefficients, Math. Comp. 73 (2004), no. 246, 731–751. MR 2031403, https://doi.org/10.1090/S0025-5718-03-01594-1
[29] 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, https://doi.org/10.1090/S0025-5718-10-02366-5
[30] 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
[31] 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, https://doi.org/10.1007/s10496-010-0236-3
[32] 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, https://doi.org/10.1093/imanum/drp043
[33] R. Prony, Essai experimental et analytique, J. Ecole Polytech. (Paris), no. 2, 24-76, 1795.
[34] 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.
[35] 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, https://doi.org/10.1016/S0377-0427(03)00500-4
[36] 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, https://doi.org/10.1007/BF02087960
[37] Eitan Tadmor, Filters, mollifiers and the computation of the Gibbs phenomenon, Acta Numer. 16 (2007), 305–378. MR 2417931, https://doi.org/10.1017/S0962492906320016
[38] 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, https://doi.org/10.1016/j.acha.2006.10.002
[39] 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
[40] A. Zygmund, Trigonometric series: Vols. I, II, Second edition, reprinted with corrections and some additions, Cambridge University Press, London-New York, 1968. MR 0236587