BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Yosef Yomdin

Yosef Yomdin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CAmath.NAmath.FANumerical AnalysisInformation Theorymath.GNmath.IT

Catalog footprint

What is connected

21works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2020arXiv

Super-resolution of near-colliding point sources

We consider the problem of stable recovery of sparse signals of the form $$F(x)=\sum_{j=1}^d a_jδ(x-x_j),\quad x_j\in\mathbb{R},\;a_j\in\mathbb{C}, $$ from their spectral measurements, known in a bandwidth $Ω$ with absolute error not exceeding $ε>0$. We consider the case when at most $p\le d$ nodes $\{x_j\}$ of $F$ form a cluster whose extent is smaller than the Rayleigh limit ${1\overΩ}$, while the rest of the nodes are well separated. Provided that $ε\lessapprox SRF^{-2p+1}$, where $SRF=(ΩΔ)^{-1}$ and $Δ$ is the minimal separation between the nodes, we show that the minimax error rate for reconstruction of the cluster nodes is of order ${1\overΩ}SRF^{2p-1}ε$, while for recovering the corresponding amplitudes $\{a_j\}$ the rate is of the order $SRF^{2p-1}ε$. Moreover, the corresponding minimax rates for the recovery of the non-clustered nodes and amplitudes are ${ε\overΩ}$ and $ε$, respectively. These results suggest that stable super-resolution is possible in much more general situations than previously thought. Our numerical experiments show that the well-known Matrix Pencil method achieves the above accuracy bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The spectral properties of Vandermonde matrices with clustered nodes

We study rectangular Vandermonde matrices $\mathbf{V}$ with $N+1$ rows and $s$ irregularly spaced nodes on the unit circle, in cases where some of the nodes are "clustered" together -- the elements inside each cluster being separated by at most $h \lesssim {1\over N}$, and the clusters being separated from each other by at least $θ\gtrsim {1\over N}$. We show that any pair of column subspaces corresponding to two different clusters are nearly orthogonal: the minimal principal angle between them is at most $$\fracπ{2}-\frac{c_1}{N θ}-c_2 N h,$$ for some constants $c_1,c_2$ depending only on the multiplicities of theclusters. As a result, spectral analysis of $\mathbf{V}_N$ is significantly simplified by reducing the problem to the analysis of each cluster individually. Consequently we derive accurate estimates for 1) all the singular values of $\mathbf{V}$, and 2) componentwise condition numbers for the linear least squares problem. Importantly, these estimates are exponential only in the local cluster multiplicities, while changing at most linearly with $s$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Doubling coverings of algebraic hypersurfaces

A doubling covering $\U$ of a complex $n$-dimensional manifold $Y$ consists of analytic functions $ψ_j:B_1\to Y$, each function being analytically extendable, as a mapping to $Y$, to a four times larger concentric ball $B_4$. Main result of this paper is an upper bound on the minimal number $κ({\U})$ of charts in doubling coverings of a manifold $Y$, being a compact part of a non-singular level hypersurface $Y=\{P=c\}$, where $P$ is a polynomial on $\C^n$ with non-degenerated critical points. We show that $κ({\U})$ is of order $\log({1}/ρ)$, where $ρ$ is the distance from $Y$ to the singular set of $P$. Our main motivation is that doubling coverings form a special class of "smooth parameterizations", which are used in bounding entropy type invariants in smooth dynamics on one side, and in bounding density of rational points in diophantine geometry on the other. Complexity of smooth parameterizations is a key issue in some important open problems in both areas. We also present connections between doubling coverings and doubling inequalities for analytic functions $f$ on $Y$, which compare the maxima of $|f|$ on couples of compact domains $Ω\subset G$ in $Y$. We shortly indicate connections with Kobayashi metric and with Harnack inequality.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

$(s,p)$-Valent Functions

