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.

In this paper, we analyze the uniqueness of the sparse time frequency decomposition and investigate the eciency of the nonlinear matching pursuit method. Under the assumption of scale separation, we show that the sparse time frequency decomposition is unique up to an error that is determined by the scale separation property of the signal. We further show that the unique decomposition can be obtained approximately by the sparse time frequency decomposition using nonlinear matching pursuit.

The problem is concerned about computing virtual coordinates for greedy routing in a wireless ad hoc network. Consider a set of wireless nodes S densely deployed inside a geometric domain R2. Nodes within communication range can directly communicate with each other. We ask whether one can compute a set of virtual coordinates for S such that greedy routing has guaranteed delivery. In particular, each node forwards the message to the neighbor whose distance to the destination, computed under the virtual coordinates and some metric function d, is the smallest. If such a neighbor can always be found, greedy routing successfully delivers the message to the destination. The problem can be phrased as finding a greedy embedding of S in some geometric space, such that greedy routing always succeeds. In the setting of this entry, we assume that the nodes are a dense sample of the domain such that

In this paper, we develop an effective and robust adaptive time-frequency analysis method for signals with intra-wave frequency modulation. To handle this kind of signals effectively, we generalize our data-driven time-frequency analysis by using a shape function to describe the intra-wave frequency modulation. The idea of using a shape function in time-frequency analysis was first proposed by Wu (Wu 2013 Appl. Comput. Harmon. Anal. 35, 181–199. (doi:10.1016/j.acha.2012.08.008)). A shape function could be any smooth 2π-periodic function. Based on this model, we propose to solve an optimization problem to extract the shape function. By exploring the fact that the shape function is a periodic function with respect to its phase function, we can identify certain low-rank structure of the signal. This low-rank structure enables us to extract the shape function from the signal. Once the shape function is obtained, the instantaneous frequency with intra-wave modulation can be recovered from the shape function. We demonstrate the robustness and efficiency of our method by applying it to several synthetic and real signals. One important observation is that this approach is very stable to noise perturbation. By using the shape function approach, we can capture the intrawave frequency modulation very well even for noisepolluted signals. In comparison, existing methods such as empirical mode decomposition/ensemble empiricalmode decomposition seem to have difficulty in capturing the intra-wave modulation when the signal is polluted by noise.

For the steady-state solution of a differential equation from a one-dimensional multistate model in transport theory, we shall derive and study a nonsymmetric algebraic Riccati equation <i>B</i> <i>XF</i> <i>F</i>⁺<i>X</i> + <i>XB</i>⁺<i>X</i> = 0, where <i>F</i> (<i>I</i> <i>F</i>)<i>D</i> and <i>B</i> <i>BD</i> with positive diagonal matrices <i>D</i> and possibly low-ranked matrices <i>F</i> and <i>B</i>. We prove the existence of the minimal positive solution <i>X</i>^* under a set of physically reasonable assumptions and study its numerical computation by fixed-point iteration, Newtons method and the doubling algorithm. We shall also study several special cases. For example when <i>B</i> and <i>F</i> are low ranked then X*=(i=14UiViT) with low-ranked <i>U_i</i> and <i>V_i</i> that can be computed using more efficient iterative processes. Numerical examples will be given to illustrate our theoretical results.