Three Mach-uniform algorithms

We focus on the construction of Mach-uniform algorithms. The basic idea is to remove the severe time step restrictions for low speed flows, by treating the acoustic terms implicitly. The way to solve the obtained semi-implicit system can be chosen. Three different solution techniques are presented, varying between a fully coupled algorithm and a fully segregated pressure correction algorithm. We show that the number of time steps to reach steady state is comparable for the fully coupled as well as the fully segregated method. Therefore, the more segregation is introduced, the more efficient the calculation can be done.     

Wavelet improvement in turning point detection using a hidden Markov model: from the aspects of cyclical identification and outlier correction

The hidden Markov model (HMM) has been widely used in regime classification and turning point detection for econometric series after the decisive paper by Hamilton (Econometrica 57(2):357–384, 1989). The present paper will show that when using HMM to detect the turning point in cyclical series, the accuracy of the detection will be influenced when the data are exposed to high volatilities or combine multiple types of cycles that have different frequency bands. Moreover, outliers will be frequently misidentified as turning points. The present paper shows that these issues can be resolved by wavelet multi-resolution analysis based methods. By providing both frequency and time resolutions, the wavelet power spectrum can identify the process dynamics at various resolution levels. We apply a Monte Carlo experiment to show that the detection accuracy of HMMs is highly improved when combined with the wavelet approach. Further simulations demonstrate the excellent accuracy of this improved HMM method relative to another two change point detection algorithms. Two empirical examples illustrate how the wavelet method can be applied to improve turning point detection in practice.     

Nonparametric adaptive detection in fading channels based on sequential Monte Carlo and Bayesian model averaging

Recently, a Bayesian receiver for blind detection in fading channels has been proposed by Chen, Wang and Liu (200,IEEE Trans. Inform. Theory,46, 2079–2094), based on the sequential Monte Carlo methodology. That work is built on a parametric modelling of the fading process in the form of a state-space model, and assumes the knowledge of the second-order statistics of the fading channel. In this paper, we develop a nonparametric approach to the problem of blind detection in fading channels, without assuming any knowledge of the channel statistics. The basic idea is to decompose the fading process using a wavelet basis, and to use the sequential Monte Carlo technique to track both the wavelet coefficients and the transmitted symbols. Moreover, the algorithm is adaptive to time varying speed/smoothness in the fading process and the uncertainty on the number of wavelet coefficients (shrinkage order) needed. Simulation results are provided to demonstrate the excellent performance of the proposed blind adaptive receivers. This work was supported in part by the U.S. National Science Foundation (NSF) under grants CCR-9875314, CCR-9980599, DMS-9982846, DMS-0073651 and DMS-0073601.     

经济时间序列的连续参数小波网络预测模型

本文利用连续小波变换方法,给出一种连续参数小波网络。网络参数的学习采用一种类似神经网络的后向传播学习算法的随机梯度算法。另外,提出了一种借助小波分析理论指导网络参数赋初值的方法。进一步,通过对中国进出口贸易额时间序列预测建模的研究和仿真预测,提出了用连续参数小波网络建立经济时间序列预测模型的一般步骤和方法。预测结果表明,此模型具有较好的泛化、学习能力,可以有效地在数值上逼近时间序列难以定量描述的相互关系,所以利用连续参数小波网络建立的时间序列预测模型有较高的预测精度。     

Average-optimal string matching

The exact string matching problem is to find the occurrences of a pattern of length m from a text of length n symbols. We develop a novel and unorthodox filtering technique for this problem. Our method is based on transforming the problem into multiple matching of carefully chosen pattern subsequences. While this is seemingly more difficult than the original problem, we show that the idea leads to very simple algorithms that are optimal on average. We then show how our basic method can be used to solve multiple string matching as well as several approximate matching problems in average optimal time. The general method can be applied to many existing string matching algorithms. Our experimental results show that the algorithms perform very well in practice.     

网络聚类算法及其生物信息学应用

介绍一些网络聚类算法及其基本原理,简述了其在生物信息学的应用。本文不是一个网络聚类算法的全面综述,只介绍这些网络聚类算法的基本思路,体会其数学建模的基本思想。     

Operators of mutation and crossover in a genetic algorithm for construction of axiomatic systems

