Haomin Zhou

Shui-Nee Chow, Xiaojing Ye, Hongyuan Zha et al.

We consider the problem of predicting the time evolution of influence, the expected number of activated nodes, given a set of initially active nodes on a propagation network. To address the significant computational challenges of this problem on large-scale heterogeneous networks, we establish a system of differential equations governing the dynamics of probability mass functions on the state graph where the nodes each lumps a number of activation states of the network, which can be considered as an analogue to the Fokker-Planck equation in continuous space. We provides several methods to estimate the system parameters which depend on the identities of the initially active nodes, network topology, and activation rates etc. The influence is then estimated by the solution of such a system of differential equations. This approach gives rise to a class of novel and scalable algorithms that work effectively for large-scale and dense networks. Numerical results are provided to show the very promising performance in terms of prediction accuracy and computational efficiency of this approach.

Haoran Sun, Hanjun Dai, Bo Dai et al.

It is known that gradient-based MCMC samplers for continuous spaces, such as Langevin Monte Carlo (LMC), can be derived as particle versions of a gradient flow that minimizes KL divergence on a Wasserstein manifold. The superior efficiency of such samplers has motivated several recent attempts to generalize LMC to discrete spaces. However, a fully principled extension of Langevin dynamics to discrete spaces has yet to be achieved, due to the lack of well-defined gradients in the sample space. In this work, we show how the Wasserstein gradient flow can be generalized naturally to discrete spaces. Given the proposed formulation, we demonstrate how a discrete analogue of Langevin dynamics can subsequently be developed. With this new understanding, we reveal how recent gradient-based samplers in discrete spaces can be obtained as special cases by choosing particular discretizations. More importantly, the framework also allows for the derivation of novel algorithms, one of which, \textit{Discrete Langevin Monte Carlo} (DLMC), is obtained by a factorized estimate of the transition matrix. The DLMC method admits a convenient parallel implementation and time-uniform sampling that achieves larger jump distances. We demonstrate the advantages of DLMC on various binary and categorical distributions.

Antonio Cicone, Haomin Zhou

Real life signals are in general non--stationary and non--linear. The development of methods able to extract their hidden features in a fast and reliable way is of high importance in many research fields. In this work we tackle the problem of further analyzing the convergence of the Iterative Filtering method both in a continuous and a discrete setting in order to provide a comprehensive analysis of its behavior. Based on these results we provide new ideas for efficient implementations of Iterative Filtering algorithm which are based on Fast Fourier Transform (FFT), and the reduction of the original iterative algorithm to a direct method.

Shui-Nee Chow, Luca Dieci, Wuchen Li et al.

We propose a new semi-discretization scheme to approximate nonlinear Fokker-Planck equations, by exploiting the gradient flow structures with respect to the 2-Wasserstein metric. We discretize the underlying state by a finite graph and define a discrete 2-Wasserstein metric. Based on such metric, we introduce a dynamical system, which is a gradient flow of the discrete free energy. We prove that the new scheme maintains dissipativity of the free energy and converges to a discrete Gibbs measure at exponential (dissipation) rate. We exhibit these properties on several numerical examples.

Bjorn Engquist, Christina Frederick, Quyen Huynh et al.

We present a multiscale approach for identifying features in ocean beds by solving inverse problems in high frequency seafloor acoustics. The setting is based on Sound Navigation And Ranging (SONAR) imaging used in scientific, commercial, and military applications. The forward model incorporates multiscale simulations, by coupling Helmholtz equations and geometrical optics for a wide range of spatial scales in the seafloor geometry. This allows for detailed recovery of seafloor parameters including material type. Simulated backscattered data is generated using numerical microlocal analysis techniques. In order to lower the computational cost of the large-scale simulations in the inversion process, we take advantage of a pre-computed library of representative acoustic responses from various seafloor parameterizations.

Yaohua Zang, Gang Bao, Xiaojing Ye et al.

