Optimal and suboptimal smoothing algorithms for identification of time-varying systems with randomly drifting parameters

Noncausal estimation algorithms, which involve smoothing, can be used for off-line identification of nonstationary systems. Since smoothing is based on both past and future data, it offers increased accuracy compared to causal (tracking) estimation schemes, incorporating past data only. It is shown that efficient smoothing variants of the popular exponentially weighted least squares and Kalman filter-based parameter trackers can be obtained by means of backward-time filtering of the estimates yielded by both algorithms. When system parameters drift according to the random walk model and the adaptation gain is sufficiently small, the properly tuned two-stage Kalman filtering/smoothing algorithm, derived in the paper, achieves the Cramér-Rao type lower smoothing bound, i.e. it is the optimal noncausal estimation scheme. Under the same circumstances performance of the modified exponentially weighted least-squares algorithm is often only slightly inferior to that of the Kalman filter-based smoother.     

On the convergence of LMS filters under periodic signals

The response of the Least Mean Square (LMS) algorithm to deterministic periodic inputs is considered. Under these conditions, initial values of the tap-weight vector can be identified that lead to periodic responses of LMS filters. The stability of these periodic responses determines the long-term convergence of the filter. This analysis presents some advantages over the classical studies based on the correlation matrix, because it leads to more accurate results and a better understanding of the filter operation. It is also shown that such an operation does not change essentially for more realistic inputs, as when the desired response is perturbed with a zero-mean random signal. Finally, to validate the obtained results, some simulations and experiments have been conducted for an adaptive noise canceller.     

基于FP-Growth的图上随机游走推荐方法

推荐是促进诸如社交网络等应用活跃度的重要模式,但 庞大 的节点规模以及复杂的节点间关系给社交网络的推荐问题带来了挑战。随机游走是一种能够有效解决这类推荐问题的策略,但传统的随机游走算法没有充分考虑相邻节点间影响力的差异。提出一种基于FP-Growth的图上随机游走推荐方法,其基于社交网络的图结构,引入FP-Growth算法来挖掘相邻节点之间的频繁度,在此基础上构造转移概率矩阵来进行随机游走计算,最后得到好友重要程度排名并做出推荐。该方法既保留了随机游走方法能有效缓解数据稀疏性等特性,又权衡了不同节点连接关系的差异性。实验结果表明,提出的方法比传统随机游走算法的推荐性能更佳。     

Nonparametric Approximation of the Density Function Logarithm of the Two-dimensional Random Variable

Consideration was given to a method for approximating the probability density of a two-dimensional random variable with separate stages of generating the local estimates and smoothing the random errors. It was proposed to decompose the space on the basis of the source data into minimal-size domains where the local estimates of the density logarithm which correspond to the observation model with additive errors accepted in the regression analysis were generated. The error covariance matrix was shown to be completely definite and independent of the original density, which made it possible to apply the apparatus of nonparametric regression to optimizing the choice of the smoothing parameter.     

Optimum decoding based smoothing algorithm for dynamic systems with interference

This paper presents a new smoothing algorithm for discrete models with arbitrary random interference. For the disturbance noise, observation noise and interference, only independency is required. Moreover, the motion and observation models are not restricted to be linear functions of the disturbance noise and interference. This algorithm estimates the states by reducing the smoothing problem to a multiple composite hypothesis testing problem, and then using the Viterbi decoding algorithm. Simulation results have shown that the new algorithm performs very well.     

A graph-spectral method for surface height recovery

This paper describes a graph-spectral method for 3D surface integration. The algorithm takes as its input a 2D field of surface normal estimates, delivered, for instance, by a shape-from-shading or shape-from-texture procedure. We commence by using the surface normals to obtain an affinity weight matrix whose elements are related to the surface curvature. The weight matrix is used to compute a row-normalized transition probability matrix, and we pose the recovery of the integration path as that of finding the steady-state random walk for the Markov chain defined by this matrix. The steady-state random walk is given by the leading eigenvector of the original affinity weight matrix. By threading the surface normals together along the path specified by the magnitude order of the components of the leading eigenvector we perform surface integration. The height increments along the path are simply related to the traversed path length and the slope of the local tangent plane. The method is evaluated on needle-maps delivered by a shape-from-shading algorithm applied to real-world data and also on synthetic data. The method is compared with the local geometric height reconstruction method of Bors, Hancock and Wilson, and the global methods of Horn and Brooks and Frankot and Chellappa.     