In this paper, the problem of automated recognition of anomalies in the behavior of complicated dynamical systems is solved by means of analyzing trajectories obtained from sensors surrounding the system. A specific feature of the problem consists in the fact that, depending on the individual properties of the system and conditions of its operation, trajectories that contain anomalies may significantly differ from each other in amplitude and length. The algorithm employed here for solving the problem of recognition of anomalies in the behavior of the system under investigation is based on the idea of applying the algebraic approach to the labeling of time series. This algorithm can be adjusted to peculiarities of a particular dynamical system; such adjustment can be performed with the help of an algorithm belonging to the class of genetic algorithms.     

A real time algorithm for the location search of discontinuous conductivities with one measurement

We consider an inverse problem for finding the anomaly of discontinuous electrical conductivity by one current‐voltage observation. We develop a real time algorithm for determining the location of the anomaly. This new idea is based on the observation of the pattern of a simple weighted combination of the input current and the output voltage. Combined with the size estimation result, this algorithm gives a good initial guess for Newton‐type schemes. We give the rigorous proof for the location search algorithm. Both the mathematical analysis and its numerical implementation indicate our location search algorithm is very fast, stable and efficient. © 2001 John Wiley & Sons, Inc.     

QRS complex detection based on multi wavelet packet decomposition

We present in this paper a wavelet packet based QRS complex detection algorithm. Our proposed algorithm consists of a particular combination of two vectors obtained by applying a designed routine of QRS detection process using ‘haar’ and ‘db10’ wavelet functions respectively. The QRS complex detection routine is based on the histogram approach where our key idea was to search for the node with highest number of histogram coefficients, at center, which we assume that they are related to the iso-electric baseline whereas the remaining least number coefficients reflect the R waves peaks. Following a classical approach based of a calculated fixed threshold, the possible QRS complexes will be determined. The QRS detection complex algorithm has been applied to the whole MIT-BIH arrhythmia Database to assess its robustness. The algorithm reported a global sensitivity of 98.68%, positive predictive value of 97.24% and a percentage error of 04.12%. Eventhough, the obtained global results are not as excellent as expected, we have demonstrate that our designed QRS detection algorithm performs good on a partial selected high percentage of the whole database, e.g., the partial results, obtained when applying the algorithm on 85.01% of the whole MIT-BIH arrhythmia Database, are 99.14% of sensitivity, 98.94% of positive predictive value and 01.92% of percentage error.     

Efficient computation of Fourier transforms on compact groups

This article genralizes the fast Fourier transform algorithm to the computation of Fourier transforms on compact Lie groups. The basic technique uses factorization of group elements and Gel'fand-Tsetlin bases to simplify the computations, and may be extended to treat the computation of Fourier transforms of finitely supported distributions on the group. Similar transforms may be defined on homogeneous spaces; in that case we show how special function properties of spherical functions lead to more efficient algorithms. These results may all be viewed as generalizations of the fast Fourier transform algorithms on the circle, and of recent results about Fourier transforms on finite groups. Acknowledgements and Notes. This paper was written while the author was supported by the Max-Planck-Institut für Mathematik, Bonn, Germany.     

一种新城市气温模式分类的聚类算法

城市气温是对城市气候特性评价的一个重要指标.提出核概率聚类算法并将其应用于城市气温的模式分类中,以此寻找城市发展上的共同点.该算法在概率聚类算法上引入了核学习方法的思想,能够很好地处理噪音和孤立点,实现更为准确的聚类.实验结果表明,与相关聚类算法相比,核概率聚类算法聚类效果好,且算法能够很快地收敛.     

NEWTON-REGULARIZED METHOD BASED ON A BASIC FUNCTION FOR SOLVING THE INVERSE PROBLEM OF CONVECTION-DIFFUSION EQUATIONS

In this paper, a new iteration algorithm to solve the coefficient inverse problem is described by using a "basic function" which is specially defined and the idea of regularization. The method is simple and clear.The main advantage of the algorithm is that its computing cost is less than other current algorithms, such as PST and Purlerbalion Methods. Since it has uniform scheme, on the other hand, the method can be easily exleded to other kinds of inverse problems of different leal equations, multidimensional inverse problem and multiparameler inverse problems, etc.     

ATM交易状态特征分析与异常检测

考虑ATM交易过程当中产生的一系列参数,如交易量、交易成功率和响应时间等,对交易状态特征进行分析并建立了异常检测模型。针对成功率与响应时间2个参数,利用聚类算法将数据点划分为正常点、疑似异常点、异常点3大类。对于疑似的异常点,再根据其时间序列周围点的分布情况确定是否确实为异常点;对于交易量参数,首先通过LOF局部离群因子对离群点进行识别,再结合交易量随时间的移动均线及标准差加以辅助筛选,得到初步的疑似异常点,进一步通过与不同天同一时刻数据进行比较,最终确定是否为异常点。根据上述模型,本文将异常情况划分为3个预警等级,并对重大故障情况进行预测。     

