Convergence Properties of a Self-adaptive Levenberg-Marquardt Algorithm Under Local Error Bound Condition

We propose a new self-adaptive Levenberg-Marquardt algorithm for the system of nonlinear equations F(x) = 0. The Levenberg-Marquardt parameter is chosen as the product of ‖F_k‖^δ with δ being a positive constant, and some function of the ratio between the actual reduction and predicted reduction of the merit function. Under the local error bound condition which is weaker than the nonsingularity, we show that the Levenberg-Marquardt method converges superlinearly to the solution for δ∈ (0, 1), while quadratically for δ∈ [1, 2]. Numerical results show that the new algorithm performs very well for the nonlinear equations with high rank deficiency. This work is supported by Chinese NSFC grants 10401023 and 10501013, Research Grants for Young Teachers of Shanghai Jiao Tong University, and E-Institute of Shanghai Municipal Education Commission, N. E03004.     

Rates of Convergence of Means of Euclidean Functionals

Let L be the Euclidean functional with p-th power-weighted edges. Examples include the sum of the p-th power-weighted lengths of the edges in minimal spanning trees, traveling salesman tours, and minimal matchings. Motivated by the works of Steele, Redmond and Yukich (Ann. Appl. Probab. 4, 1057–1073, 1994, Stoch. Process. Appl. 61, 289–304, 1996) have shown that for n i.i.d. sample points {X ₁,…,X _n } from [0,1] ^d , L({X ₁,…,X _n })/n ^(d−p)/d converges a.s. to a finite constant. Here we bound the rate of convergence of EL({X ₁,…,X _n })/n ^(d−p)/d . Y. Koo supported by the BK21 project of the Department of Mathematics, Sungkyunkwan University. S. Lee supported by the BK21 project of the Department of Mathematics, Yonsei University.     

Towards a Characterization of Markov Processes Enjoying the Time-Inversion Property

We give a necessary and sufficient condition for a homogeneous Markov process taking values in ℝ ⁿ to enjoy the time-inversion property of degree α. The condition sets the shape for the semigroup densities of the process and allows to further extend the class of known processes satisfying the time-inversion property. As an application we recover the result of Watanabe (Z. Wahrscheinlichkeitstheor. Verwandte Geb. 31:115–124, 1975) for continuous and conservative Markov processes on ℝ₊. As new examples we generalize Dunkl processes and construct a matrix-valued process with jumps related to the Wishart process by a skew-product representation.      

Global Heat Kernel Estimates for Relativistic Stable Processes in Half-space-like Open Sets

In this paper, by using probabilistic methods, we establish sharp two-sided large time estimates for the transition densities of relativistic α-stable processes with mass m ∈ (0, 1] (i.e., for the Dirichlet heat kernels of m − (m ^2/α  − Δ) ^α/2 with m ∈ (0, 1]) in half-space-like C ^{1, 1} open sets. The estimates are uniform in m in the sense that the constants are independent of m ∈ (0, 1]. Combining with the sharp two-sided small time estimates, established in Chen et al. (Ann Probab, 2011), valid for all C ^{1, 1} open sets, we have now sharp two-sided estimates for the transition densities of relativistic α-stable processes with mass m ∈ (0, 1] in half-space-like C ^{1, 1} open sets for all times. Integrating the heat kernel estimates with respect to the time variable, one can recover the sharp two-sided Green function estimates for relativistic α-stable processes with mass m ∈ (0, 1] in half-space-like C ^{1, 1} open sets established recently in Chen et al. (Stoch Process their Appl, 2011).     

Convergence to equilibria and blowup behavior of global strong solutions to the Stokes approximation equations for two-dimensional compressible flows with large data

This paper concerns the large time behavior of strong and classical solutions to the two-dimensional Stokes approximation equations for the compressible flows. We consider the unique global strong solution or classical solution to the two-dimensional Stokes approximation equations for the compressible flows with large external potential force, together with a Navier-slip boundary condition, for arbitrarily large initial data. Under the conditions that the corresponding steady state exists uniquely with the steady state density away from vacuum, we prove that the density is bounded from above independently of time, consequently, it converges to the steady state density in L^p and the velocity u converges to the steady state velocity in W^1,p for any 1p<∞ as time goes to infinity; furthermore, we show that if the initial density contains vacuum at least at one point, then the derivatives of the density must blow up as time goes to infinity.     

Exact Rate of Convergence of Some Approximation Schemes Associated to SDEs Driven by a Fractional Brownian Motion