基于LMS自适应算法的随机信号去噪仿真与分析

分析了LMS自适应滤波的基本原理和固定步长算法,介绍了Auan方差分析法。基于Matlab实现了滤波系统的搭建,并针对某光纤陀螺原始数据设计了仿真实验,得到固定步长标度因数的可行取值范围为0．2～0．9。利用仿真实验比较了LMS自适应算法与小波分析、均值滤波的去噪效果,采用Allan方差给出了误差源分析。结果表明LMS自适应滤波能有效降低角度随机游走等随机噪声。     

局部自适应输入控制的随机游走抠图

针对传统性抠图算法中,非完全正确用户标注及不精确超像素分割造成的信息误扩散,以随机游走算法为基础,提出带软性约束的抠图算法。通过对扩展Dirichlet问题的推导,指出带软约束的随机游走与部分自吸收随机游走概率的关联性。以吸收概率为指导,在传统相似扩散所构建的图模型上,根据局部窗口内特征矩阵的秩与方差设计了输入控制矩阵,使得信息扩散的过程能够跟随图像的局部特征进行自适应扩散。最后将软约束随机游走应用到单帧双层抠图及视频抠图中。实验表明,所提算法具有信息远距传播能力和良好的容错性能,尤其在用户标注不够充分的情况下能够取得更加优良的抠图结果。     

Minimax estimation by probabilistic criterion

A minimax estimation problem in multidimensional linear regression model containing uncertain parameters and random quantities is considered. Simultaneous distribution of random quantities that are a part of the observation model is not prescribed exactly; however, it has a fixed mean and a covariance matrix from the given set. For estimation algorithm optimization, we applied a minimax approach with the risk measure in the form of the exceedance probability of the estimate of a prescribed level by an error. It was shown that a linear estimation problem is equivalent to the minimax problem with the mean-square criterion. In addition, the corresponding linear estimate will be the best (in the minimax sense) by the probabilistic criterion at the class of all unbiased estimates. The least favorable distribution of random model parameters is also constructed. Several partial cases and a numerical example are considered.     

Bayes smoothing algorithms for segmentation of binary images modeled by markov random fields

A new image segmentation algorithm is presented, based on recursive Bayes smoothing of images modeled by Markov random fields and corrupted by independent additive noise. The Bayes smoothing algorithm yields the a posteriori distribution of the scene value at each pixel, given the total noisy image, in a recursive way. The a posteriori distribution together with a criterion of optimality then determine a Bayes estimate of the scene. The algorithm presented is an extension of a 1-D Bayes smoothing algorithm to 2-D and it gives the optimum Bayes estimate for the scene value at each pixel. Computational concerns in 2-D, however, necessitate certain simplifying assumptions on the model and approximations on the implementation of the algorithm. In particular, the scene (noiseless image) is modeled as a Markov mesh random field, a special class of Markov random fields, and the Bayes smoothing algorithm is applied on overlapping strips (horizontal/vertical) of the image consisting of several rows (columns). It is assumed that the signal (scene values) vector sequence along the strip is a vector Markov chain. Since signal correlation in one of the dimensions is not fully used along the edges of the strip, estimates are generated only along the middle sections of the strips. The overlapping strips are chosen such that the union of the middle sections of the strips gives the whole image. The Bayes smoothing algorithm presented here is valid for scene random fields consisting of multilevel (discrete) or continuous random variables.     

Frequency-response-shaped LMS adaptive filter

A new LMS algorithm is introduced for improved performance when a sinusoidal input signal is corrupted by correlated noise. The algorithm is based on shaping the frequency response of the transversal filter. This shaping is performed on-line by the inclusion of an additional term similar to the leakage factor in the adaptation equation of leaky LMS. This new term, which involves the multiplication of the filter coefficient vector by a matrix, is calculated in an efficient manner using the FFT. The proposed adaptive filter is shown analytically to converge in the mean and mean-square sense. The filter is also analyzed in the steady state in order to show the frequency-response-shaping capability. Simulation results illustrate that the performance of the frequency-response-shaped LMS (FRS-LMS) algorithm is very effective even for highly correlated noise.     