We propose a novel problem formulation of continuous-time information propagation on heterogenous networks based on jump stochastic differential equations (SDE). The structure of the network and activation rates between nodes are naturally taken into account in the SDE system. This new formulation allows for efficient and stable algorithm for many challenging information propagation problems, including estimations of individual activation probability and influence level, by solving the SDE numerically. To this end, we develop an efficient numerical algorithm incorporating variance reduction; furthermore, we provide theoretical bounds for its sample complexity. Moreover, we show that the proposed jump SDE approach can be applied to a much larger class of critical information propagation problems with more complicated settings. Numerical experiments on a variety of synthetic and real-world propagation networks show that the proposed method is more accurate and efficient compared with the state-of-the-art methods.

Shijun Zhang, Hongkai Zhao, Yimin Zhong et al.

In this work, we present a comprehensive study combining mathematical and computational analysis to explain why a two-layer neural network struggles to handle high frequencies in both approximation and learning, especially when machine precision, numerical noise, and computational cost are significant factors in practice. Specifically, we investigate the following fundamental computational issues: (1) the minimal numerical error achievable under finite precision, (2) the computational cost required to attain a given accuracy, and (3) the stability of the method with respect to perturbations. The core of our analysis lies in the conditioning of the representation and its learning dynamics. Explicit answers to these questions are provided, along with supporting numerical evidence.

Nathan Gaby, Xiaojing Ye, Haomin Zhou

We develop a novel computational framework to approximate solution operators of evolution partial differential equations (PDEs). By employing a general nonlinear reduced-order model, such as a deep neural network, to approximate the solution of a given PDE, we realize that the evolution of the model parameter is a control problem in the parameter space. Based on this observation, we propose to approximate the solution operator of the PDE by learning the control vector field in the parameter space. From any initial value, this control field can steer the parameter to generate a trajectory such that the corresponding reduced-order model solves the PDE. This allows for substantially reduced computational cost to solve the evolution PDE with arbitrary initial conditions. We also develop comprehensive error analysis for the proposed method when solving a large class of semilinear parabolic PDEs. Numerical experiments on different high-dimensional evolution PDEs with various initial conditions demonstrate the promising results of the proposed method.

Feng Zhou, Antonio Cicone, Haomin Zhou

The decomposition of non-stationary signals is an important and challenging task in the field of signal time-frequency analysis. In the recent two decades, many signal decomposition methods led by the empirical mode decomposition, which was pioneered by Huang et al. in 1998, have been proposed by different research groups. However, they still have some limitations. For example, they are generally prone to boundary and mode mixing effects and are not very robust to noise. Inspired by the successful applications of deep learning in fields like image processing and natural language processing, and given the lack in the literature of works in which deep learning techniques are used directly to decompose non-stationary signals into simple oscillatory components, we use the convolutional neural network, residual structure and nonlinear activation function to compute in an innovative way the local average of the signal, and study a new non-stationary signal decomposition method under the framework of deep learning. We discuss the training process of the proposed model and study the convergence analysis of the learning algorithm. In the experiments, we evaluate the performance of the proposed model from two points of view: the calculation of the local average and the signal decomposition. Furthermore, we study the mode mixing, noise interference, and orthogonality properties of the decomposed components produced by the proposed method. All results show that the proposed model allows for better handling boundary effect, mode mixing effect, robustness, and the orthogonality of the decomposed components than existing methods.

Luca Dieci, Manuela Manetta, Haomin Zhou

In this work, we present a method to explore the landscape of a smooth potential in the search of global minimizers,combining a double-descent technique and a basin-escaping technique based on intermittent colored diffusion. Numerical results illustrate the performance of the method.

Feng Zhou, Antonio Cicone, Haomin Zhou