We introduce the notion of $(\mathcal F,p)$-valent functions. We concentrate in our investigation on the case, where $\mathcal F$ is the class of polynomials of degree at most $s$. These functions, which we call $(s,p)$-valent functions, provide a natural generalization of $p$-valent functions (see~\cite{Ha}). We provide a rather accurate characterizing of $(s,p)$-valent functions in terms of their Taylor coefficients, through "Taylor domination", and through linear non-stationary recurrences with uniformly bounded coefficients. We prove a "distortion theorem" for such functions, comparing them with polynomials sharing their zeroes, and obtain an essentially sharp Remez-type inequality in the spirit of~\cite{Y3} for complex polynomials of one variable. Finally, based on these results, we present a Remez-type inequality for $(s,p)$-valent functions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Accuracy of spike-train Fourier reconstruction for colliding nodes

We consider Fourier reconstruction problem for signals F, which are linear combinations of shifted delta-functions. We assume the Fourier transform of F to be known on the frequency interval [-N,N], with an absolute error not exceeding e > 0. We give an absolute lower bound (which is valid with any reconstruction method) for the "worst case" reconstruction error of F in situations where the nodes (i.e. the positions of the shifted delta-functions in F) are known to form an l elements cluster of a size h << 1. Using "decimation" reconstruction algorithm 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 N*h of order of (2l-1)-st root of e the worst case reconstruction error of the cluster nodes is of the same order as h, 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 of 2l-st root of e.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Accuracy of Algebraic Fourier Reconstruction for Shifts of Several Signals

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 \cite{Bat.Sar.Yom2}, 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 \cite{Bat.Sar.Yom2} that in this way the reconstruction system is "decoupled" into $k$ separate systems, each including only one of the signals $f_j$. The resulting systems are of a "generalized Prony" form. However, the sampling sets as above may be non-uniform/not "dense enough" to allow for a unique reconstruction of the shifts and amplitudes. In the present paper we study uniqueness and robustness of non-uniform Fourier sampling of signals as above, investigating sampling of exponential polynomials with purely imaginary exponents. As the main tool we apply a well-known result in Harmonic Analysis: the Turán-Nazarov inequality (\cite{Naz}), and its generalization to discrete sets, obtained in \cite{Fri.Yom}. We illustrate our general approach with examples, and provide some simulation results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Local and global geometry of Prony systems and Fourier reconstruction of piecewise-smooth functions

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Taylor Domination, Difference Equations, and Bautin Ideals

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(λ)$ are polynomials in a finite-dimensional parameter $λ\in {\mathbb C}^n.$ We study "Bautin ideals" $I_k$ generated by $a_{1}(λ),\ldots,a_{k}(λ)$ in the ring ${\mathbb C}[λ]$ of polynomials in $λ$. \smallskip These three approaches turn out to be closely related. We present some results and questions in this direction.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Taylor Domination, Turán lemma, and Poincaré-Perron Sequences

We consider "Taylor domination" property for an analytic function $f(z)=\sum_{k=0}^{\infty}a_{k}z^{k},$ 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. \] This property is closely related to the classical notion of "valency" of $f$ in $D_R$. For $f$ - rational function we show that Taylor domination is essentially equivalent to a well-known and widely used Turán's inequality on the sums of powers. Next we consider linear recurrence relations of the Poincaré type \[ a_{k}=\sum_{j=1}^{d}[c_{j}+ψ_{j}(k)]a_{k-j},\ \ k=d,d+1,\dots,\quad\text{with }\lim_{k\rightarrow\infty}ψ_{j}(k)=0. \] We show that the generating functions of their solutions possess Taylor domination with explicitly specified parameters. As the main example we consider moment generating functions, i.e. the Stieltjes transforms \[ S_{g}\left(z\right)=\int\frac{g\left(x\right)dx}{1-zx}. \] We show Taylor domination property for such $S_{g}$ when $g$ is a piecewise D-finite function, satisfying on each continuity segment a linear ODE with polynomial coefficients.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Algebraic signal sampling, Gibbs phenomenon and Prony-type systems

Systems of Prony type appear in various signal reconstruction problems such as finite rate of innovation, superresolution and Fourier inversion of piecewise smooth functions. We propose a novel approach for solving Prony-type systems, which requires sampling the signal at arithmetic progressions. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An observation on the Turán-Nazarov inequality