Clustering large attributed information networks: an efficient incremental computing approach

In recent years, many information networks have become available for analysis, including social networks, road networks, sensor networks, biological networks, etc. Graph clustering has shown its effectiveness in analyzing and visualizing large networks. The goal of graph clustering is to partition vertices in a large graph into clusters based on various criteria such as vertex connectivity or neighborhood similarity. Many existing graph clustering methods mainly focus on the topological structures, but largely ignore the vertex properties which are often heterogeneous. Recently, a new graph clustering algorithm, SA-cluster, has been proposed which combines structural and attribute similarities through a unified distance measure. SA-Cluster performs matrix multiplication to calculate the random walk distances between graph vertices. As part of the clustering refinement, the graph edge weights are iteratively adjusted to balance the relative importance between structural and attribute similarities. As a consequence, matrix multiplication is repeated in each iteration of the clustering process to recalculate the random walk distances which are affected by the edge weight update. In order to improve the efficiency and scalability of SA-cluster, in this paper, we propose an efficient algorithm In-Cluster to incrementally update the random walk distances given the edge weight increments. Complexity analysis is provided to estimate how much runtime cost Inc-Cluster can save. We further design parallel matrix computation techniques on a multicore architecture. Experimental results demonstrate that Inc-Cluster achieves significant speedup over SA-Cluster on large graphs, while achieving exactly the same clustering quality in terms of intra-cluster structural cohesiveness and attribute value homogeneity.     

Active control of vibration using a neural network

Feedforward control of sound and vibration using a neural network-based control system is considered, with the aim being to derive an architecture/algorithm combination which is capable of supplanting the commonly used finite impulse response filter/filtered-x least mean square (LMS) linear arrangement for certain nonlinear problems. An adaptive algorithm is derived which enables stable adaptation of the neural controller for this purpose, while providing the capacity to maintain causality within the control scheme. The algorithm is shown to be simply a generalization of the linear filtered-x LMS algorithm. Experiments are undertaken which demonstrate the utility of the proposed arrangement, showing that it performs as well as a linear control system for a linear control problem and better for a nonlinear control problem. The experiments also lead to the conclusion that more work is required to improve the predictability and consistency of the performance before the neural network controller becomes a practical alternative to the current linear feedforward systems.     

Bayesian analysis of semiparametric reproductive dispersion mixed-effects models

Semiparametric reproductive dispersion mixed-effects model (SPRDMM) is an extension of the reproductive dispersion model and the semiparametric mixed model, and it includes many commonly encountered models as its special cases. A Bayesian procedure is developed for analyzing SPRDMMs on the basis of P-spline estimates of nonparametric components. A hybrid algorithm combining the Gibbs sampler and the Metropolis-Hastings algorithm is used to simultaneously obtain the Bayesian estimates of unknown parameters, smoothing function and random effects, as well as their standard error estimates. The Bayes factor for model comparison is employed to select better approximation of the smoothing function via path sampling. Several simulation studies and a real example are used to illustrate the proposed methodologies.     

改进相关矩阵估计的LMS牛顿算法分析与仿真

在LMS牛顿算法中权值的更新采用了输入信号矢量的相关矩阵估计，不同的估计方法对算法的性能影响很大，该文分析了一种改进相关矩阵估计的LMS牛顿算法，该算法通过对LMS牛顿算法中的相关矩阵采用改进的指数加权估计，大大提高了算法的性能，同时维持了适中的计算复杂度。此外，还比较了LMS牛顿算法与RLS算法，从原理上说明了它们的密切联系；指出算法改善性能的关键在于变步长特性，即步长随着时间增加而逐渐变小，使得算法既可以保持较快的收敛速度，又获得了较小的失调。算法在智能天线中的仿真结果表明，该算法具有比常规LMS牛顿算法更优的性能。     

Random Walk Routing in WSNs with Regular Topologies

