Publications

2016

  • [PDF] D. Batenkov, “Accurate solution of near-colliding Prony systems via decimation and homotopy continuation,” To appear in Theoretical Computer Science, 2016.
    [Bibtex]
    @Article{batenkov_accurate_2014,
    author = {Batenkov, Dmitry},
    title = {{Accurate solution of near-colliding Prony systems via decimation and homotopy continuation}},
    journal = {{To appear in Theoretical Computer Science}},
    year = {2016},
    note = {{arXiv}: 1501.00160},
    abstract = {We consider polynomial systems of Prony type, appearing in many areas of mathematics. Their robust numerical solution is considered to be difficult, especially in "near-colliding" situations. We transform the nonlinear part of the Prony system into a Hankel-type polynomial system. Combining this representation with a recently discovered "decimation" technique, we present an algorithm which applies homotopy continuation to an appropriately chosen Hankel-type system as above. In this way, we are able to solve for the nonlinear variables of the original system with high accuracy when the data is perturbed.},
    bdsk-url-1 = {http://arxiv.org/abs/1501.00160},
    file = {arXiv.org Snapshot:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/9HII27BE/1501.html:text/html;Batenkov_2014_Accurate solution of near-colliding Prony systems via decimation and homotopy.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/HVQS339M/Batenkov_2014_Accurate solution of near-colliding Prony systems via decimation and homotopy.pdf:application/pdf},
    keywords = {Computer Science - Numerical Analysis, Computer Science - Symbolic Computation, Mathematics - Numerical Analysis},
    owner = {dima},
    timestamp = {2015.01.06},
    url = {http://arxiv.org/abs/1501.00160},
    urldate = {2015-01-06}
    }
  • [PDF] [DOI] D. Batenkov, “Stability and super-resolution of generalized spike recovery,” Applied and Computational Harmonic Analysis, 2016.
    [Bibtex]
    @Article{batenkov_stability_2016,
    author = {Batenkov, Dmitry},
    title = {Stability and super-resolution of generalized spike recovery},
    journal = {{Applied and Computational Harmonic Analysis}},
    year = {2016},
    abstract = {We consider the problem of recovering a linear combination of Dirac delta functions and derivatives from a finite number of Fourier samples corrupted by noise. This is a generalized version of the well-known spike recovery problem, which is receiving much attention recently. We analyze the numerical conditioning of this problem in two different settings depending on the order of magnitude of the quantity N$\eta$, where N is the number of Fourier samples and $\eta$ is the minimal distance between the generalized spikes. In the {\textquotedblleft}well-conditioned{\textquotedblright} regime N $\eta$ >> 1 , we provide upper bounds for first-order perturbation of the solution to the corresponding least-squares problem. In the near-colliding, or {\textquotedblleft}super-resolution{\textquotedblright} regime N $\eta$ {\textrightarrow} 0 with a single cluster, we propose a natural regularization scheme based on decimating the samples {\textendash} essentially increasing the separation $\eta$ {\textendash} and demonstrate the effectiveness and near-optimality of this scheme in practice.},
    doi = {10.1016/j.acha.2016.09.004},
    file = {Batenkov_Stability and super-resolution of generalized spike recovery.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/XRPW6WJS/Batenkov_Stability and super-resolution of generalized spike recovery.pdf:application/pdf;ScienceDirect Snapshot:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/XS5672W4/S1063520316300641.html:text/html},
    issn = {1063-5203},
    keywords = {decimation, Numerical conditioning, Prony system, Spike recovery, super-resolution},
    owner = {dima},
    timestamp = {2016.10.21},
    url = {http://www.sciencedirect.com/science/article/pii/S1063520316300641},
    urldate = {2016-10-21}
    }
  • [PDF] [DOI] D. Batenkov and Y. Yomdin, “Taylor domination, TurĂ¡n lemma, and PoincarĂ©-Perron sequences,” in Contemporary Mathematics, B. Mordukhovich, S. Reich, and A. Zaslavski, Eds., Providence, Rhode Island: American Mathematical Society, 2016, vol. 659, pp. 1-15.
    [Bibtex]
    @InCollection{mordukhovich_taylor_2016,
    author = {Batenkov, Dmitry and Yomdin, Yosef},
    title = {Taylor domination, {Tur{\'a}n} lemma, and {Poincar{\'e}}-{Perron} sequences},
    booktitle = {Contemporary {Mathematics}},
    publisher = {American Mathematical Society},
    year = {2016},
    editor = {Mordukhovich, Boris and Reich, Simeon and Zaslavski, Alexander},
    volume = {659},
    pages = {1--15},
    address = {Providence, Rhode Island},
    doi = {10.1090/conm/659/13162},
    file = {Batenkov_Yomdin_Taylor Domination, Tur{\'a}n lemma, and Poincar{\'e}-Perron Sequences.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/Z7WU5V63/Batenkov_Yomdin_Taylor Domination, Tura?n lemma, and Poincare?-Perron Sequences.pdf:application/pdf},
    isbn = {978-1-4704-1736-9 978-1-4704-2904-1},
    language = {en},
    owner = {dima},
    timestamp = {2016.08.04},
    url = {http://dx.doi.org/10.1090/conm/659/13162},
    urldate = {2016-04-07}
    }

2015

  • [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 G. Binyamini, “Uniform upper bounds for the cyclicity of the zero solution of the Abel differential equation,” Journal of Differential Equations, vol. 259, iss. 11, pp. 5769-5781, 2015.
    [Bibtex]
    @Article{batenkov_uniform_2015,
    author = {Batenkov, Dmitry and Binyamini, Gal},
    title = {Uniform upper bounds for the cyclicity of the zero solution of the {Abel} differential equation},
    journal = {{Journal of Differential Equations}},
    year = {2015},
    volume = {259},
    number = {11},
    pages = {5769--5781},
    doi = {10.1016/j.jde.2015.07.009},
    file = {Batenkov_Binyamini_2015_Uniform upper bounds for the cyclicity of the zero solution of the Abel.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/9M8HT664/Batenkov_Binyamini_2015_Uniform upper bounds for the cyclicity of the zero solution of the Abel.pdf:application/pdf},
    issn = {0022-0396},
    mrnumber = {3397308},
    owner = {dima},
    timestamp = {2016.08.04},
    url = {http://www.ams.org/mathscinet-getitem?mr=3397308},
    urldate = {2016-08-04}
    }
  • [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 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] [DOI] A. Akinshin, D. Batenkov, and Y. Yomdin, “Accuracy of spike-train Fourier reconstruction for colliding nodes,” in 2015 International Conference on Sampling Theory and Applications (SampTA), 2015, pp. 617-621.
    [Bibtex]
    @InProceedings{akinshin_accuracy_2015,
    author = {Akinshin, Andrey and Batenkov, Dmitry and Yomdin, Yosef},
    title = {{Accuracy of spike-train {Fourier} reconstruction for colliding nodes}},
    booktitle = {2015 {International} {Conference} on {Sampling} {Theory} and {Applications} ({SampTA})},
    year = {2015},
    pages = {617--621},
    month = may,
    abstract = {We consider signal reconstruction problem for signals $F$ of the form $ F(x)=\left(x\right)=\sum_{j=1}^{d}a_{j}\delta\left(x-x_{j}\right),$
    from their Fourier transform ${\cal F}(F)(s)=\int_{-\infty}^\infty F(x)e^{-isx}dx.$ We assume ${\cal F}(F)(s)$ to be
    known for each $s\in [-N,N],$ with an absolute error not exceeding $\epsilon > 0$. We give an {\it absolute lower bound}
    (which is valid with any reconstruction method) for the ``worst case'' error of reconstruction of $F$ from ${\cal F}(F),$
    in situations where the nodes $x_j$ are known to form an $l$ elements cluster of a size $h \ll 1$. Using ``decimation''
    algorithm of [6,7] we provide an upper bound for the reconstruction error,
    essentially of the same form as the lower one. Roughly, our main result states that for $h$ of order $\frac{1}{N}\epsilon ^{\frac{1}{2l-1}}$
    the worst case reconstruction error of the cluster nodes is of the same order $\frac{1}{N}\epsilon^{\frac{1}{2l-1}}$, and hence the inside
    configuration of the cluster nodes (in the worst case scenario) cannot be reconstructed at all. On the other hand, decimation
    algorithm reconstructs $F$ with the accuracy of order $\frac{1}{N}\epsilon^{\frac{1}{2l}}$.},
    bdsk-url-1 = {http://dx.doi.org/10.1109/SAMPTA.2015.7148965},
    date-modified = {2016-02-01 14:21:24 +0000},
    doi = {10.1109/SAMPTA.2015.7148965},
    file = {Akinshin et al_2015_Accuracy of spike-train Fourier reconstruction for colliding nodes.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/9EXEPW7X/Akinshin et al_2015_Accuracy of spike-train Fourier reconstruction for colliding nodes.pdf:application/pdf;IEEE Xplore Abstract Record:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/N9GSC2ZE/articleDetails.html:text/html},
    keywords = {Accuracy, Fourier transforms, Geometry, image resolution, Jacobian matrices, Reconstruction algorithms, Signal resolution},
    owner = {dima},
    timestamp = {2015.07.29}
    }

2014

  • [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] [DOI] D. Batenkov and Y. Yomdin, “Geometry and Singularities of the Prony mapping,” Journal of Singularities, vol. 10, pp. 1-25, 2014.
    [Bibtex]
    @Article{batenkov_geometry_2014,
    author = {Batenkov, Dmitry and Yomdin, Yosef},
    title = {{Geometry and Singularities of the Prony mapping}},
    journal = {{Journal of Singularities}},
    year = {2014},
    volume = {10},
    pages = {1--25},
    abstract = {Prony mapping provides the global solution of the Prony system of
    equations
    \[
    \Sigma_{i=1}^{n}A_{i}x_{i}^{k}=m_{k},\ k=0,1,\dots,2n-1.
    \]
    This system appears in numerous theoretical and applied problems arising
    in Signal Reconstruction. The simplest example is the problem of reconstruction
    of linear combination of $\delta$-functions of the form $g(x)=\sum_{i=1}^{n}a_{i}\delta(x-x_{i})$,
    with the unknown parameters $a_{i},\ x_{i},\ i=1,\dots,n,$ from the
    ``moment measurements'' $m_{k}=\int x^{k}g(x)dx.$
    Global solution of the Prony system, i.e. inversion of the Prony mapping,
    encounters several types of singularities. One of the most important
    ones is a collision of some of the points $x_{i}.$ The investigation
    of this type of singularities has been started in [21]
    where the role of finite differences was demonstrated.
    In the present paper we study this and other types of singularities
    of the Prony mapping, and describe its global geometry. We show, in
    particular, close connections of the Prony mapping with the ``Vieta
    mapping'' expressing the coefficients of a polynomial through its
    roots, and with hyperbolic polynomials and ``Vandermonde mapping''
    studied by V. Arnold.},
    bdsk-url-1 = {http://www.journalofsing.org/volume10/article1.html},
    bdsk-url-2 = {http://dx.doi.org/10.5427/jsing.2014.10a},
    date-modified = {2016-02-01 13:33:10 +0000},
    doi = {10.5427/jsing.2014.10a},
    file = {Batenkov_Yomdin_2014_Geometry and Singularities of the Prony mapping.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/UTEDMNA2/Batenkov_Yomdin_2014_Geometry and Singularities of the Prony mapping.pdf:application/pdf;Journal of Singularities | Volume 10:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/QRBWTHZD/article1.html:text/html},
    issn = {19492006},
    owner = {dima},
    timestamp = {2014.12.25},
    url = {http://www.journalofsing.org/volume10/article1.html},
    urldate = {2014-12-25}
    }
  • [PDF] D. Batenkov and Y. Yomdin, “Taylor Domination, Difference Equations, and Bautin Ideals,” To appear in Springer Proceedings in Mathematics and Statistics, 2014.
    [Bibtex]
    @Article{batenkov_taylor_2014,
    author = {Batenkov, Dmitry and Yomdin, Yosef},
    title = {{Taylor Domination, Difference Equations, and Bautin Ideals}},
    journal = {{To appear in Springer Proceedings in Mathematics and Statistics}},
    year = {2014},
    month = nov,
    note = {{arXiv}: 1411.7629},
    abstract = {We compare three approaches to studying the behavior of an analytic function $f(z)=\sum_{k=0}^\infty a_kz^k$
    from its Taylor coefficients. The first is ``Taylor domination'' property for $f(z)$ in the complex disk $D_R$, which is an
    inequality of the form
    \[
    |a_{k}|R^{k}\leq C\ \max_{i=0,\dots,N}\ |a_{i}|R^{i}, \ k \geq N+1.
    \]
    The second approach is based on a possibility to generate $a_k$ via recurrence relations. Specifically, we consider linear
    non-stationary recurrences of the form
    \[
    a_{k}=\sum_{j=1}^{d}c_{j}(k)\cdot a_{k-j},\ \ k=d,d+1,\dots,
    \]
    with uniformly bounded coefficients.
    In the third approach we assume that $a_k=a_k(\lambda)$ are polynomials in a
    finite-dimensional parameter $\lambda \in C^n.$ We study ``Bautin ideals'' $I_k$ generated by
    $a_{1}(\lambda),\ldots,a_{k}(\lambda)$ in the ring $C[\lambda]$ of polynomials in $\lambda$.
    \smallskip
    These three approaches turn out to be closely related. We present some results and questions in this direction.},
    annote = {Comment: {arXiv} admin note: substantial text overlap with {arXiv}:1301.6033},
    bdsk-url-1 = {http://arxiv.org/abs/1411.7629},
    date-modified = {2016-02-01 13:47:18 +0000},
    file = {arXiv.org Snapshot:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/P6BPTZMN/1411.html:text/html;Batenkov_Yomdin_2014_Taylor Domination, Difference Equations, and Bautin Ideals.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/8K4JMTJQ/Batenkov_Yomdin_2014_Taylor Domination, Difference Equations, and Bautin Ideals.pdf:application/pdf},
    keywords = {30B10, 39A06, Mathematics - Classical Analysis and {ODEs}},
    owner = {dima},
    timestamp = {2014.12.15},
    url = {http://arxiv.org/abs/1411.7629},
    urldate = {2014-12-15}
    }
  • [PDF] [DOI] D. Batenkov, “Prony Systems via Decimation and Homotopy Continuation,” in Proceedings of the 2014 Symposium on Symbolic-Numeric Computation, New York, {NY}, {USA}, 2014, p. 59{\textendash}60.
    [Bibtex]
    @InProceedings{bat2014snc,
    author = {Batenkov, Dmitry},
    title = {{Prony Systems via Decimation and Homotopy Continuation}},
    booktitle = {{Proceedings of the 2014 Symposium on Symbolic-Numeric Computation}},
    year = {2014},
    series = {{SNC} '14},
    pages = {59{\textendash}60},
    address = {New York, {NY}, {USA}},
    publisher = {{ACM}},
    abstract = {We consider polynomial systems of Prony type, appearing in many areas of mathematics. Their robust numerical solution is considered to be difficult, especially in "near-colliding" situations. We transform the nonlinear part of the Prony system into a Hankel-type polynomial system. Combining this representation with a recently discovered "decimation" technique, we present an algorithm which applies homotopy continuation on a sequence of modified Hankel-type systems as above. In this way, we are able to solve for the nonlinear variables of the original system with high accuracy when the data is perturbed.},
    bdsk-url-1 = {http://doi.acm.org/10.1145/2631948.2631961},
    bdsk-url-2 = {http://dx.doi.org/10.1145/2631948.2631961},
    doi = {10.1145/2631948.2631961},
    file = {Batenkov_2014_Prony Systems via Decimation and Homotopy Continuation.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/JKCJ8WHH/Batenkov_2014_Prony Systems via Decimation and Homotopy Continuation.pdf:application/pdf},
    isbn = {978-1-4503-2963-7},
    keywords = {decimation, Prony systems},
    owner = {dima},
    timestamp = {2014.08.21},
    url = {http://doi.acm.org/10.1145/2631948.2631961},
    urldate = {2014-08-13}
    }

2013

  • [PDF] D. Batenkov and G. Binyamini, “Moment vanishing of piecewise solutions of linear ODEs,” To appear in Springer Proceedings in Mathematics & Statistics, 2013.
    [Bibtex]
    @Article{batenkov2013moment,
    author = {Batenkov, Dmitry and Binyamini, Gal},
    title = {{Moment vanishing of piecewise solutions of linear ODEs}},
    journal = {{To appear in Springer Proceedings in Mathematics \& Statistics}},
    year = {2013},
    abstract = {We consider the "moment vanishing problem" for a general class of piecewise-analytic functions which satisfy on each continuity interval a linear ODE with polynomial coefficients. This problem, which essentially asks how many zero first moments can such a (nonzero) function have, turns out to be related to several difficult questions in analytic theory of ODEs (Poincare's Center-Focus problem) as well as in Approximation Theory and Signal Processing ("Algebraic Sampling"). While the solution space of any particular ODE admits such a bound, it will in the most general situation depend on the coefficients of this ODE. We believe that a good understanding of this dependence may provide a clue for attacking the problems mentioned above.
    In this paper we undertake an approach to the moment vanishing problem which utilizes the fact that the moment sequences under consideration satisfy a recurrence relation of fixed length, whose coefficients are polynomials in the index. For any given operator, we prove a general bound for its moment vanishing index. We also provide uniform bounds for several operator families.},
    date-modified = {2016-02-01 12:48:18 +0000},
    owner = {dima},
    timestamp = {2013.04.15}
    }
  • [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, “On the accuracy of solving confluent Prony systems,” SIAM J. Appl. Math., vol. 73, iss. 1, pp. 134-154, 2013.
    [Bibtex]
    @Article{batenkov2011accuracy,
    author = {Batenkov, D. and Yomdin, Y.},
    title = {{On the accuracy of solving confluent Prony systems}},
    journal = {{SIAM J. Appl. Math.}},
    year = {2013},
    volume = {73},
    number = {1},
    pages = {134--154},
    abstract = {In this paper we consider several nonlinear systems of algebraic equations
    which can be called ``Prony-type''. These systems arise in various
    reconstruction problems in several branches of theoretical and applied
    mathematics, such as frequency estimation and nonlinear Fourier inversion.
    Consequently, the question of stability of solution with respect to
    errors in the right-hand side becomes critical for the success of
    any particular application. We investigate the question of ``maximal
    possible accuracy'' of solving Prony-type systems, putting stress
    on the ``local'' behavior which approximates situations with low
    absolute measurement error. The accuracy estimates are formulated
    in very simple geometric terms, shedding some light on the structure
    of the problem. Numerical tests suggest that ``global'' solution
    techniques such as Prony's algorithm and ESPRIT method are suboptimal
    when compared to this theoretical ``best local'' behavior.},
    date-modified = {2016-02-01 13:09:44 +0000},
    doi = {10.1137/110836584},
    owner = {dima},
    timestamp = {2012.10.24}
    }
  • [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] 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}
    }

2012

  • [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 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] [DOI] D. Batenkov, G. Dinkin, and Y. Yomdin, “Automatic animation of high resolution images,” in 2012 IEEE 27th Convention of Electrical Electronics Engineers in Israel (IEEEI), 2012, pp. 1-5.
    [Bibtex]
    @InProceedings{batenkov_automatic_2012,
    author = {Batenkov, D. and Dinkin, G. and Yomdin, Y.},
    title = {{Automatic animation of high resolution images}},
    booktitle = {2012 {IEEE} 27th {Convention} of {Electrical} {Electronics} {Engineers} in {Israel} ({IEEEI})},
    year = {2012},
    pages = {1--5},
    month = nov,
    abstract = {In the report, we present a novel photo-animation method and an animation tool for transformation of a photo into an animated video clip. In opposite to the existing tools, our technology provides both automatic and intuitive interactive photo-animation of high-resolution images. Our method and technology comprise the following main components: 1. Vectorization of the image, i.e. its representation by the sets of primitive structures (geometric models) in different scales. 2. 3D-2D global scale kinematic models for various image objects, especially, for the patterns of human bodies. These models allow an adaptation to definite parameters of the patterns and provide a high visual quality of motions' reproduction, including relatively large 3D rotations. 3. Tools and methods for translation of true 3D motion (like various scenarios of human 3D motion appearing in the Carnegie Mellon University database) into 2.5D animation. 4. Tools and methods for real-time automatic fitting of the models to image objects. In the course of fitting, specific anatomic parameters of the pattern are detected and preserved. The suggested method starts with face detection and model fitting, and then extends up to a full body pose capturing and model fitting. Our approach strongly relies on information provided by a vectorized image data, like the geometry of the edges and ridges and their color profiles, and on the transformations of 3D and 2D models. 5. High level scenarios and their automatic adaptation to the actual position of the characters in the photo. The presented technology is illustrated by several examples. Links to more running examples and to our on-line Photoanimation tool are provided.},
    doi = {10.1109/EEEI.2012.6376903},
    file = {Batenkov et al_2012_Automatic animation of high-resolution images.pdf:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/VE3ETQGV/Batenkov et al_2012_Automatic animation of high-resolution images.pdf:application/pdf;IEEE Xplore Abstract Record:/Users/dima/Library/Application Support/Zotero/Profiles/pvpguanx.default/zotero/storage/DSUFX5GJ/login.html:text/html},
    keywords = {2.5D animation, 3D-2D global scale kinematic models, 3D motion, 3D rotations, animated video clip, Animation, automatic photo-animation, Carnegie Mellon University database, color profiles, Computational modeling, computer animation, face detection, face recognition, Fitting, full body pose capturing, geometric modeling, geometric models, Geometry, high resolution images, high visual quality, human bodies, Humans, image colour analysis, image objects, image processing, image resolution, image vectorization, intuitive interactive photo-animation, Minimization, model fitting, motions reproduction, photoanimation, primitive structures, realtime automatic fitting, Skeleton, Solid modeling},
    owner = {dima},
    timestamp = {2016.08.04}
    }

2011

  • [PDF] [DOI] D. Batenkov, “Open BEAGLE: a generic framework for evolutionary computations,” Genetic Programming and Evolvable Machines, pp. 1-3, 2011.
    [Bibtex]
    @Article{genetic_beagle,
    author = {Batenkov, Dmitry},
    title = {{Open BEAGLE: a generic framework for evolutionary computations}},
    journal = {{Genetic Programming and Evolvable Machines}},
    year = {2011},
    pages = {1-3},
    note = {10.1007/s10710-011-9135-4},
    abstract = {Software frameworks for evolutionary computation are very important both for developing applications using known algorithms and also for writing new algorithms. One such framework is Open BEAGLE [5, 6]. Below I give a general overview of this framework.
    The project's leader (and principal developer) is Christian Cagne from Universite Laval, Canada. Development started in 1999 and the last stable version (3.0.3) was released in November 2007. Since February 2009 an alpha release of the next major version has been available.
    The name of the framework refers to the famous HMS Beagle, on which Charles Darwin made his voyage around the world [2]. Therefore, it is not surprising to find other software systems using this name both in genetic programming [3, 4] and in other fields [1].},
    affiliation = {Weizmann Institute of Science, Rehovot, Israel},
    bdsk-url-1 = {http://dx.doi.org/10.1007/s10710-011-9135-4},
    date-modified = {2016-02-01 13:18:33 +0000},
    doi = {10.1007/s10710-011-9135-4},
    issn = {1389-2576},
    keyword = {Computer Science},
    owner = {dima},
    publisher = {Springer Netherlands},
    timestamp = {2011.04.01},
    url = {http://dx.doi.org/10.1007/s10710-011-9135-4}
    }

2009

  • [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}
    }