Near optimal solutions to least-squares problems with stochastic uncertainty

In this paper, we consider least-squares (LS) problems where the regression data is affected by parametric stochastic uncertainty. In this setting, we study the problem of minimizing the expected value with respect to the uncertainty of the LS residual. For general nonlinear dependence of the data on the uncertain parameters, determining an exact solution to this problem is known to be computationally prohibitive. Here, we follow a probabilistic approach, and determine a probable near optimal solution by minimizing the empirical mean of the residual. Finite sample convergence of the proposed method is assessed using statistical learning methods. In particular, we prove that if one constructs the empirical approximation of the mean using a finite number N of samples, then the minimizer of this empirical approximation is, with high probability, an ε-suboptimal solution for the original problem. Moreover, this approximate solution can be efficiently determined numerically by a standard recursive algorithm. Comparisons with gradient algorithms for stochastic optimization are also discussed in the paper and several numerical examples illustrate the proposed methodology.     

A fast digital Radon transform—An efficient means for evaluating the Hough transform

A fast digital Radon transform based on recursively defined digital straight lines is described, which has the sequential complexity of N² log N additions for an N × N image. This transform can be used to evaluate the Hough transform to detect straight lines in a digital image. Whilst a parallel implementation of the Hough transform algorithm is difficult because of global memory access requirements, the fast digital Radon transform is vectorizable and therefore well suited for parallel computation. The structure of the fast algorithm is shown to be quite similar to the FFT algorithm for decimation in frequency. It is demonstrated that even for sequential computation the fast Radon transform is an attractive alternative to the classical Hough transform algorithm.     

On-Line File Caching

Abstract. Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost , maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. Specifically, when a requested file is not in the cache, bring it into the cache and pay the retrieval cost, and remove other files from the cache so that the total size of files remaining in the cache is at most k . This problem generalizes previous paging and caching problems by allowing objects of arbitrary size and cost, both important attributes when caching files for world-wide-web browsers, servers, and proxies. We give a simple deterministic on-line algorithm that generalizes many well-known paging and weighted-caching strategies, including least-recently-used, first-in-first-out, flush-when-full, and the balance algorithm. On any request sequence, the total cost incurred by the algorithm is at most k/(k-h+1) times the minimum possible using a cache of size h ≤ k . For any algorithm satisfying the latter bound, we show it is also the case that for most choices of k , the retrieval cost is either insignificant or at most a constant (independent of k ) times the optimum. This helps explain why competitive ratios of many on-line paging algorithms have been typically observed to be constant in practice.     

A stability classification method and its application to pipelined solution of linear recurrences

A new method of classification for numerical stability of parallel algorithms is proposed based on the theoretical foundation of forward error analysis. It partitions the algorithms according to their asymptotic stability—a measure introduced to relate the limiting behavior of the stability to the size of the problem. Using this method, the stability aspect of the pipelined solution technique for first-order and second-order linear recurrences—the core of a tridiagonal linear equation solver—is studied. In particular, it shows that the pipelined solution method of the first-order linear recurrences has the same degree of stability as the commonly used sequential evaluation algorithms. The stability problems of sequential and pipelined solution methods of the second-order linear recurrences are also studied.     

Fast parallel Preconditioned Conjugate Gradient algorithms for robot manipulator dynamics simulation

In this paper fast parallel Preconditioned Conjugate Gradient (PCG) algorithms for robot manipulator forward dynamics, or dynamic simulation, problem are presented. By exploiting the inherent structure of the forward dynamics problem, suitable preconditioners are devised to accelerate the iterations. Also, based on the choice of preconditioners, a modified dynamic formulation is used to speedup both serial and parallel computation of each iteration. The implementation of the parallel algorithms on two interconnected processor arrays is discussed and their computation and communication complexities are analyzed. The simulation results for a Puma Arm are presented to illustrate the effectiveness of the proposed preconditioners. With a faster convergence due to preconditioning and a faster computation of iterations due to parallelization, the developed parallel PCG algorithms represent the fastest alternative for parallel computation of the problem withO(n) processors.     

Covering a string

We consider the problem of finding the repetitive structures of a given stringx. The periodu of the stringx grasps the repetitiveness ofx, sincex is a prefix of a string constructed by concatenations ofu. We generalize the concept of repetitiveness as follows: A stringw covers a stringx if there is a superstring ofx which is constructed by concatenations and superpositions ofw. A substringw ofx is called aseed ofx ifw coversx. We present anO(n logn)-time algorithm for finding all the seeds of a given string of lengthn.Partially supported by SERC Grants GR/F 00898 and GR/J 17844, NATO Grant CRG 900293, ESPRIT BRA Grant 7131 for ALCOMII, and MRC Grant G 9115730.Partially supported by MRC Grant G 9115730 and S.N.U. Posco Research Fund 94-15-1112.     

几种常用CT图像分割算法分析和探讨

图像分割是数字图像处理的一个经典难题。其分割质量的好坏直接影响到图像处理的后续工作。因而在理论研究和实际应用中受到研究人员的广泛重视。本文在总结了过去的分割方法基础上,就目前常用几种分割方法进行实验研究。主要包括阈值分割、LOG算子分割、FCM聚类分割、分水岭分割,并结合CT图像进行图像分割。文章阐述了各种分割方法的概念及原理,并在此基础上对分割结果进行了分析和探讨,得出各种方法的优点和不足。这些实验结论将为后续研究提供科学依据。     

基于移动锚节点的无线传感器网络圆心定位

文章提出了一种利用无线传感器网络无线信号接收强度（RSSI）和移动锚节点轨迹来获得待定节点位置的算法。该算法在有多个可移动锚节点的情况下,定位将会更加高效。在定位阶段,通过RSSI测得锚节点到待定节点的距离,并利用三个以上移动锚节点的坐标（包括三个）来求解圆的方程,计算出待定节点的位置。     

云计算下基于CRP算法的资源提供策略

云计算资源管理系统是用于接收来自云计算用户的资源请求,并且把特定的资源封装为服务提供给资源请求者。在云计算环境下,如何为资源请求者选择合适的资源是一个值得研究的课题。文中通过对云计算下现有的资源提供策略的分析,同时根据不同云提供者提供的计算资源的成本不同的特点,综合考虑资源的计算能力、可靠性和单位成本三点因素,提出了云计算下基于CRP算法的资源提供策略。这种资源提供策略既能提供满足用户资源请求的服务,也能降低云服务提供者的运营成本,从而获得更大收益。     

基于AUPF的TDOA几何定位跟踪算法研究

使用无源时差（TDOA）定位技术确定无人机等小型辐射源目标的位置是当前研究的热点,针对时差定位算法较为复杂的实际情况,推导了时差双曲线的几何解,并提出了一种基于自适应无迹粒子滤波（AUPF）技术的移动目标定位跟踪方法。通过仿真对该方法在不同场景的应用效果进行了验证,进一步比较分析了算法的定位精度。结果表明,基于自适应无迹粒子滤波的时差几何定位跟踪算法可以在多种情况下较好地拟合出目标真实运动轨迹,实现对运动目标的定位跟踪,同时拥有更低的定位误差和更高的轨迹包容度,使用该方法可以显著提高对非合作移动辐射源目标的位置估计性能。