Piecewise-smooth inverse problems

  • [PDF] [DOI] D. Batenkov, O. Friedland, and Y. Yomdin, “Sampling, Metric Entropy and Dimensionality Reduction,” SIAM J.Math.Anal., vol. 47, iss. 1, pp. 786-796, 2015.
    [Bibtex]
    @Article{batenkov_sampling_2013,
    author = {Batenkov, D. and Friedland, O. and Yomdin, Y.},
    title = {{Sampling, Metric Entropy and Dimensionality Reduction}},
    journal = {{SIAM J.Math.Anal.}},
    year = {2015},
    volume = {47},
    number = {1},
    pages = {786--796},
    abstract = {Let $Q$ be a relatively compact subset in a Hilbert space $V$. For a given $\epsilon>0$ let $N(\epsilon,Q)$ be the minimal number of linear measurements, sufficient to reconstruct any $x \in Q$ with the accuracy $\epsilon$. We call $N(\epsilon,Q)$ the sampling $\epsilon$-entropy of $Q$. Using dimensionality reduction, as provided by the Johnson-Lindenstrauss lemma, we show that, in an appropriate probabilistic setting, $N(\epsilon,Q)$ is bounded from above by Kolmogorov's $\epsilon$-entropy $H(\epsilon,Q)$, defined as $H(\epsilon,Q) = \log M(\epsilon,Q)$, with $M(\epsilon,Q)$ being the minimal number of $\epsilon$-balls covering $Q$. As the main application, we show that piecewise smooth (piecewise analytic) functions in one and several variables can be sampled with essentially the same accuracy rate as their regular counterparts. For univariate piecewise $C^k$-smooth functions this result, which settles the so-called Eckhoff conjecture, was recently established in [4] via a deterministic ``algebraic reconstruction'' algorithm.},
    bdsk-url-1 = {http://arxiv.org/abs/1308.2781},
    date-modified = {2016-02-01 14:24:36 +0000},
    doi = {10.1137/130944436},
    file = {arXiv.org Snapshot:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/PP4XKBI4/1308.html:text/html;Batenkov et al_2013_Sampling, Metric Entropy and Dimensionality Reduction.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/V7HBCR9S/Batenkov et al_2013_Sampling, Metric Entropy and Dimensionality Reduction.pdf:application/pdf},
    keywords = {{65T40}, {65D15}, Mathematics - Classical Analysis and {ODEs}},
    owner = {dima},
    timestamp = {2014.02.26},
    url = {http://epubs.siam.org/doi/abs/10.1137/130944436},
    urldate = {2014-02-26}
    }
  • [PDF] [DOI] D. Batenkov, “Complete Algebraic Reconstruction of Piecewise-Smooth Functions from Fourier Data,” Mathematics of Computation, vol. 84, iss. 295, pp. 2329-2350, 2015.
    [Bibtex]
    @Article{batenkov_complete,
    author = {Batenkov, D.},
    title = {{Complete Algebraic Reconstruction of Piecewise-Smooth Functions from Fourier Data}},
    journal = {{Mathematics of Computation}},
    year = {2015},
    volume = {84},
    number = {295},
    pages = {2329--2350},
    abstract = {In this paper we provide a reconstruction algorithm for piecewise-smooth
    functions with a-priori known smoothness and number of discontinuities,
    from their Fourier coefficients, posessing 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.},
    bdsk-url-1 = {http://www.ams.org/mcom/0000-000-00/S0025-5718-2015-02948-2/},
    bdsk-url-2 = {http://dx.doi.org/10.1090/S0025-5718-2015-02948-2},
    date-modified = {2016-02-01 13:07:11 +0000},
    doi = {10.1090/S0025-5718-2015-02948-2},
    file = {Batenkov_Complete Algebraic Reconstruction of Piecewise-Smooth Functions from Fourier.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/R93HPHEK/Batenkov_Complete Algebraic Reconstruction of Piecewise-Smooth Functions from Fourier.pdf:application/pdf},
    keywords = {zrread},
    owner = {dima},
    timestamp = {2014.08.20},
    url = {http://www.ams.org/mcom/0000-000-00/S0025-5718-2015-02948-2/}
    }
  • [PDF] [DOI] D. Batenkov and Y. Yomdin, “Local and Global Geometry of Prony Systems and Fourier Reconstruction of Piecewise-Smooth Functions,” in Operator-Related Function Theory and Time-Frequency Analysis, Springer, 2015, pp. 57-76.
    [Bibtex]
    @InCollection{batenkov_local_2015,
    author = {Batenkov, D. and Yomdin, Y.},
    title = {{Local and Global Geometry of Prony Systems and Fourier Reconstruction of Piecewise-Smooth Functions}},
    booktitle = {{Operator-Related Function Theory and Time-Frequency Analysis}},
    publisher = {Springer},
    year = {2015},
    pages = {57--76},
    abstract = {Many reconstruction problems in signal processing require solution
    of a certain kind of nonlinear systems of algebraic equations, which
    we call Prony systems. We study these systems from a general perspective,
    addressing questions of global solvability and stable inversion. Of
    special interest are the so-called ``near-singular'' situations,
    such as a collision of two closely spaced nodes.
    We also discuss the problem of reconstructing piecewise-smooth functions
    from their Fourier coefficients, which is easily reduced by a well-known
    method of K.Eckhoff to solving a particular Prony system. As we show
    in the paper, it turns out that a modification of this highly nonlinear
    method can reconstruct the jump locations and magnitudes of such functions,
    as well as the pointwise values between the jumps, with the maximal
    possible accuracy. },
    bdsk-url-1 = {http://link.springer.com/chapter/10.1007/978-3-319-08557-9_2},
    date-modified = {2016-02-01 13:08:38 +0000},
    doi = {10.1007/978-3-319-08557-9_2},
    file = {Batenkov_Yomdin_2013_Local and global geometry of Prony systems and Fourier reconstruction of.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/56HEPPH7/Batenkov_Yomdin_2013_Local and global geometry of Prony systems and Fourier reconstruction of.pdf:application/pdf;Snapshot:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/WPVSWPC3/978-3-319-08557-9_2.html:text/html},
    owner = {dima},
    timestamp = {2014.12.15},
    url = {http://link.springer.com/chapter/10.1007/978-3-319-08557-9_2},
    urldate = {2014-11-29}
    }
  • [PDF] D. Batenkov, N. Sarig, and Y. Yomdin, “Accuracy of Algebraic Fourier Reconstruction for Shifts of Several Signals,” Sampling Theory in Signal and Image Processing, vol. 13, iss. 2, pp. 151-173, 2014.
    [Bibtex]
    @Article{batenkov_accuracy_2014,
    author = {Batenkov, Dmitry and Sarig, Niv and Yomdin, Yosef},
    title = {{Accuracy of Algebraic Fourier Reconstruction for Shifts of Several Signals}},
    journal = {{Sampling Theory in Signal and Image Processing}},
    year = {2014},
    volume = {13},
    number = {2},
    pages = {151--173},
    abstract = {We consider the problem of ``algebraic reconstruction'' of linear combinations of shifts of several known signals
    $f_1,\ldots,f_k$ from the Fourier samples. Following [5], for each $j=1,\ldots,k$ we choose sampling set
    $S_j$ to be a subset of the common set of zeroes of the Fourier transforms ${\cal F}(f_\ell), \ \ell \ne j$, on which
    ${\cal F}(f_j)\ne 0$. It was shown in [5] that in this way the reconstruction system is ``decoupled'' into $k$
    separate systems, each including only one of the signals $f_j$. Each of the resulting systems is of a ``generalized Prony'' form.
    However, the sampling sets as above usually are non-uniform. Moreover, they may be ``too small'' to allow for a unique
    reconstruction of the shifts and amplitudes. In the present paper we study uniqueness and robustness of non-uniform sampling of
    exponential polynomials, applying as the main tool a well-known result in Harmonic Analysis: the Tur\'an-Nazarov inequality
    ([16]), and its generalization to discrete sets, obtained in [11]. The results obtained are applied to our
    specific reconstruction problem of linear combinations of shifts of several signals, producing explicit accuracy estimates.
    We illustrate our general results in some specific examples, and provide some simulation results, which basically confirm
    our theoretical predictions.},
    bdsk-url-1 = {http://stsip.org/pdf/vol13/vol13no2pp151-173.pdf},
    date-modified = {2016-02-01 14:16:06 +0000},
    file = {arXiv.org Snapshot:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/TV4PJS45/1311.html:text/html;Batenkov et al_2013_Accuracy of Algebraic Fourier Reconstruction for Shifts of Several Signals.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/U94DQS48/Batenkov et al_2013_Accuracy of Algebraic Fourier Reconstruction for Shifts of Several Signals.pdf:application/pdf},
    keywords = {94A20, 65T40, Mathematics - Classical Analysis and {ODEs}},
    owner = {dima},
    timestamp = {2015.01.06},
    url = {http://stsip.org/pdf/vol13/vol13no2pp151-173.pdf},
    urldate = {2014-02-26}
    }
  • [PDF] Y. Yomdin, D. Batenkov, and N. Sarig, “Decoupling of Fourier Reconstruction System for Shifts of Several Signals,” in 10th international conference on Sampling Theory and Applications (SampTA 2013), Bremen, Germany, 2013, pp. 580-583.
    [Bibtex]
    @InProceedings{sampta13niv,
    author = {Yosef Yomdin and Dmitry Batenkov and Niv Sarig},
    title = {{Decoupling of Fourier Reconstruction System for Shifts of Several Signals}},
    booktitle = {{10th international conference on Sampling Theory and Applications (SampTA 2013)}},
    year = {2013},
    pages = {580-583},
    address = {Bremen, Germany},
    month = jul,
    abstract = {We consider the problem of ``algebraic reconstruction'' of linear
    combinations of shifts of several signals $f\_1,\ldots,f\_k$ from the
    Fourier samples. For each $r=1,\ldots,k$ we choose sampling set $S\_r$ to
    be a subset of the common set of zeroes of the Fourier transforms ${\cal
    F}(f\_\l), \ \l \ne r$, on which ${\cal F}(f\_r)\ne 0$. We show that in
    this way the reconstruction system is reduced to $k$ separate systems, each
    including only one of the signals $f\_r$. Each of the resulting systems is
    of a ``generalized Prony'' form. We discuss the problem of unique
    solvability of such systems, and provide some examples.},
    days = {1},
    keywords = {Shifts of signals; Fourier samples; Prony system, decoupling, non-uniform sampling},
    owner = {dima},
    timestamp = {2016.08.04}
    }
  • [PDF] D. Batenkov and Y. Yomdin, “Algebraic signal sampling, Gibbs phenomenon and Prony-type systems,” in 10th international conference on Sampling Theory and Applications (SampTA 2013), Bremen, Germany, 2013, pp. 137-140.
    [Bibtex]
    @InProceedings{sampta13_bat,
    author = {Dmitry Batenkov and Yosef Yomdin},
    title = {{Algebraic signal sampling, Gibbs phenomenon and Prony-type systems}},
    booktitle = {{10th international conference on Sampling Theory and Applications (SampTA 2013)}},
    year = {2013},
    pages = {137-140},
    address = {Bremen, Germany},
    month = jul,
    abstract = {Systems of Prony type appear in various reconstruction problems such as
    finite rate of innovation, superresolution and Fourier inversion of
    piecewise smooth functions. By keeping the number of equations small and
    fixed, we demonstrate that such {"}decimation{"} can lead to practical
    improvements in the reconstruction accuracy. As an application, we provide
    a solution to the so-called Eckhoff's conjecture, which asked for
    reconstructing jump positions and magnitudes of a piecewise-smooth function
    from its Fourier coefficients with maximal possible asymptotic accuracy --
    thus eliminating the Gibbs phenomenon.},
    days = {1},
    keywords = {Algebraic sampling; Gibbs phenomenon; superresolution; Prony system},
    owner = {dima},
    timestamp = {2016.08.04}
    }
  • [PDF] [DOI] D. Batenkov, V. Golubyatnikov, and Y. Yomdin, “Reconstruction of Planar Domains from Partial Integral Measurements,” Contemporary Mathematics, vol. 591, pp. 51-66, 2013.
    [Bibtex]
    @Article{planar_domains,
    author = {Batenkov, D. and Golubyatnikov, V. and Yomdin, Y.},
    title = {{Reconstruction of Planar Domains from Partial Integral Measurements}},
    journal = {{Contemporary Mathematics}},
    year = {2013},
    volume = {591},
    pages = {51-66},
    abstract = {We consider the problem of reconstruction of planar domains from their moments. Specifically, we consider domains with boundary which can be represented by a union of a finite number of pieces whose graphs are solutions of a linear differential equation with polynomial coefficients. This includes do- mains with piecewise-algebraic and, in particular, piecewise-polynomial bound- aries. Our approach is based on the one-dimensional reconstruction method of [5] and a kind of ``separation of variables'' which reduces the planar problem to two one-dimensional problems, one of them parametric. Several explicit examples of reconstruction are given.
    Another main topic of the paper concerns ``invisible sets'' for various types of incomplete moment measurements. We suggest a certain point of view which stresses remarkable similarity between several apparently unrelated problems. In particular, we discuss zero quadrature domains (invisible for harmonic poly- nomials), invisibility for powers of a given polynomial, and invisibility for com- plex moments (Wermer's theorem and further developments). The common property we would like to stress is a ``rigidity'' and symmetry of the invisible ob jects.},
    date-modified = {2016-02-01 14:23:37 +0000},
    doi = {10.1090/conm/591/11826},
    owner = {dmitryb},
    timestamp = {2012.03.11}
    }
  • [PDF] [DOI] D. Batenkov and Y. Yomdin, “Algebraic Fourier reconstruction of piecewise smooth functions,” Mathematics of Computation, vol. 81, pp. 277-318, 2012.
    [Bibtex]
    @Article{batyom_alg_fourier,
    author = {Batenkov, D. and Yomdin, Y.},
    title = {{Algebraic Fourier reconstruction of piecewise smooth functions}},
    journal = {{Mathematics of Computation}},
    year = {2012},
    volume = {81},
    pages = {277--318},
    abstract = {Accurate reconstruction of piecewise-smooth functions from a finite
    number of Fourier coefficients is an important problem in various
    applications. This probelm exhibits an inherent inaccuracy, in particular
    the Gibbs phenomenon, and it is being intensively investigated during
    the last 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.},
    adsnote = {Provided by the SAO/NASA Astrophysics Data System},
    adsurl = {http://adsabs.harvard.edu/abs/2010arXiv1005.1884B},
    archiveprefix = {arXiv},
    bdsk-url-1 = {http://dx.doi.org/10.1090/S0025-5718-2011-02539-1},
    date-modified = {2016-02-01 13:05:00 +0000},
    doi = {10.1090/S0025-5718-2011-02539-1},
    eprint = {1005.1884},
    keywords = {Mathematics - Classical Analysis and ODEs, 65T40 (Primary), 65D15 (Secondary)},
    owner = {Dima},
    timestamp = {2010.12.10},
    url = {http://dx.doi.org/10.1090/S0025-5718-2011-02539-1}
    }
  • [PDF] D. Batenkov, N. Sarig, and Y. Yomdin, “An “algebraic" reconstruction of piecewise-smooth functions from integral measurements,” Functional Differential Equations, vol. 19, iss. 1-2, pp. 13-30, 2012.
    [Bibtex]
    @Article{batenkov_fde,
    author = {Batenkov, D. and Sarig, N. and Yomdin, Y.},
    title = {{An ``algebraic" reconstruction of piecewise-smooth functions from integral measurements}},
    journal = {{Functional Differential Equations}},
    year = {2012},
    volume = {19},
    number = {1-2},
    pages = {13--30},
    abstract = {This paper presents some results on a well-known problem in Algebraic Signal Sampling and in other areas of applied mathematics: reconstruction of piecewise-smooth functions from their integral measurements (like moments, Fourier coefficients, Radon transform, etc.). Our results concern reconstruction (from the moments or Fourier coefficients) of signals in two specific classes: linear combinations of shifts of a given function, and "piecewise D-finite functions" which satisfy on each continuity interval a linear differential equation with polynomial coefficients. In each case the problem is reduced to a solution of a certain type of non-linear algebraic system of equations ("Prony-type system"). We recall some known methods for explicitly solving such systems in one variable, and provide extensions to some multi-dimensional cases. Finally, we investigate the local stability of solving the Prony-type systems.},
    date-modified = {2016-02-01 13:05:29 +0000},
    owner = {dmitryb},
    timestamp = {2012.03.11}
    }
  • [PDF] [DOI] D. Batenkov, “Moment inversion problem for piecewise D-finite functions,” Inverse Problems, vol. 25, iss. 10, p. 105001, 2009.
    [Bibtex]
    @Article{bat2008,
    author = {D. Batenkov},
    title = {{Moment inversion problem for piecewise D-finite functions}},
    journal = {{Inverse Problems}},
    year = {2009},
    volume = {25},
    number = {10},
    pages = {105001},
    month = {October},
    abstract = {We consider the problem of exact reconstruction of univariate functions with jump discontinuities at unknown positions from their moments. These functions are assumed to satisfy an \emph{a priori unknown} linear homogeneous differential equation with polynomial coefficients on each continuity interval. Therefore, they may be specified by a finite amount of information. This reconstruction problem has practical importance in Signal Processing and other applications.
    It is somewhat of a ``folklore'' that the sequence of the moments of such ``piecewise $D$-finite''functions satisfies a linear recurrence relation of bounded order and degree. We derive this recurrence relation explicitly. It turns out that the coefficients of the differential operator which annihilates every piece of the function, as well as the locations of the discontinuities, appear in this recurrence in a precisely controlled manner. This leads to the formulation of a generic algorithm for reconstructing a piecewise $D$-finite function from its moments.
    We investigate the conditions for solvability of the resulting linear systems in the general case, as well as analyze a few particular examples. We provide results of numerical simulations for several types of signals, which test the sensitivity of the proposed algorithm to noise.},
    bdsk-url-1 = {http://iopscience.iop.org/0266-5611/25/10/105001/},
    bdsk-url-2 = {http://dx.doi.org/10.1088/0266-5611/25/10/105001},
    date-modified = {2016-02-01 13:09:02 +0000},
    doi = {10.1088/0266-5611/25/10/105001},
    owner = {Dima},
    timestamp = {2010.12.10},
    url = {http://iopscience.iop.org/0266-5611/25/10/105001/}
    }
  • [PDF] D. Batenkov, N. Sarig, and Y. Yomdin, “An “algebraic” reconstruction of piecewise-smooth functions from integral measurements,” in Proc. of Sampling Theory and Applications (SAMPTA), 2009.
    [Bibtex]
    @InProceedings{batenkov2009arp,
    author = {D. Batenkov and N. Sarig and Y. Yomdin},
    title = {{An ``algebraic'' reconstruction of piecewise-smooth functions from integral measurements}},
    booktitle = {{Proc. of Sampling Theory and Applications (SAMPTA)}},
    year = {2009},
    abstract = {This paper presents some results on a well-known problem in Algebraic Signal Sampling and in other areas of applied mathematics: reconstruction of piecewise-smooth functions from their integral measurements (like moments, Fourier coef cients, Radon transform, etc.). Our results concern reconstruction (from the moments) of signals in two special classes: linear combinations of shifts of a given function, and ``piecewise $D$-finite functions'' which satisfy on each continuity interval a linear differential equation with polynomial coefficients.},
    comment = {Arxiv preprint arXiv:0901.4659},
    date-modified = {2016-02-01 14:41:26 +0000},
    owner = {dima},
    timestamp = {2013.04.15},
    url = {https://hal.archives-ouvertes.fr/hal-00452200}
    }