## Algebraic Fourier reconstruction of piecewise smooth functions

HTML articles powered by AMS MathViewer

- by Dmitry Batenkov and Yosef Yomdin PDF
- Math. Comp.
**81**(2012), 277-318 Request permission

## Abstract:

Accurate reconstruction of piecewise smooth functions from a finite number of Fourier coefficients is an important problem in various applications. This problem exhibits an inherent inaccuracy, in particular, the Gibbs phenomenon, and it has been intensively investigated during the last few decades. Several nonlinear reconstruction methods have been proposed in the literature, and it is by now well-established that the “classical” convergence order can be completely restored up to the discontinuities. Still, the maximal accuracy of determining the positions of these discontinuities remains an open question.

In this paper we prove that the locations of the jumps (and subsequently the pointwise values of the function) can be reconstructed with at least “half the classical accuracy”. In particular, we develop a constructive approximation procedure which, given the first $k$ Fourier coefficients of a piecewise $C^{2d+1}$ function, recovers the locations of the jumps with accuracy $\sim k^{-\left (d+2\right )}$, and the values of the function between the jumps with accuracy $\sim k^{-\left (d+1\right )}$ (similar estimates are obtained for the associated jump magnitudes). A key ingredient of the algorithm is to start with the case of a single discontinuity, where a modified version of one of the existing algebraic methods (due to K. Eckhoff) may be applied. It turns out that the additional orders of smoothness produce highly correlated error terms in the Fourier coefficients, which eventually cancel out in the corresponding algebraic equations. To handle more than one jump, we apply a localization procedure via a convolution in the Fourier domain, which eventually preserves the accuracy estimates obtained for the single jump. We provide some numerical results which support the theoretical predictions.

## References

