Algebraic super-resolution

  • [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] 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}
    }
  • [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] 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}
    }
  • [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, “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 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}
    }