The main observation of this note is that the Lebesgue measure $μ$ in the Turán-Nazarov inequality for exponential polynomials can be replaced with a certain geometric invariant $ω\ge μ$, which can be effectively estimated in terms of the metric entropy of a set, and may be nonzero for discrete and even finite sets. While the frequencies (the imaginary parts of the exponents) do not enter in the original Turán-Nazarov inequality, they necessarily enter the definition of $ω$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Decoupling of Fourier Reconstruction System for Shifts of Several Signals

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_ł), \ ł\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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Geometry and Singularities of the Prony mapping

Prony mapping provides the global solution of the Prony system of equations \[ Σ_{i=1}^{n}A_{i}x_{i}^{k}=m_{k},\ k=0,1,...,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 $δ$-functions of the form $g(x)=\sum_{i=1}^{n}a_{i}δ(x-x_{i})$, with the unknown parameters $a_{i},\ x_{i},\ i=1,...,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 \cite{yom2009Singularities} 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Remez-Type Inequality for Smooth Functions

The classical Remez inequality bounds the maximum of the absolute value of a polynomial $P(x)$ of degree $d$ on $[-1,1]$ through the maximum of its absolute value on any subset $Z$ of positive measure in $[-1,1]$. Similarly, in several variables the maximum of the absolute value of a polynomial $P(x)$ of degree $d$ on the unit ball $B^n \subset {\mathbb R}^n$ can be bounded through the maximum of its absolute value on any subset $Z\subset Q^n_1$ of positive $n$-measure $m_n(Z)$. In \cite{Yom} a stronger version of Remez inequality was obtained: the Lebesgue $n$-measure $m_n$ was replaced by a certain geometric quantity $ω_{n,d}(Z)$ satisfying $ω_{n,d}(Z)\geq m_n(Z)$ for any measurable $Z$. The quantity $ω_{n,d}(Z)$ can be effectively estimated in terms of the metric entropy of $Z$ and it may be nonzero for discrete and even finite sets $Z$. In the present paper we extend Remez inequality to functions of finite smoothness. This is done by combining the result of \cite{Yom} with the Taylor polynomial approximation of smooth functions. As a consequence we obtain explicit lower bounds in some examples in the Whitney problem of a $C^k$-smooth extrapolation from a given set $Z$, in terms of the geometry of $Z$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the accuracy of solving confluent Prony systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Reconstruction of Planar Domains from Partial Integral Measurements

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 domains with piecewise-algebraic and, in particular, piecewise-polynomial boundaries. Our approach is based on one-dimensional reconstruction method of [Bat]* 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 polynomials), invisibility for powers of a given polynomial, and invisibility for complex moments (Wermer's theorem and further developments). The common property we would like to stress is a "rigidity" and symmetry of the invisible objects. * D.Batenkov, Moment inversion of piecewise D-finite functions, Inverse Problems 25 (2009) 105001

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Algebraic reconstruction of piecewise-smooth functions from integral measurements

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Algebraic Fourier reconstruction of piecewise smooth functions

Accurate reconstruction of piecewise-smooth functions from a finite number of Fourier coefficients is an important problem in various applications. The inherent inaccuracy, in particular the Gibbs phenomenon, is being intensively investigated during the last decades. Several nonlinear reconstruction methods have been proposed, 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^{-(d+2)}$, and the values of the function between the jumps with accuracy $\sim k^{-(d+1)}$ (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 a highly correlated error terms in the Fourier coefficients, which eventually cancel out in the corresponding algebraic equations. To handle more than one jump, we propose to apply a localization procedure via a convolution in the Fourier domain.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Rotation of Trajectories of Lipschitz Vector Fields

We prove that in finite time a trajectory of a Lipschitz vector field in $\hbox{\bbbb R}^{\hbox{\tmm n}}$ can not have infinite rotation around a given point. This result extends to the mutual rotation of two trajectories of a field in $\hbox{\bbbb R}^{\hbox{\tmm 3}}$: this rotation is bounded from above on any finite time interval. The bounds we give are only in terms of the Lipschitz constant of the field and the length of the time interval.

0 citations0 reviewsNo code linkedOpen access