Time-frequency analysis is an important and challenging task in many applications. Fourier and wavelet analysis are two classic methods that have achieved remarkable success in many fields. However, they also exhibit limitations when applied to nonlinear and non-stationary signals. To address this challenge, a series of nonlinear and adaptive methods, pioneered by the empirical mode decomposition method, have been proposed. The goal of these methods is to decompose a non-stationary signal into quasi-stationary components that enhance the clarity of features during time-frequency analysis. Recently, inspired by deep learning, we proposed a novel method called iterative residual convolutional neural network (IRCNN). IRCNN not only achieves more stable decomposition than existing methods but also handles batch processing of large-scale signals with low computational cost. Moreover, deep learning provides a unique perspective for non-stationary signal decomposition. In this study, we aim to further improve IRCNN with the help of several nimble techniques from deep learning and optimization to ameliorate the method and overcome some of the limitations of this technique.

Qujiangxue Chen, Jianbo Cui, Luca Dieci et al.

In this paper, we study dynamical optimal transport on a connected graph from the perspective of the Benamou-Brenier formulation, where densities are assigned to vertices and velocities to edges. However, directly using Newton's method on the resulting nonlinear systems encounters two potential difficulties: (i) if the graph contains cycles, edge variables are not unique, and (ii) there is no guarantee that the density variables remain positive. To address these challenges, we introduce a finite-difference-type Newton method that eliminates cycle-induced redundancies through a spanning-tree gauge, resulting in a reduced set of independent variables and a well-posed, sparse linear system. For the lattice graph arising from the continuous optimal transport problem, density positivity can also be guaranteed by using an upwind discretization subject to a CFL-type condition. We further demonstrate the versatility of the proposed scheme by applying it to a range of problems, including optimal transport on lattices and random graphs, inverse optimal transport problems, and social network analysis.

Xiangxiong Zhang, Haomin Zhou

We compute the ground state $u$ of the Gross--Pitaevskii equation (GPE) via Wasserstein gradient descent in diffeomorphism space. We represent the density $ρ=u^2$ as the push-forward of a fixed reference measure through a parameterized transport map $T_θ$, realized by a boundary-preserving Neural ODE. The Wasserstein gradient flow on probability densities then lifts to natural gradient descent in the finite-dimensional parameter space, with metric tensor given by the pullback of the Wasserstein metric. The method is entirely mesh-free and preserves the unit-mass constraint without normalization. We present numerical experiments in dimensions $d=1,2,3$ and demonstrate that the parameterized Wasserstein gradient flow (PWGF) output can be used to initialize the $H^1$ Sobolev gradient flow, reducing the initial energy gap by a factor of $7$ in 2D and $4.5$ in 3D compared to trivial initial conditions.

Yaxin Feng, Yang Xiang, Haomin Zhou

In this paper, we propose an initial value fomulation of the discrete mean field games on finite graphs (Graph MFG), and design a neural network based approach to solve it. Graph MFG describes infinite, non-cooperative and interactive homogeneous agents move on node states through the edges to optimize their own goals. Nash Equilibrium of the Graph MFG is characterized by a coupled ordinary differential equations (ODE) system, including the discrete forward continuity equation and the discrete backward Hamilton-Jacobi equation. In this paper, we mainly focus on the potential mean field games (Potential MFG) on finite graphs, which has an infinite-dimensional constrained optimization structure. We reformulate Potential MFG as an initial value finite-dimentional optimization problem with dynamics constrains, names Graph MFG-IV. Specifically, the initial condition of the Hamilton-Jacobi equation is regarded as the unique variable, constrained by the coupled Hamilton-Jacobi and continuity equation system as the ODE integrator. This formulation is a reduced-order model, which avoids time-discretization of the infinite-dimensional path and has a much smaller searching space than the general path-wise problem setting. We design a neural network-based approach to solve the Graph MFG-IV problem.

Shijun Zhang, Hongkai Zhao, Yimin Zhong et al.