- Milton Abramowitz and Irene A. Stegun,
*Handbook of mathematical functions with formulas, graphs, and mathematical tables*, National Bureau of Standards Applied Mathematics Series, No. 55, U. S. Government Printing Office, Washington, D.C., 1964. For sale by the Superintendent of Documents. MR**0167642** - Francesc Arandiga, Albert Cohen, Rosa Donat, and Nira Dyn,
*Interpolation and approximation of piecewise smooth functions*, SIAM J. Numer. Anal.**43**(2005), no. 1, 41–57. MR**2177955**, DOI 10.1137/S0036142903426245 - 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 - Dmitry Batenkov,
*Moment inversion problem for piecewise $D$-finite functions*, Inverse Problems**25**(2009), no. 10, 105001, 24. MR**2545970**, DOI 10.1088/0266-5611/25/10/105001 - D. Batenkov, N. Sarig, and Y. Yomdin. An “algebraic” reconstruction of piecewise-smooth functions from integral measurements.
*Proc. of Sampling Theory and Applications (SAMPTA)*, 2009. - 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 - Pier Luigi Dragotti, Martin Vetterli, and Thierry Blu,
*Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang-Fix*, IEEE Trans. Signal Process.**55**(2007), no. 5, 1741–1757. MR**2472334**, DOI 10.1109/TSP.2006.890907 - 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 - B. Ettinger, N. Sarig, and Y. Yomdin,
*Linear versus non-linear acquisition of step-functions*, J. Geom. Anal.**18**(2008), no. 2, 369–399. MR**2393265**, DOI 10.1007/s12220-008-9016-0 - Alan George and Wai Hung Liu,
*A note on fill for sparse matrices*, SIAM J. Numer. Anal.**12**(1975), 452–455. MR**378383**, DOI 10.1137/0712035 - Anne Gelb and Dennis Cates,
*Segmentation of images from Fourier spectral data*, Commun. Comput. Phys.**5**(2009), no. 2-4, 326–349. MR**2513689** - 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 - Gene H. Golub, Peyman Milanfar, and James Varah,
*A stable numerical method for inverting shape from moments*, SIAM J. Sci. Comput.**21**(1999/00), no. 4, 1222–1243. MR**1740393**, DOI 10.1137/S1064827597328315 - 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 - 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 - Björn Gustafsson, Chiyu He, Peyman Milanfar, and Mihai Putinar,
*Reconstructing planar domains from their moments*, Inverse Problems**16**(2000), no. 4, 1053–1070. MR**1776483**, DOI 10.1088/0266-5611/16/4/312 - 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. Kantorovič and V. I. Krylov,
*Priblizhennye metody vysshego analiza*, Fifth corrected edition, Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow-Leningrad, 1962 (Russian). MR**0154389** - 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 - Yaron Lipman and David Levin,
*Approximating piecewise-smooth functions*, IMA J. Numer. Anal.**30**(2010), no. 4, 1159–1183. MR**2727820**, DOI 10.1093/imanum/drn087 - Yuri I. Lyubich,
*The Sylvester-Ramanujan system of equations and the complex power moment problem*, Ramanujan J.**8**(2004), no. 1, 23–45. MR**2068428**, DOI 10.1023/B:RAMA.0000027196.19661.b7 - 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** - I.P. Natanson.
*Constructive Function Theory (in Russian)*. Gostekhizdat, 1949. - Leszek Plaskota and Grzegorz W. Wasilkowski,
*The power of adaptive algorithms for functions with singularities*, J. Fixed Point Theory Appl.**6**(2009), no. 2, 227–248. MR**2580977**, DOI 10.1007/s11784-009-0121-x - R. Prony. Essai experimental et analytique.
*J. Ec. Polytech.(Paris)*, 2:24–76, 1795. - N. Sarig and Y. Yomdin,
*Signal acquisition from measurements via non-linear models*, C. R. Math. Acad. Sci. Soc. R. Can.**29**(2007), no. 4, 97–114 (English, with English and French summaries). MR**2426609** - 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 - Gábor Szegő,
*Orthogonal polynomials*, 4th ed., American Mathematical Society Colloquium Publications, Vol. XXIII, American Mathematical Society, Providence, R.I., 1975. MR**0372517** - Eitan Tadmor,
*Filters, mollifiers and the computation of the Gibbs phenomenon*, Acta Numer.**16**(2007), 305–378. MR**2417931**, DOI 10.1017/S0962492906320016 - Martin Vetterli, Pina Marziliano, and Thierry Blu,
*Sampling signals with finite rate of innovation*, IEEE Trans. Signal Process.**50**(2002), no. 6, 1417–1428. MR**1930786**, DOI 10.1109/TSP.2002.1003065 - J. Vindas.
*Local Behavior of Distributions and Applications*. PhD thesis, 2009. - 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 - J. H. Wilkinson,
*Rounding errors in algebraic processes*, Dover Publications, Inc., New York, 1994. Reprint of the 1963 original [Prentice-Hall, Englewood Cliffs, NJ; MR0161456 (28 #4661)]. MR**1280465** - A. Zygmund,
*Trigonometric series: Vols. I, II*, Cambridge University Press, London-New York, 1968. Second edition, reprinted with corrections and some additions. MR**0236587**

## Additional Information

**Dmitry Batenkov**- Affiliation: Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
- MR Author ID: 881951
- ORCID: setImmediate$0.09410305223452953$7
- Email: dima.batenkov@weizmann.ac.il
**Yosef Yomdin**- Affiliation: Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
- MR Author ID: 185690
- Email: yosef.yomdin@weizmann.ac.il
- Received by editor(s): May 13, 2010
- Received by editor(s) in revised form: October 25, 2010
- Published electronically: August 30, 2011
- Additional Notes: We would like to thank Ch. Fefferman, E. Tadmor and N. Zobin for useful discussions.

This research was supported by ISF grant 264/09 and the Minerva Foundation. - © Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**81**(2012), 277-318 - MSC (2010): Primary 42A16; Secondary 65T40, 41A25
- DOI: https://doi.org/10.1090/S0025-5718-2011-02539-1
- MathSciNet review: 2833496