Qiang Niu

This paper studies a unified framework for graph matching problems called the constrained gradient method. Popular algorithms within this framework include graduated assignment (GA), integer projected fixed-point method (IPFP), and doubly stochastic projected fixed-point method (DSPFP). These algorithms differ from the step size parameter and constrained operator. Our contributed adaptive step size parameter can guarantee the underlying algorithms' convergence and enhance their efficiency and accuracy. A preliminary analysis suggests that the optimal step size parameter has a high probability of being 1 in fully connected graph matching. Secondly, we propose a dynamic strategy for softassign, a popular constrained operator, to address its sensitivity concerning nodes' cardinality and risk of overflow. Combining the adaptive step size parameter and the dynamical softassign, we propose a novel graph matching algorithm: the softassign constrained gradient method. Various experiments demonstrate that it is significantly faster than other state-of-the-art algorithms based on the constrained gradient method with improved accuracy.

The hyperbolic problem has a unique entropy solution, which maintains the entropy inequality. As such, people hope that the numerical results should maintain the discrete entropy inequalities accordingly. In view of this, people tend to construct entropy stable (ES) schemes. However, traditional numerical schemes cannot directly maintain discrete entropy inequalities. To address this, we here construct an ES finite difference scheme for the nonlinear hyperbolic systems of conservation laws. The proposed scheme can not only maintain the discrete entropy inequality, but also enjoy high-order accuracy. Firstly, we construct the second-order accurate semi-discrete entropy conservative (EC) schemes and ensure that the schemes meet the entropy identity when an entropy pair is given. Then, the second-order EC schemes are used as a building block to achieve the high-order accurate semi-discrete EC schemes. Thirdly, we add a dissipation term to the above schemes to obtain the high-order ES schemes. The term is based on the Weighted Essentially Non-Oscillatory (WENO) reconstruction. Finally, we integrate the scheme using the third-order Runge–Kutta (RK) approach in time. In the end, plentiful one- and two-dimensional examples are implemented to validate the capability of the scheme. In summary, the current scheme has sharp discontinuity transitions and keeps the genuine high-order accuracy for smooth solutions. Compared to the standard WENO schemes, the current scheme can achieve higher resolution.

Volatility clustering is a common phenomenon in financial time series. Typically, linear models can be used to describe the temporal autocorrelation of the (logarithmic) variance of returns. Considering the difficulty in estimating this model, we construct a Dynamic Bayesian Network, which utilizes the conjugate prior relation of normal-gamma and gamma-gamma, so that its posterior form locally remains unchanged at each node. This makes it possible to find approximate solutions using variational methods quickly. Furthermore, we ensure that the volatility expressed by the model is an independent incremental process after inserting dummy gamma nodes between adjacent time steps. We have found that this model has two advantages: 1) It can be proved that it can express heavier tails than Gaussians, i.e., have positive excess kurtosis, compared to popular linear models. 2) If the variational inference(VI) is used for state estimation, it runs much faster than Monte Carlo(MC) methods since the calculation of the posterior uses only basic arithmetic operations. And its convergence process is deterministic. We tested the model, named Gam-Chain, using recent Crypto, Nasdaq, and Forex records of varying resolutions. The results show that: 1) In the same case of using MC, this model can achieve comparable state estimation results with the regular lognormal chain. 2) In the case of only using VI, this model can obtain accuracy that are slightly worse than MC, but still acceptable in practice; 3) Only using VI, the running time of Gam-Chain, in general case, can be reduced to below 5% of that based on the lognormal chain via MC.

In this paper we consider the classical Kaczmarz algorithm for solving system of linear equations. Based on the geometric relationship between the error vector and rows of the coefficient matrix, we derive the optimal strategy of selecting rows at each step of the algorithm for solving consistent system of linear equations. For solving perturbed system of linear equations, a new upper bound in the convergence rate of the randomized Kaczmarz algorithm is obtained.