The architecture of a neural network and the selection of its activation function are both fundamental to its performance. Equally vital is ensuring these two elements are well-matched, as their alignment is key to achieving effective representation and learning. In this paper, we introduce the Fourier Multi-Component and Multi-Layer Neural Network (FMMNN), a novel model that creates a strong synergy between them. We demonstrate that FMMNNs are highly effective and flexible in modeling high-frequency components. Our theoretical results demonstrate that FMMNNs have exponential expressive power for function approximation. We also analyze the optimization landscape of FMMNNs and find it to be much more favorable than that of standard fully connected neural networks, especially when dealing with high-frequency features. In addition, we propose a scaled random initialization method for the first layer's weights in FMMNNs, which significantly speeds up training and enhances overall performance. Extensive numerical experiments support our theoretical insights, showing that FMMNNs consistently outperform traditional approaches in accuracy and efficiency across various tasks.

Shijun Zhang, Hongkai Zhao, Yimin Zhong et al.

In this work, we propose a balanced multi-component and multi-layer neural network (MMNN) structure to accurately and efficiently approximate functions with complex features, in terms of both degrees of freedom and computational cost. The main idea is inspired by a multi-component approach, in which each component can be effectively approximated by a single-layer network, combined with a multi-layer decomposition strategy to capture the complexity of the target function. Although MMNNs can be viewed as a simple modification of fully connected neural networks (FCNNs) or multi-layer perceptrons (MLPs) by introducing balanced multi-component structures, they achieve a significant reduction in training parameters, a much more efficient training process, and improved accuracy compared to FCNNs or MLPs. Extensive numerical experiments demonstrate the effectiveness of MMNNs in approximating highly oscillatory functions and their ability to automatically adapt to localized features.

Jiaojiao Fan, Shu Liu, Shaojun Ma et al.

Monge map refers to the optimal transport map between two probability distributions and provides a principled approach to transform one distribution to another. Neural network based optimal transport map solver has gained great attention in recent years. Along this line, we present a scalable algorithm for computing the neural Monge map between two probability distributions. Our algorithm is based on a weak form of the optimal transport problem, thus it only requires samples from the marginals instead of their analytic expressions, and can accommodate optimal transport between two distributions with different dimensions. Our algorithm is suitable for general cost functions, compared with other existing methods for estimating Monge maps using samples, which are usually for quadratic costs. The performance of our algorithms is demonstrated through a series of experiments with both synthetic and realistic data, including text-to-image generation and image inpainting tasks.

Shaojun Ma, Haomin Zhou, Hongyuan Zha

We propose a novel mean field games (MFGs) based GAN(generative adversarial network) framework. To be specific, we utilize the Hopf formula in density space to rewrite MFGs as a primal-dual problem so that we are able to train the model via neural networks and samples. Our model is flexible due to the freedom of choosing various functionals within the Hopf formula. Moreover, our formulation mathematically avoids Lipschitz-1 constraint. The correctness and efficiency of our method are validated through several experiments.

Shu Liu, Shaojun Ma, Yongxin Chen et al.

We propose a new formulation and learning strategy for computing the Wasserstein geodesic between two probability distributions in high dimensions. By applying the method of Lagrange multipliers to the dynamic formulation of the optimal transport (OT) problem, we derive a minimax problem whose saddle point is the Wasserstein geodesic. We then parametrize the functions by deep neural networks and design a sample based bidirectional learning algorithm for training. The trained networks enable sampling from the Wasserstein geodesic. As by-products, the algorithm also computes the Wasserstein distance and OT map between the marginal distributions. We demonstrate the performance of our algorithms through a series of experiments with both synthetic and realistic data.

Gang Bao, Xiaojing Ye, Yaohua Zang et al.

We consider a weak adversarial network approach to numerically solve a class of inverse problems, including electrical impedance tomography and dynamic electrical impedance tomography problems. We leverage the weak formulation of PDE in the given inverse problem, and parameterize the solution and the test function as deep neural networks. The weak formulation and the boundary conditions induce a minimax problem of a saddle function of the network parameters. As the parameters are alternatively updated, the network gradually approximates the solution of the inverse problem. We provide theoretical justifications on the convergence of the proposed algorithm. Our method is completely mesh-free without any spatial discretization, and is particularly suitable for problems with high dimensionality and low regularity on solutions. Numerical experiments on a variety of test inverse problems demonstrate the promising accuracy and efficiency of our approach.

