Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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 $ 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 [Enhancements On Off] (What's this?)

  • 1. M. Abramowitz and I.A. Stegun.
    Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables.
    National Bureau of Standards Applied Math. Ser., 55, U.S. Govt. Printing Office, Washington, D. C., 1964. MR 0167642 (29:4914)
  • 2. F. Arandiga, A. Cohen, R. Donat, and N. Dyn.
    Interpolation and approximation of piecewise smooth functions.
    SIAM Journal on Numerical Analysis, 43:41, 2005. MR 2177955 (2006h:41002)
  • 3. N.S. Banerjee and J.F. Geer.
    Exponentially accurate approximations to periodic Lipschitz functions based on Fourier series partial sums.
    Journal of Scientific Computing, 13(4):419-460, 1998. MR 1676752 (2000b:65020)
  • 4. A. Barkhudaryan, R. Barkhudaryan, and A. Poghosyan.
    Asymptotic behavior of Eckhoff's method for Fourier series convergence acceleration.
    Analysis in Theory and Applications, 23(3):228-242, 2007. MR 2350105 (2010e:42002)
  • 5. P. Barone and R. March.
    Reconstruction of a piecewise constant function from noisy Fourier coefficients by Padé method.
    SIAM Journal on Applied Mathematics, 60(4):1137-1156, 2000. MR 1760030 (2001b:41018)
  • 6. D. Batenkov.
    Moment inversion problem for piecewise D-finite functions.
    Inverse Problems, 25(10):105001, October 2009. MR 2545970 (2011a:44011)
  • 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. B. Beckermann, A.C. Matos, and F. Wielonsky.
    Reduction of the Gibbs phenomenon for smooth functions with jumps by the $ \varepsilon$-algorithm.
    Journal of Computational and Applied Mathematics, 219(2):329-349, 2008. MR 2441229 (2009h:41011)
  • 10. John P. Boyd.
    Acceleration of algebraically-converging fourier series when the coefficients have series in powers of 1/n.
    Journal of Computational Physics, 228(5):1404-1411, 2009. MR 2494223 (2010b:65311)
  • 11. C. Brezinski.
    Extrapolation algorithms for filtering series of functions, and treating the Gibbs phenomenon.
    Numerical Algorithms, 36(4):309-329, 2004. MR 2108182 (2005g:42005)
  • 12. P.L. Dragotti, M. Vetterli, and T. Blu.
    Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang-Fix.
    IEEE Transactions on Signal Processing, 55(5):1741, 2007. MR 2472334 (2010f:94150)
  • 13. T.A. Driscoll and B. Fornberg.
    A Padé-based algorithm for overcoming the Gibbs phenomenon.
    Numerical Algorithms, 26(1):77-92, 2001. MR 1827318 (2002b:65007)
  • 14. K.S. Eckhoff.
    Accurate and efficient reconstruction of discontinuous functions from truncated series expansions.
    Mathematics of Computation, 61(204):745-763, 1993. MR 1195430 (94a:65073)
  • 15. K.S. Eckhoff.
    Accurate reconstructions of functions of finite regularity from truncated Fourier series expansions.
    Mathematics of Computation, 64(210):671-690, 1995. MR 1265014 (95f:65234)
  • 16. K.S. Eckhoff.
    On a high order numerical method for functions with singularities.
    Mathematics of Computation, 67(223):1063-1088, 1998. MR 1459387 (98j:65014)
  • 17. S. Elaydi.
    An Introduction to Difference Equations.
    Springer, 2005. MR 2128146 (2005j:39001)
  • 18. S. Engelberg and E. Tadmor.
    Recovery of edges from spectral data with noise - a new perspective.
    SIAM Journal on Numerical Analysis, 46(5):2620-2635, 2008. MR 2421050 (2009d:42005)
  • 19. B. Ettinger, N. Sarig, and Y. Yomdin.
    Linear versus non-linear acquisition of step-functions.
    Journal of Geometric Analysis, 18(2):369-399, 2008. MR 2393265 (2009e:41056)
  • 20. W. Gautschi.
    Norm estimates for inverses of Vandermonde matrices.
    Numerische Mathematik, 23(4):337-347, 1974. MR 0378383 (51:14550)
  • 21. A. Gelb and D. Cates.
    Segmentation of Images from Fourier Spectral Data.
    Commun. Comput. Phys., 5:326-349, 2009. MR 2513689 (2010c:65263)
  • 22. A. Gelb and E. Tadmor.
    Detection of edges in spectral data.
    Applied and Computational Harmonic Analysis, 7(1):101, 1999. MR 1699594 (2000g:42003)
  • 23. G.H. Golub, P. Milanfar, and J. Varah.
    A stable numerical method for inverting shape from moments.
    SIAM Journal on Scientific Computing, 21(4):1222-1243, 2000. MR 1740393 (2000m:65048)
  • 24. D. Gottlieb and C.W. Shu.
    On the Gibbs phenomenon and its resolution.
    SIAM Review, pages 644-668, 1997. MR 1491051 (98m:42002)
  • 25. C. Guilpin, J. Gacougnolle, and Y. Simon.
    The $ \varepsilon$-algorithm allows to detect Dirac delta functions.
    Applied Numerical Mathematics, 48(1):27-40, 2004. MR 2027820 (2004j:65011)
  • 26. B. Gustafsson, C. He, P. Milanfar, and M. Putinar.
    Reconstructing planar domains from their moments.
    Inverse Problems, 16(4):1053-1070, 2000. MR 1776483 (2001k:44010)
  • 27. T. Hrycak and K. Gröchenig.
    Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method.
    Journal of Computational Physics, 229(3):933-946, 2010. MR 2566372 (2010k:65313)
  • 28. L.V. Kantorovich and V.I. Krylov.
    Approximate Methods of Higher Analysis.
    Fizmatgiz, Moscow, 1962. MR 0154389 (27:4338)
  • 29. G. Kvernadze.
    Approximating the jump discontinuities of a function by its Fourier-Jacobi coefficients.
    Mathematics of Computation, 73(246):731-752, 2004. MR 2031403 (2004j:42026)
  • 30. G. Kvernadze.
    Approximation of the discontinuities of a function by its classical orthogonal polynomial Fourier coefficients.
    Math. Comp, 79:2265-2285, 2010. MR 2684364
  • 31. Yaron Lipman and David Levin.
    Approximating piecewise-smooth functions.
    IMA J. Numer. Anal. 30(4):1159-1193, 2010. MR 2727820
  • 32. Y.I. Lyubich.
    The Sylvester-Ramanujan system of equations and the complex power moment problem.
    The Ramanujan Journal, 8(1):23-45, 2004. MR 2068428 (2005e:30068)
  • 33. H.N. Mhaskar and J. Prestin.
    Polynomial frames for the detection of singularities.
    In Wavelet Analysis and Multiresolution Methods: Proceedings of the Conference Held at University of Illinois at Urbana-Champaign, Illinois, page 273. CRC, 2000. MR 1777997 (2001k:65212)
  • 34. I.P. Natanson.
    Constructive Function Theory (in Russian).
    Gostekhizdat, 1949.
  • 35. L. Plaskota and G.W. Wasilkowski.
    The power of adaptive algorithms for functions with singularities.
    Journal of Fixed Point Theory and Applications, 6(2):227-248, 2009. MR 2580977 (2011b:65269)
  • 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.
    Mathematical Reports of the Academy of Science of the Royal Society of Canada, 29(4):97-114, 2008. MR 2426609 (2009h:62029)
  • 38. B.D. Shizgal and J.H. Jung.
    Towards the resolution of the Gibbs phenomena.
    Journal of Computational and Applied Mathematics, 161(1):41-65, 2003. MR 2018574 (2004k:42042)
  • 39. A. Solomonoff.
    Reconstruction of a discontinuous function from a few Fourier coefficients using Bayesian estimation.
    Journal of Scientific Computing, 10(1):29-80, 1995. MR 1337448 (96b:65013)
  • 40. G. Szegő.
    Orthogonal Polynomials.
    Colloq. Publ. Vol. 23, American Mathematical Society, 1975. MR 0372517 (51:8724)
  • 41. E. Tadmor.
    Filters, mollifiers and the computation of the Gibbs phenomenon.
    Acta Numerica, 16:305-378, 2007. MR 2417931 (2009c:65033)
  • 42. M. Vetterli, P. Marziliano, and T. Blu.
    Sampling signals with finite rate of innovation.
    IEEE Transactions on Signal Processing, 50(6):1417-1428, 2002. MR 1930786 (2003i:94019)
  • 43. J. Vindas.
    Local Behavior of Distributions and Applications.
    PhD thesis, 2009.
  • 44. M. Wei, A.G. Martínez, and A.R. De Pierro.
    Detection of edges from spectral data: New results.
    Applied and Computational Harmonic Analysis, 22(3):386-393, 2007. MR 2311863 (2008j:42002)
  • 45. J.H. Wilkinson.
    Rounding errors in algebraic processes.
    Dover Publ, 1994. MR 1280465
  • 46. A. Zygmund.
    Trigonometric Series. Vols. I, II.
    Cambridge University Press, New York, 1959. MR 0236587 (38:4882)

Similar Articles

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

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

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.

American Mathematical Society