User hans engler - MathOverflow

Maximizing the cutnorm for matrices with low rank

2012-11-30T22:51:43Z

Given an $m \times n$ matrix $A$ with positive and negative entries, consider the problem of maximizing the expression $\sum_{i,j} x_i y_j a_{ij}$ subject to the constraints $x_i, \, y_j = \pm 1$. It was shown by N. Alon and A. Naor in SIAM J. Comput. vol. 35, 2006 that this problem is MAX-SNP hard, and they gave a relaxation approach that uses semidefinite programming and that gets within 0.56 of the maximum.

On the other hand it is immediate that if $A = a b^t$ has rank 1, where $a, \ b$ are column vectors, then $x_i = sign\ a_i, \ y_j = sign \ b_j$ is the optimum.

My question is whether there are also "better" approaches if $A$ has merely low rank > 1.

Spectrum of transition matrix for symmetric random walk

2012-11-30T13:37:31Z

I asked this question previously on math.stackexchange.com, where it had little traction.

Consider the symmetric random walk on ${0,1,…,n}$ with transition probabilities $P(j→j±1)=1/2$ for $0 < j < n$ and $P(0→0)=P(0→1)=P(n→n)=P(n→n−1)=1/2$. I am interested in the spectrum of the transition matrix (which is symmetric, hence the spectrum is real).

Mathematica suggests that the characteristic polynomial of the transition matrix is of the form $p_n(x)=(1−x)q_n(x)$, where $q_n$ is a polynomial that is odd / even iff $n−1$ is odd / even and that has only simple zeroes. Therefore, the spectrum appears to be a symmetric set of n points from the open unit interval, plus the point $λ=1$.

It occurs to me that this ought to be well known. In particular, the factors $q_n(x)$ in the characteristic polynomials ought to be special.

Does anybody know more?

Answer by Hans Engler for Limit of a rescaled random sum of i.i.d. random variables

2012-04-19T19:53:06Z

A closely related problem was treated by H. Robbins, The asymptotic distribution of the sum of a random number of random variables, Bull. AMS 54(1948), 1151--1161, Math Reviews MR0027974.

In essence, under suitable nondegeneracy assumptions and assuming the existence of finite second moments, Robbins proves that the asymptotic (as $\alpha \to \infty$) distribution of $\frac{S_N - E(S_N)}{\sqrt{var(S_N)}}$ is related to the asymptotic distribution of a linear combination of $\frac{N - E(N)}{\sqrt{var(N)}}$ and another normal r.v. $Z$.

For the case where $var(N) = o(E(N)^2)$, the implication seems to be that $\frac{S_N}{E(S_N)} \stackrel{d}{\longrightarrow} 1$, a constant.

Answer by Hans Engler for German mathematical terms like "Nullstellensatz"

2012-03-13T20:54:46Z

All this should be compiled in a Festschrift.

Answer by Hans Engler for Checking consistency of a system of linear equations and inequalities

2012-03-04T13:32:27Z

To simplify the notation, let $A$ be the coefficient matrix in a given instance of your problem, let $\xi = ((x,y,z,w)^T)/2$, and let $O = (0,0,0,0)^T$, $e = (1,1,1,1,...)^T$, $e_4 = (1,1,1,1)^T$. The problem then can be written in shorthand as $$ A \xi = e, O < \xi < e_4 $$ where $O < \xi < e_4$ is understood component wise.

To check if there is a feasible solution, proceed in two steps:

Check if there is a feasible solution of the linear system $A \xi = e$. If there is one, it can be found as $\xi = (A^TA)A^Te$ and therefore $A(A^TA)^{-1}A^Te = e$ must hold. In practice, compute the $QR$ decomposition of $A$, $A = QR$ where $R$ is square and upper triangular and $Q$ has the same dimensions as $A$ and satisfies $Q^TQ = I$ (identity matrix) and look at the system $R \xi = Q^T e$. If $R$ has full rank, you can find $\xi$ and compare $A \xi $ to $e$. If $R$ does not have full rank (i.e. there are zero rows at the bottom), this also tells you if there is a solution.
Suppose now there is a nontrivial solution of $A \xi = e$. Then choose a small number $\epsilon$, e.g. $\epsilon = 10^{-8}$, and solve the linear program $$ A \xi = e, \epsilon e_4 \le \xi \le (1 - \epsilon) e_4, c^T \xi \to \max $$ with any vector $c$. If there is a feasible solution to the full problem, it will show up as the optimum (and some of its components may be equal to $\epsilon$ or $1 - \epsilon$). By varying $\epsilon$ for these problems, you may be able to find solutions which are further in the interior of the four-dimensional cube in which your solution is supposed to be.