Topology is one of the most important characteristics for any type of networks because it represents the network's inherent properties and has great impact on the performance of the network. For wireless sensor networks (WSN), a well-deployed regular topology can help save more energy than what a random topology can do. WSNs with regular topologies can prolong network lifetime as studied in many previous work. However, little work has been done in developing effective routing algorithms for WSNs with regular topologies, except routing along a shortest path with the knowledge of global location information of sensor nodes. In this paper, a new routing protocol based on random walk is proposed. It does not require global location information. It also achieves load balancing property inherently for WSNs which is difficult to achieve by other routing protocols. In the scenarios where the message required to be sent to the base station is in comparatively small size with the inquiry message among neighboring nodes, it is proved that the random walk routing protocol can guarantee high probability of successful transmission from the source to the base station with the same amount of energy consumption as the shortest path routing. Since in many applications of WSNs, sensor nodes often send only beep-like small messages to the base station to report their status, our proposed random walk routing is thus a viable scheme and can work very efficiently especially in these application scenarios. The random walk routing provides load balancing in the WSN as mentioned, however, the nodes near to the base station are inevitably under heavier burden than those far away from the base station. Therefore, a density-aware deployment scheme is further proposed to guarantee that the heavy-load nodes do not affect the network lifetime even if their energy is exhausted. The main idea is deploying sensors with different densities according to their distance to the base station. It will be shown in this paper that incorporating the random walk routing protocol with the density-aware deployment scheme can effectively prolong the network lifetime.     

随机行走的电路分析应用及并行化改进

论述了随机行走算法的基本原理,理论分析了给定允许误差和置信概率下,随机行走算法的结束条件;讨论了随机行走算法在电路分析中的应用,并结合应用实例分析了算法的性能;讨论了算法的时间复杂性和影响算法执行时间的主要因素,重点分析了算法的并行特征,提出了采用并行计算技术提高算法性能的新方法,通过与串行算法的实验比较,表明了并行计算技术是提高随机行走算法执行速度的有效方法,比现有的方法适应性更广。     

全局孤立性和局部同质性图表示的随机游走显著目标检测算法

目前的显著性检测算法主要依赖像素间的相互对比,缺乏对显著目标自身特性的分析理解. 依据显著目标是显眼、紧凑和完整的思路,提出一种基于目标全局孤立性和局部同质性的 随机游走显著目标检测算法,将视觉显著性检测公式化为马尔科夫随机游走问题. 首先将输入图像进行分块,根据像素块之间颜色特征和方向特征的相似性确定边的权重, 从而构建图模型;然后通过全连通图搜索提取全局特性,突出全局较孤立的区域; 同时通过k-regular图搜索提取局部特性,增强局部较均匀的区域;最后将全局特性和局部 特性相结合得到显著图,进而确定感兴趣区域位置. 实验结果表明,相比于其他两种具有代表性的算法,所提方法检测结果更加准确、合理, 证明该算法切实可行.     

The analysis of a parameter identification algorithm which was derived from the continuous time Kalman filter

The matrix Riccati equation associated with the identification algorithm may be regarded as two sets of scalar equations representing the squares and products of pairs of errors in the estimates of the parameters. Although the initial condition for the Riccati equation is arbitrary, it is shown that its elements tend to the ratio of the product of the actual estimation errors. This method of identification is shown to be stable but rather sensitive to numerical errors in its computation. However, an outcome of the analysis is that an alternative algorithm, which eliminates the Riccati equation, is suggested. Related convergence and stability properties of state observation by the deterministic filter are also discussed.     

改进的随机游走模型节点排序方法

复杂网络节点重要性排序是研究复杂网络特性的重要方面之一,被广泛应用于数据挖掘、Web搜索、社会网络分析等众多研究领域。基于物理学场论模型,提出改进的随机游走模式的节点重要性排序算法,即通过节点之间相互作用的场力来确定随机游走模型中的Markov转移矩阵,这样可以对节点重要性排序作出更加准确真实的评估。实验结果表明,所采用的节点重要性评估方法能更合理地解释节点重要性的意义,并且可以给出更加真实精确的节点重要性的评估结果。