Shaojun Ma, Haodong Sun, Xiaojing Ye et al.

Inverse optimal transport (OT) refers to the problem of learning the cost function for OT from observed transport plan or its samples. In this paper, we derive an unconstrained convex optimization formulation of the inverse OT problem, which can be further augmented by any customizable regularization. We provide a comprehensive characterization of the properties of inverse OT, including uniqueness of solutions. We also develop two numerical algorithms, one is a fast matrix scaling method based on the Sinkhorn-Knopp algorithm for discrete OT, and the other one is a learning based algorithm that parameterizes the cost function as a deep neural network for continuous OT. The novel framework proposed in the work avoids repeatedly solving a forward OT in each iteration which has been a thorny computational bottleneck for the bi-level optimization in existing inverse OT approaches. Numerical results demonstrate promising efficiency and accuracy advantages of the proposed algorithms over existing state-of-the-art methods.

Shaojun Ma, Shu Liu, Hongyuan Zha et al.

Learning nonlinear dynamics from aggregate data is a challenging problem because the full trajectory of each individual is not available, namely, the individual observed at one time may not be observed at the next time point, or the identity of individual is unavailable. This is in sharp contrast to learning dynamics with full trajectory data, on which the majority of existing methods are based. We propose a novel method using the weak form of Fokker Planck Equation (FPE) -- a partial differential equation -- to describe the density evolution of data in a sampled form, which is then combined with Wasserstein generative adversarial network (WGAN) in the training process. In such a sample-based framework we are able to learn the nonlinear dynamics from aggregate data without explicitly solving the partial differential equation (PDE) FPE. We demonstrate our approach in the context of a series of synthetic and real-world data sets.

Haoyan Zhai, Magnus Egerstedt, Haomin Zhou

This paper introduces a graph-based, potential-guided method for path planning problems in unknown environments, where obstacles are unknown until the robots are in close proximity to the obstacle locations. Inspired by optimal transport theory, the proposed method generates a graph connecting the initial and target configurations, and then finds a path over the graph using the available environmental information. The graph and path are updated iteratively when newly encountered obstacle information becomes available. The resulting method is a deterministic procedure proven to be complete, i.e., it is guaranteed to find a feasible path, when one exists, in a finite number of iterations. The method is scalable to high-dimensional problems. In addition, our method does not search the entire domain for the path, instead, the algorithm only explores a sub-region that can be described by the evolution of the Fokker-Planck equation. We demonstrate the performance of our algorithm via several numerical examples with different environments and dimensions, including high-dimensional cases.

Ruilin Li, Xiaojing Ye, Haomin Zhou et al.

We propose a unified data-driven framework based on inverse optimal transport that can learn adaptive, nonlinear interaction cost function from noisy and incomplete empirical matching matrix and predict new matching in various matching contexts. We emphasize that the discrete optimal transport plays the role of a variational principle which gives rise to an optimization-based framework for modeling the observed empirical matching data. Our formulation leads to a non-convex optimization problem which can be solved efficiently by an alternating optimization method. A key novel aspect of our formulation is the incorporation of marginal relaxation via regularized Wasserstein distance, significantly improving the robustness of the method in the face of noisy or missing empirical matching data. Our model falls into the category of prescriptive models, which not only predict potential future matching, but is also able to explain what leads to empirical matching and quantifies the impact of changes in matching factors. The proposed approach has wide applicability including predicting matching in online dating, labor market, college application and crowdsourcing. We back up our claims with numerical experiments on both synthetic data and real world data sets.

Antonio Cicone, Jingfang Liu, Haomin Zhou

