Algebraic Fourier reconstruction of piecewise smooth functions

Authors:
Dmitry Batenkov and Yosef Yomdin

Journal:
Math. Comp. **81** (2012), 277-318

MSC (2010):
Primary 42A16; Secondary 65T40, 41A25

Published electronically:
August 30, 2011

MathSciNet review:
2833496

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 Fourier coefficients of a piecewise function, recovers the locations of the jumps with accuracy , and the values of the function between the jumps with accuracy (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.

**1.**Milton Abramowitz and Irene A. Stegun,*Handbook of mathematical functions with formulas, graphs, and mathematical tables*, National Bureau of Standards Applied Mathematics Series, vol. 55, For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C., 1964. MR**0167642****2.**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 (electronic). MR**2177955**, 10.1137/S0036142903426245**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**, 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**, 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 (electronic). MR**1760030**, 10.1137/S0036139998333841**6.**Dmitry Batenkov,*Moment inversion problem for piecewise 𝐷-finite functions*, Inverse Problems**25**(2009), no. 10, 105001, 24. MR**2545970**, 10.1088/0266-5611/25/10/105001**7.**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.**8.**R. Bauer.*Band filters for determining shock locations*.

PhD thesis, Department of Applied Mathematics, Brown University, Providence, RI, 1995.**9.**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**, 10.1016/j.cam.2007.11.011**10.**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**, 10.1016/j.jcp.2008.10.039**11.**C. Brezinski,*Extrapolation algorithms for filtering series of functions, and treating the Gibbs phenomenon*, Numer. Algorithms**36**(2004), no. 4, 309–329. MR**2108182**, 10.1007/s11075-004-2843-6**12.**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**, 10.1109/TSP.2006.890907**13.**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**, 10.1023/A:1016648530648**14.**Knut S. Eckhoff,*Accurate and efficient reconstruction of discontinuous functions from truncated series expansions*, Math. Comp.**61**(1993), no. 204, 745–763. MR**1195430**, 10.1090/S0025-5718-1993-1195430-1**15.**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**, 10.1090/S0025-5718-1995-1265014-7**16.**Knut S. Eckhoff,*On a high order numerical method for functions with singularities*, Math. Comp.**67**(1998), no. 223, 1063–1087. MR**1459387**, 10.1090/S0025-5718-98-00949-1**17.**Saber Elaydi,*An introduction to difference equations*, 3rd ed., Undergraduate Texts in Mathematics, Springer, New York, 2005. MR**2128146****18.**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**, 10.1137/070689899**19.**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**, 10.1007/s12220-008-9016-0**20.**Alan George and Wai Hung Liu,*A note on fill for sparse matrices*, SIAM J. Numer. Anal.**12**(1975), 452–455. MR**0378383****21.**Anne Gelb and Dennis Cates,*Segmentation of images from Fourier spectral data*, Commun. Comput. Phys.**5**(2009), no. 2-4, 326–349. MR**2513689****22.**Anne Gelb and Eitan Tadmor,*Detection of edges in spectral data*, Appl. Comput. Harmon. Anal.**7**(1999), no. 1, 101–135. MR**1699594**, 10.1006/acha.1999.0262**23.**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 (electronic). MR**1740393**, 10.1137/S1064827597328315**24.**David Gottlieb and Chi-Wang Shu,*On the Gibbs phenomenon and its resolution*, SIAM Rev.**39**(1997), no. 4, 644–668. MR**1491051**, 10.1137/S0036144596301390**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**, 10.1016/S0168-9274(03)00104-1**26.**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**, 10.1088/0266-5611/16/4/312**27.**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**, 10.1016/j.jcp.2009.10.026**28.**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****29.**George Kvernadze,*Approximating the jump discontinuities of a function by its Fourier-Jacobi coefficients*, Math. Comp.**73**(2004), no. 246, 731–751. MR**2031403**, 10.1090/S0025-5718-03-01594-1**30.**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**, 10.1090/S0025-5718-10-02366-5**31.**Yaron Lipman and David Levin,*Approximating piecewise-smooth functions*, IMA J. Numer. Anal.**30**(2010), no. 4, 1159–1183. MR**2727820**, 10.1093/imanum/drn087**32.**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**, 10.1023/B:RAMA.0000027196.19661.b7**33.**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****34.**I.P. Natanson.*Constructive Function Theory (in Russian)*.

Gostekhizdat, 1949.**35.**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**, 10.1007/s11784-009-0121-x**36.**R. Prony.

Essai experimental et analytique.*J. Ec. Polytech.(Paris)*, 2:24-76, 1795.**37.**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****38.**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**, 10.1016/S0377-0427(03)00500-4**39.**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**, 10.1007/BF02087960**40.**Gábor Szegő,*Orthogonal polynomials*, 4th ed., American Mathematical Society, Providence, R.I., 1975. American Mathematical Society, Colloquium Publications, Vol. XXIII. MR**0372517****41.**Eitan Tadmor,*Filters, mollifiers and the computation of the Gibbs phenomenon*, Acta Numer.**16**(2007), 305–378. MR**2417931**, 10.1017/S0962492906320016**42.**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**, 10.1109/TSP.2002.1003065**43.**J. Vindas.*Local Behavior of Distributions and Applications*.

PhD thesis, 2009.**44.**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**, 10.1016/j.acha.2006.10.002**45.**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****46.**A. Zygmund,*Trigonometric series: Vols. I, II*, Second edition, reprinted with corrections and some additions, Cambridge University Press, London-New York, 1968. MR**0236587**

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
42A16,
65T40,
41A25

Retrieve articles in all journals with MSC (2010): 42A16, 65T40, 41A25

Additional Information

**Dmitry Batenkov**

Affiliation:
Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel

Email:
dima.batenkov@weizmann.ac.il

**Yosef Yomdin**

Affiliation:
Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel

Email:
yosef.yomdin@weizmann.ac.il

DOI:
https://doi.org/10.1090/S0025-5718-2011-02539-1

Keywords:
Fourier inversion,
nonlinear approximation,
piecewise smooth functions

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.

Article copyright:
© Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.