User hans engler - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T02:47:48Z http://mathoverflow.net/feeds/user/7352 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115031/maximizing-the-cutnorm-for-matrices-with-low-rank Maximizing the cutnorm for matrices with low rank Hans Engler 2012-11-30T22:51:43Z 2012-11-30T22:51:43Z <p>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 <a href="http://www.cims.nyu.edu/~naor/homepage%2520files/cutnorm.pdf" rel="nofollow">SIAM J. Comput. vol. 35, 2006</a> 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.</p> <p>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.</p> <p>My question is whether there are also "better" approaches if $A$ has merely low rank > 1. </p> http://mathoverflow.net/questions/114977/spectrum-of-transition-matrix-for-symmetric-random-walk Spectrum of transition matrix for symmetric random walk Hans Engler 2012-11-30T13:37:31Z 2012-11-30T20:22:52Z <p>I asked this question previously on math.stackexchange.com, where it had little traction. </p> <p>Consider the symmetric random walk on ${0,1,…,n}$ with transition probabilities $P(j→j±1)=1/2$ for $0 &lt; j &lt; 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).</p> <p>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$.</p> <p>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. </p> <p>Does anybody know more?</p> http://mathoverflow.net/questions/94516/limit-of-a-rescaled-random-sum-of-i-i-d-random-variables/94563#94563 Answer by Hans Engler for Limit of a rescaled random sum of i.i.d. random variables Hans Engler 2012-04-19T19:53:06Z 2012-04-19T19:53:06Z <p>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. </p> <p>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$. </p> <p>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.</p> http://mathoverflow.net/questions/62218/german-mathematical-terms-like-nullstellensatz/91117#91117 Answer by Hans Engler for German mathematical terms like "Nullstellensatz" Hans Engler 2012-03-13T20:54:46Z 2012-03-13T20:54:46Z <p>All this should be compiled in a <em>Festschrift</em>.</p> http://mathoverflow.net/questions/90189/checking-consistency-of-a-system-of-linear-equations-and-inequalities/90199#90199 Answer by Hans Engler for Checking consistency of a system of linear equations and inequalities Hans Engler 2012-03-04T13:32:27Z 2012-03-04T13:44:30Z <p>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 &lt; \xi &lt; e_4$$ where $O &lt; \xi &lt; e_4$ is understood component wise. </p> <p>To check if there is a feasible solution, proceed in two steps:</p> <ol> <li><p>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.</p></li> <li><p>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.</p></li> </ol> <p>The entire method should be easily implementable in e.g. R (package lpSolve) and it is obvious how to parallelize it.</p> http://mathoverflow.net/questions/90051/do-these-kernel-functions-satisfy-the-semi-group-property/90119#90119 Answer by Hans Engler for Do these kernel functions satisfy the semi-group property? Hans Engler 2012-03-03T15:02:28Z 2012-03-03T15:02:28Z <p>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. </p> <p>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$. </p> <p>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 <a href="http://www.fracalmo.org/" rel="nofollow">http://www.fracalmo.org/</a>, maintained by F. Mainardi, that may be helpful.</p> http://mathoverflow.net/questions/70263/how-to-do-dft-for-irregular-sampling-period/70285#70285 Answer by Hans Engler for How to do DFT for irregular sampling period ? Hans Engler 2011-07-14T02:49:18Z 2011-07-14T15:26:41Z <p>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.</p> http://mathoverflow.net/questions/66656/c-0-semigroups-applications/66665#66665 Answer by Hans Engler for $C_0$-semigroups applications Hans Engler 2011-06-01T14:33:19Z 2011-06-01T14:33:19Z <p>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.</p> <p>There, I have done it and mentioned the names of two of my former colleagues </p> http://mathoverflow.net/questions/61839/efficient-algorithm-for-finding-the-minima-of-a-piecewise-linear-function/61854#61854 Answer by Hans Engler for Efficient algorithm for finding the minima of a piecewise linear function Hans Engler 2011-04-15T18:47:41Z 2011-04-15T18:57:07Z <p>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)$. </p> http://mathoverflow.net/questions/59690/does-there-exist-a-global-solution-in-l2-for-reaction-diffusion-equation-with-fo/61826#61826 Answer by Hans Engler for Does there exist a global solution in L^2 for reaction diffusion equation with focusing nonlinearity? Hans Engler 2011-04-15T15:12:23Z 2011-04-15T15:12:23Z <p>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:</p> <p><a href="http://repository.dl.itc.u-tokyo.ac.jp/dspace/bitstream/2261/6061/1/jfs130201.pdf" rel="nofollow">http://repository.dl.itc.u-tokyo.ac.jp/dspace/bitstream/2261/6061/1/jfs130201.pdf</a></p> <p>All nontrivial non-negative solution blow up in finite time if $\sigma &lt; \frac{2}{N}$. There has been a lot of work on this, see Google Scholar.</p> http://mathoverflow.net/questions/61465/working-with-group-means/61473#61473 Answer by Hans Engler for Working with group means Hans Engler 2011-04-12T21:33:23Z 2011-04-12T21:33:23Z <p>The proper way to do this is to model the $j$-th measurement $x_{ij}$ on the $i$-th student as</p> <p>$$x_{ij} = \mu_i + \delta_i + \epsilon_{ij} \quad (1 \le j \le n_i)$$</p> <p>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}$. </p> <p>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.</p> <p>Now use Analysis of Variance. All standard computer programs can do that for you.</p> http://mathoverflow.net/questions/61125/system-of-two-second-order-differential-equations/61228#61228 Answer by Hans Engler for system of two second order differential equations Hans Engler 2011-04-10T17:31:17Z 2011-04-10T17:31:17Z <p>You can reduce the number of parameters quite a bit, for starters. Set $$x = \alpha u , \; y = \beta v, \; t = \gamma \tau$$<br> 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.</p> http://mathoverflow.net/questions/61044/maximum-principle-for-weak-solutions/61052#61052 Answer by Hans Engler for Maximum principle for weak solutions Hans Engler 2011-04-08T11:49:57Z 2011-04-08T11:49:57Z <p>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). </p> <p>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). </p> http://mathoverflow.net/questions/114977/spectrum-of-transition-matrix-for-symmetric-random-walk/115014#115014 Comment by Hans Engler Hans Engler 2012-11-30T22:18:22Z 2012-11-30T22:18:22Z Thank you, just what I hoped for. http://mathoverflow.net/questions/114977/spectrum-of-transition-matrix-for-symmetric-random-walk/115018#115018 Comment by Hans Engler Hans Engler 2012-11-30T22:18:19Z 2012-11-30T22:18:19Z Thank you for providing a wider context. http://mathoverflow.net/questions/114977/spectrum-of-transition-matrix-for-symmetric-random-walk/114989#114989 Comment by Hans Engler Hans Engler 2012-11-30T22:18:13Z 2012-11-30T22:18:13Z Very interesting approach. http://mathoverflow.net/questions/114977/spectrum-of-transition-matrix-for-symmetric-random-walk/115021#115021 Comment by Hans Engler Hans Engler 2012-11-30T22:18:08Z 2012-11-30T22:18:08Z Interesting approach, thank you. http://mathoverflow.net/questions/114977/spectrum-of-transition-matrix-for-symmetric-random-walk/115017#115017 Comment by Hans Engler Hans Engler 2012-11-30T22:14:13Z 2012-11-30T22:14:13Z Thank you, this is a very helpful reference. http://mathoverflow.net/questions/114977/spectrum-of-transition-matrix-for-symmetric-random-walk Comment by Hans Engler Hans Engler 2012-11-30T15:33:56Z 2012-11-30T15:33:56Z Thank you, this is very useful indeed. http://mathoverflow.net/questions/103569/matrix-maximization Comment by Hans Engler Hans Engler 2012-07-31T13:52:00Z 2012-07-31T13:52:00Z You could start by using Lagrange multipliers. http://mathoverflow.net/questions/103297/coupled-system-of-linear-parabolic-pdes Comment by Hans Engler Hans Engler 2012-07-28T01:03:28Z 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$. http://mathoverflow.net/questions/94516/limit-of-a-rescaled-random-sum-of-i-i-d-random-variables Comment by Hans Engler Hans Engler 2012-04-19T12:14:07Z 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$? http://mathoverflow.net/questions/93899/chain-rule-for-fractional-laplacian Comment by Hans Engler Hans Engler 2012-04-14T14:56:23Z 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. http://mathoverflow.net/questions/89078/solution-of-heat-equation-with-neumann-bc-in-an-arbitrary-domain Comment by Hans Engler Hans Engler 2012-03-07T01:55:54Z 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. http://mathoverflow.net/questions/90051/do-these-kernel-functions-satisfy-the-semi-group-property Comment by Hans Engler Hans Engler 2012-03-03T19:48:49Z 2012-03-03T19:48:49Z You might also look at recent work by Cabr\'e and Roquejoffre, e.g. <a href="http://arxiv.org/abs/1202.6072" rel="nofollow">arxiv.org/abs/1202.6072</a> . http://mathoverflow.net/questions/70263/how-to-do-dft-for-irregular-sampling-period/70369#70369 Comment by Hans Engler Hans Engler 2011-07-15T01:54:23Z 2011-07-15T01:54:23Z If it's from Osnabr&#252;ck, I am endorsing it :) http://mathoverflow.net/questions/70263/how-to-do-dft-for-irregular-sampling-period/70285#70285 Comment by Hans Engler Hans Engler 2011-07-14T12:43:06Z 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. http://mathoverflow.net/questions/64486/optimization-help Comment by Hans Engler Hans Engler 2011-05-10T13:04:49Z 2011-05-10T13:04:49Z Have you tried the greedy approach?