In this article, we derive the exact rate of convergence of some approximation schemes associated to scalar stochastic differential equations driven by a fractional Brownian motion with Hurst index H. We consider two cases. If H>1/2, the exact rate of convergence of the Euler scheme is determined. We show that the error of the Euler scheme converges almost surely to a random variable, which in particular depends on the Malliavin derivative of the solution. This result extends those contained in J. Complex. 22(4), 459–474, 2006 and C.R. Acad. Sci. Paris, Ser. I 340(8), 611–614, 2005. When 1/6<H<1/2, the exact rate of convergence of the Crank-Nicholson scheme is determined for a particular equation. Here we show convergence in law of the error to a random variable, which depends on the solution of the equation and an independent Gaussian random variable.     

Fredholm properties of Riemannian exponential maps on diffeomorphism groups

We prove that exponential maps of right-invariant Sobolev H ^r metrics on a variety of diffeomorphism groups of compact manifolds are nonlinear Fredholm maps of index zero as long as r is sufficiently large. This generalizes the result of Ebin et al. (Geom. Funct. Anal. 16, 2006) for the L ² metric on the group of volume-preserving diffeomorphisms important in hydrodynamics. In particular, our results apply to many other equations of interest in mathematical physics. We also prove an infinite-dimensional Morse Index Theorem, settling a question raised by Arnold and Khesin (Topological methods in hydrodynamics. Springer, New York, 1998) on stable perturbations of flows in hydrodynamics. Finally, we include some applications to the global geometry of diffeomorphism groups.     

Well-posedness for a mean field model of Ginzburg–Landau vortices with opposite degrees

In this paper we analyze the hydrodynamic equations for Ginzburg–Landau vortices as derived by E (Phys. Rev. B. 50(3):1126–1135, 1994). In particular, we are interested in the mean field model describing the evolution of two patches of vortices with equal and opposite degrees. Many results are already available for the case of a single density of vortices with uniform degree. This model does not take into account the vortex annihilation, hence it can also be seen as a particular instance of the signed measures system obtained in Ambrosio et al. (Ann. Inst. H. Poincaré Anal. Non Linéaire 28(2):217–246, 2011) and related to the Chapman et al. (Eur. J. Appl. Math. 7(2):97–111, 1996) formulation. We establish global existence of L ^p solutions, exploiting some optimal transport techniques introduced in this context in Ambrosio and Serfaty (Commun. Pure Appl. Math. LXI(11):1495–1539, 2008). We prove uniqueness for L ^∞ solutions, as expected by analogy with the incompressible Euler equations in fluidodynamics. We also consider the corresponding Dirichlet problem in a bounded domain. Moreover, we show some simple examples of 1-dimensional dynamic.     

<Emphasis Type="Italic">C</Emphasis><Superscript>1+<Emphasis Type="Italic">α</Emphasis></Superscript>-Regularity for Two-Dimensional Almost-Minimal Sets in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We give a new proof and a partial generalization of Jean Taylor’s result (Ann. Math. (2) 103(3), 489–539, 1976) that says that Almgren almost-minimal sets of dimension 2 in ℝ³ are locally C ^1+α -equivalent to minimal cones. The proof is rather elementary, but uses a local separation result proved in Ann. Fac. Sci. Toulouse 18(1), 65–246, 2009 and an extension of Reifenberg’s parameterization theorem (David et al. in Geom. Funct. Anal. 18, 1168–1235, 2008). The key idea is still that if X is the cone over an arc of small Lipschitz graph in the unit sphere, but X is not contained in a disk, we can use the graph of a harmonic function to deform X and substantially diminish its area. The local separation result is used to reduce to unions of cones over arcs of Lipschitz graphs. A good part of the proof extends to minimal sets of dimension 2 in ℝ ⁿ , but in this setting our final regularity result on E may depend on the list of minimal cones obtained as blow-up limits of E at a point.     

Optimal Meshes for Finite Elements of Arbitrary Order

Given a function f defined on a bounded domain Ω⊂ℝ² and a number N>0, we study the properties of the triangulation T_N\mathcal{T}_{N} that minimizes the distance between f and its interpolation on the associated finite element space, over all triangulations of at most N elements. The error is studied in the norm X=L ^p for 1≤p≤∞, and we consider Lagrange finite elements of arbitrary polynomial degree m−1. We establish sharp asymptotic error estimates as N→+∞ when the optimal anisotropic triangulation is used, recovering the results on piecewise linear interpolation (Babenko et al. in East J. Approx. 12(1), 71–101, 2006; Babenko, submitted; Chen et al. in Math. Comput. 76, 179–204, 2007) and improving the results on higher degree interpolation (Cao in SIAM J. Numer. Anal. 45(6), 2368–2391, 2007, SIAM J. Sci. Comput. 29, 756–781, 2007, Math. Comput. 77, 265–286, 2008). These estimates involve invariant polynomials applied to the m-th order derivatives of f. In addition, our analysis also provides practical strategies for designing meshes such that the interpolation error satisfies the optimal estimate up to a fixed multiplicative constant. We partially extend our results to higher dimensions for finite elements on simplicial partitions of a domain Ω⊂ℝ ^d .     