The entire method should be easily implementable in e.g. R (package lpSolve) and it is obvious how to parallelize it.

Answer by Hans Engler for Do these kernel functions satisfy the semi-group property?

2012-03-03T15:02:28Z

Let $H_a(t,\xi) = \hat G_a(t,\xi)$ be the spatial Fourier transform of the kernel under study and let $h_a(\xi) = H_a(1,\xi)$. Then $H_a(t,\xi) = H_a(1,t^{1/a}\xi) = h_a(t^{1/a}\xi)$, from the scaling property stated in your question. The postulated semigroup property now implies that for all $\xi$ and all $t, s > 0$ $$h_a(t^{1/a}\xi)h_a(s^{1/a}\xi) = h_a((t+s)^{1/a}\xi) $$ and therefore $$ h_a(t^{1/a}\xi) = e^{A(\xi)t} $$ for some function $A(\xi)$ that may still depend on $a$. Since your kernel is assumed to be isotropic, $A$ can depend only on $|\xi|$. Another scaling argument then shows that $A(\xi) \propto |\xi|^a$ with a negative proportionality constant. Now if $a = 1$, then $A(\xi) \propto -|\xi|$, leading to the Poisson semigroup, which indeed has a kernel of this form. If $a = 2$, then you obtain the heat semigroup, with a very different kernel.

Your question boils down to asking whether for $a \ne 1$, the inverse Fourier transform of $e^{-|\xi|^a}$ is of the form $(1+|x|^{1+a})^{-1}$, up to scaling. This is not true for $a = 2$ and it cannot be true for positive even values of $a$, since in these cases $h_a(\xi)$ is analytic at $\xi = 0$ and hence its inverse Fourier transform must have moments of infinite order. I very much doubt that it is true for other $a \ne 1$.

Consult the book by Zolotarev on stable distributions for more detail. As Dr. Kochubei already stated, the book and papers by Eidelman are also helpful. Finally, there is a website on fractional differentiation and applications at http://www.fracalmo.org/, maintained by F. Mainardi, that may be helpful.

Answer by Hans Engler for How to do DFT for irregular sampling period ?

2011-07-14T02:49:18Z

In a nutshell, do a spline interpolation, resample, and then compute a DFT. You will encounter difficulties if the $t_{k+1}- t_k$ vary over several orders of magnitude because the smallest such gap dictates the interval width for resampling. You will also have immense trouble if the data are noisy - in that case you could try to denoise them first, e.g. using wavelets. Finally you will have to handle endpoint problems.

Answer by Hans Engler for $C_0$-semigroups applications

2011-06-01T14:33:19Z

The first theorem (proved by Richard Datko in the Hilbert space case and by Pazy in the Banach space case) is very useful to establish controllability for systems governed by hyperbolic differential equations. Examples include the boundary control of plates, rods, and other elastic structures. There is a book by Jack Lagnese and Jacques-Louis Lions on this general topic.

There, I have done it and mentioned the names of two of my former colleagues

Answer by Hans Engler for Efficient algorithm for finding the minima of a piecewise linear function

2011-04-15T18:47:41Z

This is a convex function of a single variable, so a derivative free search method such as Golden Section search will converge without problems. These methods all converge linearly, but they don't move along corners. The effort per function evaluation is $O(n)$.

Answer by Hans Engler for Does there exist a global solution in L^2 for reaction diffusion equation with focusing nonlinearity?

2011-04-15T15:12:23Z

There are non-trivial global smooth solutions with small $L^2$-norm and small $L^\infty$-norm if $\sigma > \frac{2}{N}$, by results of H. Fujita (J. Fac. Science Univ. Tokyo, 1966). Fujita's original is paper is here:

http://repository.dl.itc.u-tokyo.ac.jp/dspace/bitstream/2261/6061/1/jfs130201.pdf

All nontrivial non-negative solution blow up in finite time if $\sigma < \frac{2}{N}$. There has been a lot of work on this, see Google Scholar.

Answer by Hans Engler for Working with group means

2011-04-12T21:33:23Z

The proper way to do this is to model the $j$-th measurement $x_{ij}$ on the $i$-th student as

$$x_{ij} = \mu_i + \delta_i + \epsilon_{ij} \quad (1 \le j \le n_i)$$

where $n_i$ is the number of measurements for student $i$. Assume that $\mu_i = \mu_{WS}$ if student $i$ was born in Winter/Spring and $\mu_{i} = \mu_{SA}$ otherwise. You want to compare $\mu_{WS}$ to $\mu_{SA}$.

You can assume that the means of the $\delta_i$ over the two groups are both zero and have to assume that the $\epsilon_{ij}$ are independent random errors with zero means and the same standard deviations.

