A new version of Kovarik’s approximate orthogonalization algorithm without matrix inversion

In 1970 Kovarik proposed approximate orthogonalization algorithms. One of them (algorithm B) has quadratic convergence but requires at each iteration the inversion of a matrix of similar dimension to the initial one. An attempt to overcome this difficulty was made by replacing the inverse with a finite Neumann series expansion involving the original matrix and its adjoint. Unfortunately, this new algorithm loses the quadratic convergence and requires a large number of terms in the Neumann series which results in a dramatic increase in the computational effort per iteration. In this paper we propose a much simpler algorithm which, by using only the first two terms in a different series expansion, gives us the desired result with linear convergence. Systematic numerical experiments for collocation and Toeplitz matrices are also described.     

Entropies for detection of epilepsy in EEG

The electroencephalogram (EEG) is a representative signal containing information about the condition of the brain. The shape of the wave may contain useful information about the state of the brain. However, the human observer cannot directly monitor these subtle details. Besides, since bio-signals are highly subjective, the symptoms may appear at random in the time scale. Therefore, the EEG signal parameters, extracted and analyzed using computers, are highly useful in diagnostics. The aim of this work is to compare the different entropy estimators when applied to EEG data from normal and epileptic subjects. The results obtained indicate that entropy estimators can distinguish normal and epileptic EEG data with more than 95% confidence (using t-test). The classification ability of the entropy measures is tested using ANFIS classifier. The results are promising and a classification accuracy of about 90% is achieved.     

近似动态规划在双容水箱预测控制中的应用

在双容水箱液位优化控制的研究中,由于双容水箱液位控制系统是一个典型的具有大滞后、非线性特征的难控系统,造成系统液位控制不稳定.为解决上述问题,提出一种近似动态规划的预测控制算法,建立反映系统预测时域内参考轨迹与预测输出偏差的性能指标函数J.将函数J的优化问题看作动态规划问题,为了避免“维数灾”,采用近似动态规划求解J的近似值,获得最(次)优控制策略.算法包括评价网络、模型网络和执行网络三部分.评价网络近似性能指标函数,模型网络近似系统输入输出关系,执行网络给出相应控制策略.通过不断在线调整各网络参数,使系统输出逼近参考液位.仿真结果表明,与经典PID算法相比,改进算法表现出更好的控制效果.     

Parallel block tridiagonalization of real symmetric matrices

Two parallel block tridiagonalization algorithms and implementations for dense real symmetric matrices are presented. Block tridiagonalization is a critical pre-processing step for the block tridiagonal divide-and-conquer algorithm for computing eigensystems and is useful for many algorithms desiring the efficiencies of block structure in matrices. For an “effectively” sparse matrix, which frequently results from applications with strong locality properties, a heuristic parallel algorithm is used to transform it into a block tridiagonal matrix such that the eigenvalue errors remain bounded by some prescribed accuracy tolerance. For a dense matrix without any usable structure, orthogonal transformations are used to reduce it to block tridiagonal form using mostly level 3 BLAS operations. Numerical experiments show that block tridiagonal structure obtained from this algorithm directly affects the computational complexity of the parallel block tridiagonal divide-and-conquer eigensolver. Reduction to block tridiagonal form provides significantly lower execution times, as well as memory traffic and communication cost, over the traditional reduction to tridiagonal form for eigensystem computations.     

Approximate factorization of multivariate polynomials using singular value decomposition

We describe the design, implementation and experimental evaluation of new algorithms for computing the approximate factorization of multivariate polynomials with complex coefficients that contain numerical noise. Our algorithms are based on a generalization of the differential forms introduced by W. Ruppert and S. Gao to many variables, and use singular value decomposition or structured total least squares approximation and Gauss–Newton optimization to numerically compute the approximate multivariate factors. We demonstrate on a large set of benchmark polynomials that our algorithms efficiently yield approximate factorizations within the coefficient noise even when the relative error in the input is substantial (10⁻³).     

数据流层次窗口模型及聚集查询算法

本文提出了一种多层次时间窗口模型,支持在不同时段对数据流进行不同粒度的建模,并给出了多粒度聚集树结构及其数据流聚集查询算法,从而有效地解决了在有限时空条件下的数据流聚集查询问题。     

一种求解欧几里德TSP问题的新算法

针对几何性质的TSP问题,提出了一种“整体优先”算法,算法的核心思想是边构造边调整。实验结果表明,该算法不仅时间复杂度和空间复杂度低,寻优能力也很强,其综合性能超过目前的一些主流算法,特别适合在微机上求解TSP问题。     

A model-based approximate λ-policy iteration approach to online evasive path planning and the video game Ms. Pac-Man

This paper presents a model-based approximate λ-policy iteration approach using temporal differences for optimizing paths online for a pursuit-evasion problem, where an agent must visit several target positions within a region of interest while simultaneously avoiding one or more actively pursuing adversaries. This method is relevant to applications, such as robotic path planning, mobile-sensor applications, and path exposure. The methodology described utilizes cell decomposition to construct a decision tree and implements a temporal difference-based approximate λ-policy iteration to combine online learning with prior knowledge through modeling to achieve the objectives of minimizing the risk of being caught by an adversary and maximizing a reward associated with visiting target locations. Online learning and frequent decision tree updates allow the algorithm to quickly adapt to unexpected movements by the adversaries or dynamic environments. The approach is illustrated through a modified version of the video game Ms. Pac-Man, which is shown to be a benchmark example of the pursuit-evasion problem. The results show that the approach presented in this paper outperforms several other methods as well as most human players.     

RMAIN: Association rules maintenance without reruns through data

Association rules are well recognised as a data mining tool for analysis of transactional data, currently going far beyond the early basket-based applications. A wide spectrum of methods for mining associations have been proposed up to date, including batch and incremental approaches. Most of the accurate incremental methods minimise, but do not completely eliminate reruns through processed data. In this paper we propose a new approximate algorithm RMAIN for incremental maintenance of association rules, which works repeatedly on subsequent portions of new transactions. After a portion has been analysed, the new rules are combined with the old ones, so that no reruns through the processed transactions are performed in the future. The resulting set of rules is kept similar to the one that would be achieved in a batch manner. Unlike other incremental methods, RMAIN is fully separated from a rule mining algorithm and this independence makes it highly general and flexible. Moreover, it operates on rules in their final form, ready for decision support, and not on intermediate representation (frequent itemsets), which requires further processing. These features make the RMAIN algorithm well suited for rule maintenance within knowledge bases of autonomous systems with strongly bounded resources and time for decision making. We evaluated the algorithm on synthetic and real datasets, achieving promising results with respect to either performance or quality of output rules.     

Models of approximation in databases

Partial information in databases can arise when information from several databases is combined. Even if each database is complete for some “world”, the combined databases will not be, and answers to queries against such combined databases can only be approximated. In this paper we describe various situations in which a precise answer cannot be obtained for a query asked against multiple databases. Based on an analysis of these situations, we propose a classification of constructs that can be used to model approximations.

The main goal of the paper is to study several formal models of approximations and their semantics. In particular, we obtain universality properties for these models of approximations. Universality properties suggest syntax for languages with approximations based on the operations which are naturally associated with them. We prove universality properties for most of the approximation constructs. Then we design languages built around datatypes given by the approximation constructs. A straightforward approach results in languages that have a number of limitations. In an attempt to overcome those limitations, we explain how all the languages can be embedded into a language for conjunctive and disjunctive sets from Libkin and Wong (1996) and demonstrate its usefulness in querying independent databases. We also discuss the semantics of approximation constructs and the relationship between them.