User dima - MathOverflow

Constructing a linear ODE for a product of two holonomic functions without introducing additional singularities

2013-03-29T10:45:18Z

A function $f$ is called holonomic if it satisfies some linear differential equation with polynomial coefficients $$p_n(x) f^{(n)}(x)+\dots+p_1(x)f'(x)+p_0(x)f(x)=0.$$ Now if $f,g$ are holonomic then so are their sum and product. To obtain a differential equation for $h=fg$, first observe that $$ h^{(k)} = \sum_{i=0}^k {k\choose i} f^{(i)} g^{(k-i)}.$$ Since each $f^{(i)}$ is a linear combintation of $f,f',\dots,f^{(n-1)}$ with rational coefficients (where $n$ is the order of the ODE satisfied by $f$), and analogously each $g^{(i)}$ is a linear combination of $g,g',\dots,g^{(m-1)}$, then $h,h',h'',\dots$ span a finite-dimensional vector space of dimension at most $d=mn$, and hence there exists a nontrivial relation of the form $$ r_d(x)h^{(d)}+\dots+r_1(x)h'+r_0(x)h=0$$with $r_i(x)$ rational functions.

Now suppose that the ODE which $f$ satisfies had singular points $u_1,\dots,u_n$, while the equation of $g$ had singular points $w_1,\dots,w_m$. The ODE for $h$ might have additional singular points besides $u_1,\dots,u_n,w_1,\dots,w_m$. For example, if $$(x-a)f''(x)+cf(x)=0\\ (x-b)g''(x)+dg(x)=0$$ then $h=fg$ satisfies an ODE of order 4 with leading coefficient $$(x-a)^3 (x-b)^3 \biggl((c-d)x-(bc-ad)\biggr)h^{(4)}+\dots$$ (I calculated this using C.Mallinger's GeneratingFunctions Mathematica package).

Is it possible to construct a holonomic ODE for $h$ (in the above example and in general) without introducing additional singular points?

Smallest Lipschitz constant on non-convex domains

2012-12-05T01:27:07Z

It is well known that if a function $f:U\to \mathbb C^n$, $U\subset \mathbb C^m$ satisfies $\sup_{x\in U}\|Df(x)\|_{\infty} = C < \infty$ uniformly on $U$ and $U$ is compact and convex, then $f$ is Lipschitz with smallest possible constant $C$.

What if $U$ is non-convex, but still compact and connected? Is there any reasonable "measure of non-convexity" which can be used to bound the Lipschitz constant of such $f$?

Approximation power of wavelets

2012-12-03T10:43:45Z

The Wikipedia article on Wavelet Transform states that:

Wavelet compression is not good for all kinds of data: transient signal characteristics mean good wavelet compression, while smooth, periodic signals are better compressed by other methods, particularly traditional harmonic compression (frequency domain, as by Fourier transforms and related).

What is the precise quantification of this statement? For the smooth periodic signals we have for example: if the signal is of class $C^d$ of $d$-times continuously differentiable periodic functions, then the partial Fourier sum of order $N$ gives uniform approximation error at most $N^{-d-1}$. What would be the corresponding characterization for wavelet series?

To make the question more concrete: if the signal is piecewise $C^d$-periodic, with, say, one discontinuity, what approximation error do I get with $N$ wavelet coefficients (the Fourier approximation gives only $N^{-1}$ away from the discontinuity)? Conversely, how many coefficients do I need to get an accuracy $\epsilon$?

Norm of inverse confluent Vandermonde matrix

2012-11-30T12:25:07Z

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as $$V= \begin{bmatrix} v_{1,0}&v_{2,0}&\dots&v_{n,0}\\ v_{1,1}&v_{2,1}&\dots&v_{n,1}\\ \vdots\\ v_{1,N-1}&v_{2,N-1}&\dots&v_{n,N-1} \end{bmatrix}$$ where $v_{j,k}=\begin{bmatrix}x_j^k,&kx_j^{k-1},&\dots&k(k-1)\times\dots\times (k-l_j+1) x_j^{k-l_j+1}\end{bmatrix}$. Let $\|\cdot\|$ denote the row sum matrix norm. In some applications (e.g. interpolation, signal processing) one would like to estimate the quantity $\|V^{-1}\|$.

Gautschi [1] has shown that for $l_1=\dots=l_n=2$ one has $$ \|V^{-1}\| \leq \max_{1\leq \lambda\leq n} \beta_{\lambda} \prod_{\nu=1,\nu\neq\lambda}^n \biggl(\frac{1+|x_{\lambda}|}{|x_{\nu}-x_{\lambda}|}\biggr)^2$$ where $\beta_{\lambda}=\max\biggl(1+|x_{\lambda}|,1+2(1+|x_{\lambda}|)\sum_{\nu\neq\lambda}{1\over |x_\nu-x_\lambda|}\biggr)$.

I am interested in a somewhat cruder estimates, as follows: if $|x_j|\leq 1$ and $|x_i-x_j|\geq \delta$, then for the above case we have $$\|V^{-1}\| \leq C n 2^N\delta^{-N+1}\qquad (*)$$ for some absolute constant $C$.

Is it true that something like $(*)$ holds for the general configuration $\{l_1,\dots,l_n\}$?

EDIT: using [2], this seems to boil down to the following. Let $$ h_j(x)=\prod_{i \neq j}(x-x_i)^{-l_i}.$$ For $t=0,1,\dots,l_j$ evaluate $h_j^{(t)}(x_j).$

[1] W.Gautschi, "On Inverses of Vandermonde and Confluent Vandermonde matrices II", Numerische Mathematik 5, 425-430, 1963.

[2] R.Schapelle, "The Inverse of the Confluent Vandermonde Matrix", IEEE Trans. on Automatic Control, October 1972, pp.724-725.

Answer by dima for Norm of inverse confluent Vandermonde matrix

2012-12-01T17:55:31Z

For $j=1,\dots,n$ and $k=0,1,\dots,l_j-1$ denote by $u_{j,k}$ the row with index $l_1+\dots +l_{j-1}+k$ of the matrix $V^{-1}$. By using a generalization of the Hermite interpolation formula (see [3]), in [2] it is shown that the elements of $u_{j,k}$ are the coefficients of the polynomial $$ {1\over k!} \sum_{t=0}^{l_j-1-k} {1\over t!} h_j^{(t)}(x_j) (x-x_j)^{k+t} \prod_{i\neq j} (x-x_i)^{l_i} $$

Now thanks to the answer to this MSE question, one has $$ |h_j^{(t)}(x_j)|\leq N(N+1)\cdots (N+t-1)\delta^{-N-t}. $$

The sum of absolute values of the coefficients of the polynomials $(x-x_j)^{k+t} \prod_{i\neq j} (x-x_i)^{l_i}$ is at most (see [4, Lemma]) $$ (1+|x_j|)^{k+t} \prod_{i\neq j}(1+|x_i|)^{l_i} \leq 2^{N-(l_j-k-t)}. $$

So now $$ \|u_{j,k}\| \leq {1\over k!}\sum_{t=0}^{l_j-1-k} {1\over t!} {N(N+1)\cdots (N+t-1) \over {\delta^{N+t}}}2^{N-l_j+k+t}\\ \leq \biggl({2\over \delta}\biggr)^N {1\over {2^{l_j-k}k!}}\sum_{t=0}^{l_j-1-k} {l_j-1-k \choose t} {N(N+1)\cdots(N+t-1)\over (l_j-k-t)\cdots(l_j-k-2)(l_j-k-1)} \biggl({2\over \delta}\biggr)^t\\ \leq \biggl({2\over \delta}\biggr)^N {1\over {2^{l_j-k}k!}} \biggl(1+{2N\over \delta}\biggr)^{l_j-1-k}\\ =\biggl({2\over \delta}\biggr)^N {2\over k!} \biggl({1\over 2}+{N\over\delta}\biggr)^{l_j-1-k}. $$

[3] A.Spitzbart, "A Generalization of Hermite's Interpolation Formula", The American Mathematical Monthly, Vol.67 No.1, p.42-46, 1960.

[4] W.Gautschi, "On Inverses of Vandermonde and Confluent Vandermonde matrices", Numerische Mathematik 4, p.117-123, 1962.

Perturbations of zero-dimensional algebraic varieties

2012-11-29T10:00:51Z

Let $P(z,w):\mathbb C^2\to\mathbb C$ be a certain polynomial, and consider $p(s,t)=P(e^{is},e^{it}):\mathbb T^2\to \mathbb C$ its restriction to the real torus. Assume generic situation, so by counting dimensions, the set $Z=\{(s,t): p(s,t)=0\}\subset \mathbb T^2$ is discrete.

Now assume that the original polynomial is perturbed slightly, $Q(z,w)=P(z,w)+R(z,w)$ where coefficients of $R(z,w)$ are small (in a controllable manner) w.r.t those of $P$.

Can I in principle estimate the magnitude of the corresponding perturbation of the set Z? (In the one-dimensional case, without the restriction on the circle, this would be just Rouche's theorem.)

I would like something like this: if the norm of the coefficients of $R$ is at most $\epsilon\ll 1$, then the distances of the elements of the new zero set $Z'=\{(s,t): Q(e^{is},e^{it})=0\}$ from their counterparts in $Z$ are bounded by some function of $\epsilon$.

I'm thinking about passing from $p$ to a meromorphic function by defining a suitable complex structure on $\mathbb T^2$ and then applying Rouche's theorem, but I don't quite understand how to do this properly.

A.G. Vitushkin's "Easily representable families of functions" - can it be generalized?

2012-11-18T12:59:02Z

Background

In his monograph "Estimation of the complexity of the tabulation problem" (translated into English as "Theory of the Transmission and Processing of Information") Vitushkin studies efficient representation of (compact) function classes $F$ defined on some compact set $G$ (continuous, smooth, analytic) by "tables". Let's say that we would like to approximate an element $f\in F$ up to accuracy $\epsilon$. A "table" can be thought of as a mapping $\Gamma:\omega^p \to N_{\epsilon}(F)$ where $N_{\epsilon}(F)$ is an $\epsilon$-net of $F$ and $\omega$ is a finite set of numbers (everything is considered in the uniform norm). The quantity $|\omega|^p$ is called the "table volume", and clearly it cannot be smaller than the minimal size of an $\epsilon$-net of $F$. Therefore $$p\log_2 |\omega| \geq H_{\epsilon}(F)\qquad (1)$$ where $H_{\epsilon}(F)=\log N_{\epsilon}(F)$ is the Kolmogorov's $\epsilon$-entropy.

Obviously, nothing more concrete can be said without restricting the nature of the reconstruction/approximation algorithms $\Gamma$. Vitushkin takes $$\Gamma = \{ P_x(\omega_1,\dots,\omega_p); \deg P\leq k \}$$ where $P$ is a poloynomial in $p$ variables of degree $k$ in each one, whose coefficients depend somehow on the coordinates $x\in G$. Then he shows that

For subspaces $F$ of $d$-times continuously differentiable functions $$p\log(k+1)\geq H_{\epsilon}(F)$$
For subspaces $F$ of analytic functions $$p\log({k+1\over \epsilon}) \geq H_{\epsilon}(F) \qquad (2)$$

Assume for the rest of the discussion that $k$ is fixed. Then the above suggests that "the complexity of representation" of analytic functions (the number of parameters $p$ in the table) can be made much smaller (by a factor of $\log {1\over \epsilon}$) than by using only considerations of metric entropy (compare $(2)$ with $(1)$).

Easily representable families

In proving $(2)$ Vitushkin uses the fact that the analytic functions are "easily representable", in the following sense.

Definition 1 For any finite subset $S=\{s_1,\dots,s_n\} \subset G$ of cardinality $n$, let $f(S)$ denote the set $$ f(S) = \{ \left(\Re f(s_1),\Re f(s_2),\dots,\Re f(s_n), \Im f(s_1),\Im f(s_2),\dots,\Im f(s_n) \right) : \; f\in F\} \subset \mathbf R^{2n}.$$

Definition 2: For given $\delta\geq \epsilon$, let $\nu_\epsilon^\delta(F)$ denote the minimal size of a subset $\alpha_\epsilon^\delta \subset G$ for which $$ H_\epsilon(f(\alpha_\epsilon^\delta)) \geq H_\delta(F).$$

Definition 3 A subspace $F$ is called "easily representable" if there exists a function $\delta=\delta(\epsilon)\geq 2\epsilon$, decreasing monotonically to zero as $\epsilon\to 0$, such that for any $B>0$ and for sufficiently small $\epsilon$ we have $\nu_{B\epsilon}^{\delta(\epsilon)} < +\infty$, and $$ \lim_{\epsilon\to 0} {\nu_{B\epsilon}^{\delta(\epsilon)} \over H_{\delta(\epsilon)}(F)}=0.$$

My question

Are there any known generalizations of the above ideas? For instance, the construction of the set $f(S)$ can be considered as a transformation of the space $F$ by the collection of linear functionals $$\{\delta_{s_1},\dots,\delta_{s_n} \} $$ (here $\delta$ is the delta-function).

Can one replace this collection by another set of linear functionals (i.e. changing Definition 1 to some other Definition 1'), and still get meaningful results, i.e. a non-empty set of "easily representable functions" in this new sense? What if one takes the first $n$ Fourier coefficients? (in this case one should also probably change the metric to $L^2$). Or even an arbitrary/random collection of $n$ linear functionals?

Answer by dima for n-widths and Kolmogorov's entropy

2012-11-08T14:58:48Z

I would also recommend "Nonlinear Methods of Approximation" by V.N.Temlyakov.

Worst-case error and Cramer-Rao Lower Bound - is there any mathematical relation between them?

2012-11-05T14:44:49Z

I would like to understand the relation (if any) between the Cramer-Rao Lower Bound of estimation theory and the following simple definition of "reconstruction accuracy" which doesn't use any statistical framework.

Let $\theta\in\Theta\subset \mathbb{R}^n$ be an unknown parameter vector and let $x=f(\theta)\subset\mathbb{R}^m$ be a set of measurements, from which $\theta$ is to be reconstructed. Assume that the absolute error in each measurement is bounded from above by $\epsilon>0$, and otherwise nothing is known about the measurement error. Let $T_{\theta,\epsilon}=f^{-1}(x+B(0,\epsilon))$ (the full preimage, always well-defined). Obviously, $\theta\in T_{\theta,\epsilon}$. The "best possible" reconstruction accuracy is defined as $\delta_{\theta,\epsilon}=\sup_{t\in T_{\theta,\epsilon}} \|t-\theta\|$.

(Informal justification for the definition: if the measurement error is bounded by $\epsilon$, the original parameter vector $\theta$ can only be recovered up to accuracy $\delta_{\theta,\epsilon}$ because any parameter vector $\hat\theta\in T_{\theta,\epsilon}$ could have produced a measurement vector $\hat x \in B(x,\epsilon)$.)

In contrast, Cramer-Rao lower bound depends on some distribution $p(x;\theta)$ of the measurements, and gives a bound on the variance of any unbiased estimator $\hat \theta$ of $\theta$ satisfying some regularity conditions.

Apparently, the two notions are different and in general not comparable.

Still, are there cases in which the Cramer-Rao bound can be thought of as the $\delta_{\theta,\epsilon}$ defined above?

Example

Consider the simple case of a single parameter. Assuming $f'(\theta)\neq 0$, first-order approximation of the reconstruction accuracy as defined above is $$\delta_{\theta,\epsilon}\approx \frac{\epsilon}{f'(\theta)}. \qquad (1) $$ On the other hand, assuming that the measurements are modeled as $$ x = f(\theta) + w$$ where $w$ is Gaussian with zero mean and variance $\sigma^2$, we have (see e.g. Kay's book, section 3.5) $$ CRB{\theta} = \frac{\sigma^2}{\biggl(\frac{\partial f}{\partial \theta}\biggr)^2} \qquad (2)$$

Comparing $(1)$ and $(2)$ seems to suggest that in this case the notions are very closely related.

Prove that a particular polynomial sequence is a Sturm sequence

2012-10-17T12:45:41Z

Let us define the following sequence of polynomials for every two non-negative integers $i,d$: $$s_i^d(w)=\sum_{j=0}^{d+1} (-1)^j {d+1\choose j} (j+1)^i w^{d+1-j}.$$ Conjecture: The sequence ${s_d^d(w),s_d^{d-1}(w),\dots,s_d^0(w)}$ is a Sturm sequence.

An easy corollary of this conjecture is that:

Corollary: For $i\geq d$, the roots of the polynomial $s_i^d(w)$ are all real, simple (and positive).

Any idea how to prove either the Conjecture or (directly) the Corollary? Or, in the worst case, the Corollary for the special case $i=d$?

Note that:

$s_0^d(w)=(w-1)^{d+1}$
$s_i^0(w)=w-2^i$
${d\over dw} s_i^d(w)=(d+1)s_i^{d-1}(w)$.

Lower asymptotic bounds for the derivative of Laguerre polynomials

2012-10-17T13:00:57Z

Let $ L_{d}^{(1)}(x)$ denote the generalized Laguerre polynomial of degree $d$ and order $\alpha=1$. Clearly, since all the roots $r_1,\dots,r_d$ of $L_{d}^{(1)}$ are simple, there exists a strictly positive function $C=C(d)$ for which $$ \min_{i=1,\dots,d} |L'^{(1)}_{d} (r_i)| \geq C(d) > 0.$$

I would like to have a lower asymptotic bound for $C(d)$ (i.e. as rapidly increasing/slowly decreasing as possible).

Comment by dima

2013-04-04T11:19:34Z

Thanks Manuel! That kind of things is exactly what I needed.

Comment by dima

2013-03-31T12:48:41Z

Since my German is nonexistent, could you please pinpoint the location in the paper where they talk about the case of one singular point? Also, I couldn't figure out if they always assume that the solutions of the ODEs are entire functions...

Comment by dima

2012-12-05T10:18:28Z

Of course, should have figured this out myself. Thanks!

Comment by dima

2012-12-05T00:18:55Z

@Alexandre: a Jordan block with zero eigenvalue would not correspond to an invertible map, I think

Comment by dima

2012-12-05T00:13:14Z

I now realize that this is just a question about smallest Lipschitz constant.

Comment by dima

2012-12-04T23:44:53Z

@Deane: you are right, I probably complicated things by going to the inverse. So the question is just this: if $C=\max_{x\in D} \|J_{f}(x)\|_2$, is it true that for every $\delta x$ one has $\|f(x+\delta x)-f(x)\|_2 \leq C \|\delta x\|_2$? I guess I will rewrite the question.

Comment by dima

2012-12-04T21:59:17Z

The spectral norm is the largest singular value.

Comment by dima

2012-12-04T21:58:33Z

@Alexandre of course this should be $\max$ and not $\min$. I also want the inequality to hold for all appropriate $\delta y$ (and not just locally), that's why I assume $f$ to be 1-1 and onto.

Comment by dima

2012-12-03T16:02:08Z

OK, this is nice, thanks. I would really like to know, though, what happens for $d\geqslant 2$...

Comment by dima

2012-12-03T13:32:56Z

+1 for the link. Still, this is for me very confusing. What if I want to approximate the function with accuracy $\epsilon$, how large should I take $k$ to be? Consequently, how many wavelet coefficients are needed?

Comment by dima

2012-10-18T20:27:58Z

Now this is perfect.

Comment by dima

2012-10-18T16:23:24Z

Indeed the proof of the recurrence is straightforward. However this last step (proving that $s^d_d$ is square-free) is right now elusive.

Comment by dima

2012-10-18T15:26:15Z

These polynomials appear as first-order approximations in some nonlinear reconstruction problems, see e.g. arxiv.org/abs/1005.1884. If we substitute $t=-w$ we get a polynomial with positive coefficients and preserving the multiplicities of the roots. So, if positive-coefficient sequence is Sturm, it should be sufficient for our purposes.

Comment by dima

2012-10-18T12:58:43Z

Rewrite the recurrence as $$s_{i+1}^d(w)=(d+2)s_i^d(w)-ws'_i^d(w)$$ Now by [Polya & Szego, Vol. 2, Part 5, Problem 66] we have that $s_{i+1}^d$ has no more imaginary roots than $s_i^d$. But $s_0^d=(w-1)^{d+1}$, therefore $s_i^d$ has only real roots for all $i\geq 0$. The only thing left is to show that $s_d^d$ has no multiple roots.

Comment by dima

2012-10-18T11:50:15Z

what is the induction basis? If it's $\{n=0,1; k=0\}$, then the inductive argument doesn't help to prove the interlacing for $n>0$ (one cannot take the basis to be $\{n=0,1,…,d;k=0\}$ since $s^d_0=(x−1)^{d+1}$ and therefore no interlacing between $s^{d−1}_0$ and $s^d_0$).