A direct approach to the weighted admissibility of observation operators for bounded analytic semigroups

In this note we adopt the approach in Bonnit et al. (Czechoslov. Math. J. 60(2):527–539, 2010) to give a direct proof of some recent results in Haak and Le Merdy (Houst. J. Math., 2005) and Haak and Kunstmann (SIAM J. Control Optim. 45:2094–2118, 2007) which characterizes the L ^p -admissibility of type α depending on p of unbounded observation operators for bounded analytic semigroups.     

On the Union of Cylinders in Three Dimensions

We show that the combinatorial complexity of the union of n infinite cylinders in ℝ³, having arbitrary radii, is O(n ^2+ε ), for any ε>0; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), who established a nearly-quadratic bound for the restricted case of nearly congruent cylinders. Our result extends, in a significant way, the result of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), in particular, a simple specialization of our analysis to the case of nearly congruent cylinders yields a nearly-quadratic bound on the complexity of the union in that case, thus significantly simplifying the analysis in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000). Finally, we extend our technique to the case of “cigars” of arbitrary radii (that is, Minkowski sums of line-segments and balls) and show that the combinatorial complexity of the union in this case is nearly-quadratic as well. This problem has been studied in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000) for the restricted case where all cigars have (nearly) equal radii. Based on our new approach, the proof follows almost verbatim from the analysis for infinite cylinders and is significantly simpler than the proof presented in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000).     

Spikes for the Gierer–Meinhardt System with Discontinuous Diffusion Coefficients

We rigorously prove results on spiky patterns for the Gierer–Meinhardt system (Kybernetik (Berlin) 12:30–39, 1972) with a jump discontinuity in the diffusion coefficient of the inhibitor. Using numerical computations in combination with a Turing-type instability analysis, this system has been investigated by Benson, Maini, and Sherratt (Math. Comput. Model. 17:29–34, 1993a; Bull. Math. Biol. 55:365–384, 1993b; IMA J. Math. Appl. Med. Biol. 9:197–213, 1992). Firstly, we show the existence of an interior spike located away from the jump discontinuity, deriving a necessary condition for the position of the spike. In particular, we show that the spike is located in one-and-only-one of the two subintervals created by the jump discontinuity of the inhibitor diffusivity. This localization principle for a spike is a new effect which does not occur for homogeneous diffusion coefficients. Further, we show that this interior spike is stable. Secondly, we establish the existence of a spike whose distance from the jump discontinuity is of the same order as its spatial extent. The existence of such a spike near the jump discontinuity is the second new effect presented in this paper. To derive these new effects in a mathematically rigorous way, we use analytical tools like Liapunov–Schmidt reduction and nonlocal eigenvalue problems which have been developed in our previous work (J. Nonlinear Sci. 11:415–458, 2001). Finally, we confirm our results by numerical computations for the dynamical behavior of the system. We observe a moving spike which converges to a stationary spike located in the interior of one of the subintervals or near the jump discontinuity.      

Optimally adapted meshes for finite elements of arbitrary order and W 1, p norms

Given a function f defined on a bounded polygonal domain W ì \mathbbR²{\Omega \subset \mathbb{R}^2} and a number N > 0, we study the properties of the triangulation T_N{\mathcal{T}_N} that minimizes the distance between f and its interpolation on the associated finite element space, over all triangulations of at most N elements. The error is studied in the W ^{1, p} semi-norm for 1 ≤ p < ∞, and we consider Lagrange finite elements of arbitrary polynomial order m − 1. We establish sharp asymptotic error estimates as N → +∞ when the optimal anisotropic triangulation is used. A similar problem has been studied in Babenko et al. (East J Approx. 12(1):71–101, 2006), Cao (J Numer Anal. 45(6):2368–2391, 2007), Chen et al. (Math Comput. 76:179–204, 2007), Cohen (Multiscale, Nonlinear and Adaptive Approximation. Springer, Berlin, 2009), Mirebeau (Constr Approx. 32(2):339–383, 2010), but with the error measured in the L ^p norm. The extension of this analysis to the W ^{1, p} norm is required in order to match more closely the needs of numerical PDE analysis, and it is not straightforward. In particular, the meshes which satisfy the optimal error estimate are characterized by a metric describing the local aspect ratio of each triangle and by a geometric constraint on their maximal angle, a second feature that does not appear for the L ^p error norm. Our analysis also provides with practical strategies for designing meshes such that the interpolation error satisfies the optimal estimate up to a fixed multiplicative constant.     