Chemicals released in the air can be extremely dangerous for human beings and the environment. Hyperspectral images can be used to identify chemical plumes, however the task can be extremely challenging. Assuming we know a priori that some chemical plume, with a known frequency spectrum, has been photographed using a hyperspectral sensor, we can use standard techniques like the so called matched filter or adaptive cosine estimator, plus a properly chosen threshold value, to identify the position of the chemical plume. However, due to noise and sensors fault, the accurate identification of chemical pixels is not easy even in this apparently simple situation. In this paper we present a post-processing tool that, in a completely adaptive and data driven fashion, allows to improve the performance of any classification methods in identifying the boundaries of a plume. This is done using the Multidimensional Iterative Filtering (MIF) algorithm (arXiv:1411.6051, arXiv:1507.07173), which is a non-stationary signal decomposition method like the pioneering Empirical Mode Decomposition (EMD) method. Moreover, based on the MIF technique, we propose also a pre-processing method that allows to decorrelate and mean-center a hyperspectral dataset. The Cosine Similarity measure, which often fails in practice, appears to become a successful and outperforming classifier when equipped with such pre-processing method. We show some examples of the proposed methods when applied to real life problems.

Antonio Cicone, Jingfang Liu, Haomin Zhou

Time-frequency analysis for non-linear and non-stationary signals is extraordinarily challenging. To capture features in these signals, it is necessary for the analysis methods to be local, adaptive and stable. In recent years, decomposition based analysis methods, such as the empirical mode decomposition (EMD) technique pioneered by Huang et al., were developed by different research groups. These methods decompose a signal into a finite number of components on which the time-frequency analysis can be applied more effectively. In this paper we consider the iterative filters (IFs) approach as an alternative to EMD. We provide sufficient conditions on the filters that ensure the convergence of IFs applied to any $L^2$ signal. Then we propose a new technique, the Adaptive Local Iterative Filtering (ALIF) method, which uses the IFs strategy together with an adaptive and data driven filter length selection to achieve the decomposition. Furthermore we design smooth filters with compact support from solutions of Fokker-Planck equations (FP filters) that can be used within both IFs and ALIF methods. These filters fulfill the derived sufficient conditions for the convergence of the IFs algorithm. Numerical examples are given to demonstrate the performance and stability of IFs and ALIF techniques with FP filters. In addition, in order to have a complete and truly local analysis toolbox for non-linear and non-stationary signals, we propose a new definition for the instantaneous frequency which depends exclusively on local properties of a signal.

Chunmei Wang, Haomin Zhou

In this paper, a new and efficient numerical algorithm by using weak Galerkin (WG) finite element methods is proposed for a type of fourth order problem arising from fluorescence tomography(FT). Fluorescence tomography is an emerging, in vivo non-invasive 3-D imaging technique which reconstructs images that characterize the distribution of molecules that are tagged by fluorophores. Weak second order elliptic operator and its discrete version are introduced for a class of discontinuous functions defined on a finite element partition of the domain consisting of general polygons or polyhedra. An error estimate of optimal order is derived in an $H^2$-equivalent norm for the WG finite element solutions. Error estimates in the usual $L^2$ norm are established, yielding optimal order of convergence for all the WG finite element algorithms except the one corresponding to the lowest order (i.e., piecewise quadratic elements). Some numerical experiments are presented to illustrate the efficiency and accuracy of the numerical scheme.

Antonio Cicone, Haomin Zhou

Iterative Filtering (IF) is an alternative technique to the Empirical Mode Decomposition (EMD) algorithm for the decomposition of non-stationary and non-linear signals. Recently in [1] IF has been proved to be convergent for any $L^2$ signal and its stability has been also showed through examples. Furthermore in [1] the so called Fokker-Planck (FP) filters have been introduced. They are smooth at every point and have compact supports. Based on those results, in this paper we introduce the Multidimensional Iterative Filtering (MIF) technique for the decomposition and time-frequency analysis of non-stationary high-dimensional signals. And we present the extension of FP filters to higher dimensions. We illustrate the promising performance of MIF algorithm, equipped with high-dimensional FP filters, when applied to the decomposition of 2D signals. [1] A. Cicone, J. Liu, and H. Zhou, Adaptive local iterative filtering for signal decomposition and instantaneous frequency analysis, arXiv:1411.6051, 2014.