# Algebraic super-resolution

• 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}
}
• 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}
}
• 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. },
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},
urldate = {2014-11-29}
}
• 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}
}
• 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}
}
• 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},
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}
}
• 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}
}