Now use Analysis of Variance. All standard computer programs can do that for you.

Answer by Hans Engler for system of two second order differential equations

2011-04-10T17:31:17Z

You can reduce the number of parameters quite a bit, for starters. Set $$x = \alpha u , \; y = \beta v, \; t = \gamma \tau $$
and write $\dot w = \frac{d}{d \tau} w, \ddot w = \frac{d^2}{d\tau^2} w$. By choosing the constants $\alpha, \beta, \gamma$ properly, you should be able to nondimensionalize the system to something like $$c u + (\dot v)^2 - \ddot u - d u \ddot v + v \ddot v = 0$$ $$1 - (\dot u)^2 - u \ddot u + d^{-1} \ddot u v - \ddot v = 0 $$ $$ u(0) = \tilde a, \; v(0) = \dot u(0) = \dot v(0) = 0. $$ So there are only three independent constants in the system, not 7.

Answer by Hans Engler for Maximum principle for weak solutions

2011-04-08T11:49:57Z

You might want to distinguish between maximum principles (which assert typically things like "the max of the solution is attained on the boundary / parabolic boundary of the set") and positivity, which assert things like "if the data are non-negative on the (parabolic) boundary, then so is the solution in the entire domain". The latter often can be shown with functional analytic techniques (see previous post).

As to maximum principles for generalized solutions, there is work by Jensen on viscosity solutions of fully nonlinear elliptic problems. And there is work in the 70s that extends maximum principles for elliptic equations to solutions in $W^{2,n}$ where $n$ is the spatial dimension (if I remember correctly).

Comment by Hans Engler

2012-11-30T22:18:22Z

Thank you, just what I hoped for.

Comment by Hans Engler

2012-11-30T22:18:19Z

Thank you for providing a wider context.

Comment by Hans Engler

2012-11-30T22:18:13Z

Very interesting approach.

Comment by Hans Engler

2012-11-30T22:18:08Z

Interesting approach, thank you.

Comment by Hans Engler

2012-11-30T22:14:13Z

Thank you, this is a very helpful reference.

Comment by Hans Engler

2012-11-30T15:33:56Z

Thank you, this is very useful indeed.

Comment by Hans Engler

2012-07-31T13:52:00Z

You could start by using Lagrange multipliers.

Comment by Hans Engler

2012-07-28T01:03:28Z

I don't think you'll get good results if the $a_i$ are merely continuous, since in that case there may not be a good maximal regularity theory. But if all coefficients and the $f_i$ are in $C^{\alpha,\alpha/2}$ in the sense of Ladyzhenskaya, then the mapping $M: f_1 \mapsto a_3u_{xx} + a_4 u_x + a_5 u$ is linear and bounded and therefore you are just solving a linear equation for $v$.

Comment by Hans Engler

2012-04-19T12:14:07Z

One can certainly say something if $N(\alpha)$ does not depend on $\alpha$. Do you also want to require that $E(N(\alpha)) \to \infty$?

Comment by Hans Engler

2012-04-14T14:56:23Z

I would begin by looking for analogues of the product rule. Once you have that, then the chain rule for the case where $g$ is a polynomial will follow, giving some insight into the general situation.

Comment by Hans Engler

2012-03-07T01:55:54Z

Are you expecting a formula like $u(x,t) = \int_\Omega k(x-y,t)u_0(y) dy$ or something like $u(x,t) = \int_\Omega k(x,y,t)u_0(y)dy$ ? I don't think something like the first formula can be true. For small $t$, such a $k$ would have to like the fundamental solution of the heat equation. At the same time, $u(x,t) \approx u_0(x)$ for small $t$. Near the boundary of $\Omega$, this cannot be possible.

Comment by Hans Engler

2012-03-03T19:48:49Z

You might also look at recent work by Cabr\'e and Roquejoffre, e.g. arxiv.org/abs/1202.6072 .

Comment by Hans Engler

2011-07-15T01:54:23Z

If it's from Osnabrück, I am endorsing it :)

Comment by Hans Engler

2011-07-14T12:43:06Z

@Rod - I did this for data coming from measurements in electronic circuits. Typically about 20K sample points, with $\frac{max_k(t_{k+1}-t_k)}{min_k(t_{k+1}-t_k)} \approx 10^3$ or so. The main advantage there was that $(t_{k+1}-t_k)$ varied very smoothly with $k$. The bottleneck turned out to be the spline interpolation, due to the differences in scales. I ended up using cubic box splines and then just adding (superposing) the dft's of these box splines explicitly (no fft after all). But that would not work if $(_{k+1}-t_k$ varies irregularly.

Comment by Hans Engler

2011-05-10T13:04:49Z

Have you tried the greedy approach?