FFTs on the Rotation Group

We discuss an implementation of an efficient algorithm for the numerical computation of Fourier transforms of bandlimited functions defined on the rotation group SO(3). The implementation is freely available on the web. The algorithm described herein uses O(B ⁴) operations to compute the Fourier coefficients of a function whose Fourier expansion uses only (the O(B ³)) spherical harmonics of degree at most B. This compares very favorably with the direct O(B ⁶) algorithm derived from a basic quadrature rule on O(B ³) sample points. The efficient Fourier transform also makes possible the efficient calculation of convolution over SO(3) which has been used as the analytic engine for some new approaches to searching 3D databases (Funkhouser et al., ACM Trans. Graph. 83–105, [2003]; Kazhdan et al., Eurographics Symposium in Geometry Processing, pp. 167–175, [2003]). Our implementation is based on the “Separation of Variables” technique (see, e.g., Maslen and Rockmore, Proceedings of the DIMACS Workshop on Groups and Computation, pp. 183–237, [1997]). In conjunction with techniques developed for the efficient computation of orthogonal polynomial expansions (Driscoll et al., SIAM J. Comput. 26(4):1066–1099, [1997]), our fast SO(3) algorithm can be improved to give an algorithm of complexity O(B ³log ² B), but at a cost in numerical reliability. Numerical and empirical results are presented establishing the empirical stability of the basic algorithm. Examples of applications are presented as well. First author was supported by NSF ITR award; second author was supported by NSF Grant 0219717 and the Santa Fe Institute.     

Fixed-point-free elements in <Emphasis Type="Italic">p</Emphasis>-groups

In this paper we prove that there exists no function F(m, p) (where the first argument is an integer and the second a prime) such that, if G is a finite permutation p-group with m orbits, each of size at least p ^F(m,p), then G contains a fixed-point-free element. In particular, this gives an answer to a conjecture of Peter Cameron; see [4], [6].     

Rate of Approximation of Regular Convex Bodies by?Convex Algebraic Level Surfaces

We consider the problem of the approximation of regular convex bodies in ℝ ^d by level surfaces of convex algebraic polynomials. Hammer (in Mathematika 10, 67–71, 1963) verified that any convex body in ℝ ^d can be approximated by a level surface of a convex algebraic polynomial. In Jaen J. Approx. 1, 97–109, 2009 and subsequently in J. Approx. Theory 162, 628–637, 2010 a quantitative version of Hammer’s approximation theorem was given by showing that the order of approximation of convex bodies by convex algebraic level surfaces of degree n is \frac1n\frac{1}{n}. Moreover, it was also shown that whenever the convex body is not regular (that is, there exists a point on its boundary at which the convex body possesses two distinct supporting hyperplanes), then \frac1n\frac{1}{n} is essentially the sharp rate of approximation. This leads to the natural question whether this rate of approximation can be improved further when the convex body is regular. In this paper we shall give an affirmative answer to this question. It turns out that for regular convex bodies a o(1/n) rate of convergence holds. In addition, if the body satisfies the condition of C ²-smoothness the rate of approximation is O(\frac1n²)O(\frac{1}{n^{2}}).     

Continuous Shearlet Tight Frames

Based on the shearlet transform we present a general construction of continuous tight frames for L ²(ℝ²) from any sufficiently smooth function with anisotropic moments. This includes for example compactly supported systems, piecewise polynomial systems, or both. From our earlier results in Grohs (Technical report, KAUST, 2009) it follows that these systems enjoy the same desirable approximation properties for directional data as the previous bandlimited and very specific constructions due to Kutyniok and Labate (Trans. Am. Math. Soc. 361:2719–2754, 2009). We also show that the representation formulas we derive are in a sense optimal for the shearlet transform.     

A Note About Critical Percolation on Finite Graphs

In this note we study the geometry of the largest component C₁\mathcal {C}_{1} of critical percolation on a finite graph G which satisfies the finite triangle condition, defined by Borgs et al. (Random Struct. Algorithms 27:137–184, 2005). There it is shown that this component is of size n ^2/3, and here we show that its diameter is n ^1/3 and that the simple random walk takes n steps to mix on it. By Borgs et al. (Ann. Probab. 33:1886–1944, 2005), our results apply to critical percolation on several high-dimensional finite graphs such as the finite torus \mathbbZ_n^d\mathbb{Z}_{n}^{d} (with d large and n→∞) and the Hamming cube {0,1} ⁿ .