We develop Random Batch Methods for interacting particle systems with large number of particles. These methods use small but random batches for particle interactions, thus the computational cost is reduced from $O(N^2)$ per time step to $O(N)$, for a system with $N$ particles with binary interactions. On one hand, these methods are efficient Asymptotic-Preserving schemes for the underlying particle systems, allowing $N$-independent time steps and also capture, in the $N \to \infty$ limit, the solution of the mean field limit which are nonlinear Fokker-Planck equations; on the other hand, the stochastic processes generated by the algorithms can also be regarded as new models for the underlying problems. For one of the methods, we give a particle number independent error estimate under some special interactions. Then, we apply these methods to some representative problems in mathematics, physics, social and data sciences, including the Dyson Brownian motion from random matrix theory, Thomson's problem, distribution of wealth, opinion dynamics and clustering. Numerical results show that the methods can capture both the transient solutions and the global equilibrium in these problems.

The equilibrium metric for minimizing a continuous congested traffic model is the solution of a variational problem involving geodesic distances. The continuous equilibrium metric and its associated variational problem are closely related to the classical discrete Wardrops equilibrium. We propose an adjoint state method to numerically approximate continuous traffic congestion equilibria through the continuous formulation. The method formally derives an adjoint state equation to compute the gradient descent direction so as to minimize a nonlinear functional involving the equilibrium metric and the resulting geodesic distances. The geodesic distance needed for the state equation is computed by solving a factored eikonal equation, and the adjoint state equation is solved by a fast sweeping method. Numerical examples demonstrate that the proposed adjoint state method produces desired equilibrium metrics and

Sparse modeling/approximation of images plays an important role in image restoration. Instead of using a fixed system to sparsely model any input image, a more promising approach is using a system that is adaptive to the input image. A non-convex variational model is proposed in [1] for constructing a tight frame that is optimized for the input image, and an alternating scheme is used to solve the resulting non-convex optimization problem. Although it showed good empirical performance in image denoising, the proposed alternating iteration lacks convergence analysis. This paper aims at providing the convergence analysis of the method proposed in [1]. We first established the sub-sequence convergence property of the iteration scheme proposed in [1], i.e., there exists at least one convergent sub-sequence and any convergent sub-sequence converges to a stationary point of the minimization problem. Moreover, we showed that the original method can be modified to have sequence convergence, i.e., the modified algorithm generates a sequence that converges to a stationary point of the minimization problem.

In this paper, we establish a connection between the recently developed data-driven timefrequency analysis [10, 11] and the classical second order differential equations. The main idea of the data-driven time-frequency analysis is to decompose a multiscale signal into the sparsest collection of Intrinsic Mode Functions (IMFs) over the largest possible dictionary via nonlinear optimization. These IMFs are of the form a(t) cos(θ(t)) where the amplitude a(t) is positive and slowly varying. The non-decreasing phase function θ(t) is determined by the data and in general depends on the signal in a nonlinear fashion. One of the main results of this paper is that we show that each IMF can be associated with a solution of a second order ordinary differential equation of the form x¨ + p(x, t)x˙ + q(x, t) = 0. Further, we propose a localized variational formulation for this problem and develop an effective l1-based optimization method to recover p(x, t) and q(x, t) by looking for a sparse representation of p and q in terms of the polynomial basis. Depending on the form of nonlinearity in p(x, t) and q(x, t), we can define the order of nonlinearity for the associated IMF. This generalizes a concept recently introduced by Prof. N. E. Huang et al. [15]. Numerical examples will be provided to illustrate the robustness and stability of the proposed method for data with or without noise. This manuscript should be considered as a proof of concept.

We begin a systematical study on the effect of numerical viscosities. In this paper we investigate the behavior of shock-capturing methods for slowly moving shocks. It is known that for slowly moving shocks even a first-order scheme, such as the Godunov or Roe type methods, will generate downstream oscillatory wave patterns that cannot be effectively damped by the dissipation of these first-order schemes. The purpose of this paper is to understand the formation and behavior of these downstream patterns. Our study shows that the downstream errors are generated by the unsteady nature of the viscous shock profiles and behave diffusively. The scenario is as follows. When solving the compressible Euler equations by shock capturing methods, the smeared density profile introduces a momentum spike at the shock location if the shock moves slowly. Downstream waves will necessarily emerge in order to balance the momentum mass carried by the spike for the momentum conservation. Although each family of waves decays inl∞andl2while they preserve the same mass, the perturbing nature of the viscous or spike profile is a constant source for the generation of new downstream waves, causing spurious solutions foralltime. Higher order TVD or ENO type interpolations accentuate this problem.