Nonlinear Methods of Approximation

Abstract. Our main interest in this paper is nonlinear approximation. The basic idea behind nonlinear approximation is that the elements used in the approximation do not come from a fixed linear space but are allowed to depend on the function being approximated. While the scope of this paper is mostly theoretical, we should note that this form of approximation appears in many numerical applications such as adaptive PDE solvers, compression of images and signals, statistical classification, and so on. The standard problem in this regard is the problem of m -term approximation where one fixes a basis and looks to approximate a target function by a linear combination of m terms of the basis. When the basis is a wavelet basis or a basis of other waveforms, then this type of approximation is the starting point for compression algorithms. We are interested in the quantitative aspects of this type of approximation. Namely, we want to understand the properties (usually smoothness) of the function which govern its rate of approximation in some given norm (or metric). We are also interested in stable algorithms for finding good or near best approximations using m terms. Some of our earlier work has introduced and analyzed such algorithms. More recently, there has emerged another more complicated form of nonlinear approximation which we call highly nonlinear approximation. It takes many forms but has the basic ingredient that a basis is replaced by a larger system of functions that is usually redundant. Some types of approximation that fall into this general category are mathematical frames, adaptive pursuit (or greedy algorithms), and adaptive basis selection. Redundancy on the one hand offers much promise for greater efficiency in terms of approximation rate, but on the other hand gives rise to highly nontrivial theoretical and practical problems. With this motivation, our recent work and the current activity focuses on nonlinear approximation both in the classical form of m -term approximation (where several important problems remain unsolved) and in the form of highly nonlinear approximation where a theory is only now emerging.     

基于小波网络的干旱程度评估方法

本根据干旱事件识别的基本原理,同时基于小波基具有很强的自适应性和函数变化能力,提出了一种基于小波网络的干旱程度评估新方法,并在最小均方能量准则下,采用相应的共轭梯度学习算法求解子波函数线性组合的尺度和时延参数,以及小波网络的权值,仿真实验表明采用该方法极大地提高了对干旱程度辩识的正确率,可为干旱研究提一条新的途径。     

斜变换ST的演化生成与快速算法

１．引言 含有“斜”基向量的正交变换（斜变换 ＳＴ）概念是由 Ｅｎｏｍｏｔｏ ＆ Ｓｈｉｂａｔａ（１９７１）提出的［１］．斜向量是一个在其范围内呈均匀阶梯下降的离散锯齿波形．对于亮度逐渐改变的图象,用斜向量来表示是适合的． Ｅｎｏｍｏｔｏ 　＆ 　Ｓｈｉｂａｔａ仅考虑了斜向量长度为 ４和 ８的情况．Ｐｒａｔｔ等人利用递推性将 ＳＴ推广到 Ｎ＝ ２ｍ阶的情形,给出了 ＳＴ的一般定义［２］,并与其它变换进行了比较［３］．ＳＴ已成功地用在图象编码上,而且在非正弦类交换编码的应用中,斜变换的效果最好［２,３］． Ａｈ…     

紧支撑三元正交小波滤波器的参数化

高维小波分析是分析和处理多维数字信号的有力工具．非张量积多元小波被广泛地应用在模式识别、纹理分析和边缘检测等领域．本文给出方体域上三元正交滤波器的一种参数化构造算法,三元小波滤波器的这种构造方法使我们能更方便地研究非张量积的三元正交小波．最后给出数值算例．     

Linear relations in time series models. II

In this paper an asymptotic theory is developed for a new time series model which was introduced in a previous paper [5]. An algorithm for computing estimates of the parameters of this time series model is given, and it is shown that these estimators are asymptotically efficient in the sense that they have the same asymptotic distribution as the maximum likelihood estimators.     

一种基于邻近点算法的变步长原始-对偶算法

本文考虑求解一种源于信号及图像处理问题的鞍点问题.基于邻近点算法的思想,我们对原始-对偶算法进行改进,构造一种对称正定且可变的邻近项矩阵,得到一种新的原始-对偶算法.新算法可以看成一种邻近点算法,因此它的收敛性易于分析,且无需较强的假设条件.初步实验结果表明,当新算法被应用于求解图像去模糊问题时,和其他几种主流的高效算法相比,新算法能得到较高质量的结果,且计算时间也是有竞争力的.     

Exact algorithms for dominating set

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969ⁿ) time and polynomial space algorithm.