Fast Computation of Multivariate Kernel Estimators

Abstract

Multivariate extensions of binning techniques for fast computation of kernel estimators are described and examined. Several questions arising from this multivariate extension are addressed. The choice of binning rule is discussed, and it is demonstrated that linear binning leads to substantial accuracy improvements over simple binning. An investigation into the most appropriate means of computing the multivariate discrete convolutions required for binned kernel estimators is also given. The results of an empirical study indicate that, in multivariate settings, the fast Fourier transform offers considerable time savings compared to direct calculation of convolutions.     

Multivariate interval interpolation

The problem of multivariate interval interpolation has been defined. Two algorithms for the computation of a multivariate interval interpolating polynomial have been proposed. The algorithms have been compared among themselves with respect to the number of interval arithmetic operations required to compute them and the width of the computed intervals. One of the algorithms is recommended for fast computation and the other for obtaining the most accurate results.     

On Moments of Folded and Truncated Multivariate Normal Distributions

Recurrence relations for integrals that involve the density of multivariate normal distributions are developed. These recursions allow fast computation of the moments of folded and truncated multivariate normal distributions. Besides being numerically efficient, the proposed recursions also allow us to obtain explicit expressions of low-order moments of folded and truncated multivariate normal distributions. Supplementary material for this article is available online.     

Bootstrap bandwidth selection in kernel density estimation from a contaminated sample

In this paper we consider kernel estimation of a density when the data are contaminated by random noise. More specifically we deal with the problem of how to choose the bandwidth parameter in practice. A theoretical optimal bandwidth is defined as the minimizer of the mean integrated squared error. We propose a bootstrap procedure to estimate this optimal bandwidth, and show its consistency. These results remain valid for the case of no measurement error, and hence also summarize part of the theory of bootstrap bandwidth selection in ordinary kernel density estimation. The finite sample performance of the proposed bootstrap selection procedure is demonstrated with a simulation study. An application to a real data example illustrates the use of the method. This research was supported by ‘Projet d’Actions de Recherche Concertées’ (No. 98/03-217) from the Belgian government. Financial support from the IAP research network nr P5/24 of the Belgian State (Federal Office for Scientific, Technical and Cultural Affairs) is also gratefully acknowledged.     

虚拟企业管理中的伙伴选择问题:模型与理论分析

本文建立了虚拟企业伙伴选择问题的整数规划模型，并从理论上证明了该类问题正规解的存在性．所获结果对于该类问题的研究与求解提供了可靠的理论依据，并将建立的模型和所得结论应用到一个工程实际问题，采用遗传算法求解，取得了满意的计算结果．     

基于时序矩阵分解的缺失销售数据估计

企业的历史销售记录是供应链优化研究的基础数据来源,然而,在日常的研究中,几乎所有可以通过公开途径获得的销售记录都是高度不完整的,这为研究者开展工作带来了极大的不便。为解决此问题,本文提出,以销售数据集中已有的数据为基础,使用面向时序数据的矩阵分解模型MAFTIS对其缺失的部分进行估算,从而把残缺的数据集补全完整。进一步地,为提高MAFTIS的计算效率,本文还为该模型设计了一种基于交替最小二乘法的求解策略MAFTIS^ALS。在评估实验中,MAFTIS^ALS被用于三个真实销售数据集的缺失记录估计,结果显示,与其它估计模型相比,MAFTIS^ALS能获得更准确的估计结果,并且具有更高的收敛速度。     

A fast solution method for the time-dependent orienteering problem

This paper introduces a fast solution procedure to solve 100-node instances of the time-dependent orienteering problem (TD-OP) within a few seconds of computation time. Orienteering problems occur in logistic situations were an optimal combination of locations needs to be selected and the routing between the selected locations needs to be optimized. In the time-dependent variant, the travel time between two locations depends on the departure time at the first location. Next to a mathematical formulation of the TD-OP, the main contribution of this paper is the design of a fast and effective algorithm to tackle this problem. This algorithm combines the principles of an ant colony system (ACS) with a time-dependent local search procedure equipped with a local evaluation metric. Additionally, realistic benchmark instances with varying size and properties are constructed. The average score gap with the known optimal solution on these test instances is only 1.4% with an average computation time of 0.5 seconds. An extensive sensitivity analysis shows that the performance of the algorithm is insensitive to small changes in its parameter settings.     

Multipole fast algorithm for the least‐squares approach of the method of fundamental solutions for three‐dimensional harmonic problems

In this article we describe an improvement in the speed of computation for the least‐squares method of fundamental solutions (MFS) by means of Greengard and Rokhlin's FMA. Iterative solution of the linear system of equations is performed for the equations given by the least‐squares formulation of the MFS. The results of applying the method to test problems from potential theory with a number of boundary points in the order of 80,000 show that the method can achieve fast solutions for the potential and its directional derivatives. The results show little loss of accuracy and a major reduction in the memory requirements compared to the direct solution method of the least squares problem with storage of the full MFS matrix. The method can be extended to the solution of overdetermined systems of equations arising from boundary integral methods with a large number of boundary integration points. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 828–845, 2003.     

Multi-Path Approach for Reliability-Redundancy Allocation Using a Scaling Method

The reliability-redundancy allocation problem is an optimization problem that achieves better system reliability by determining levels of component redundancies and reliabilities simultaneously. The problem is classified with the hardest problems in the reliability optimization field because the decision variables are mixed-integer and the system reliability function is nonlinear, non-separable, and non-convex. Thus, iterative heuristics are highly recommended for solving the problem due to their reasonable solution quality and relatively short computation time. At present, most iterative heuristics use sensitivity factors to select an appropriate variable which significantly improves the system reliability. The sensitivity factor represents the impact amount of each variable to the system reliability at a designated iteration. However, these heuristics are inefficient in terms of solution quality and computation time because the sensitivity factor calculations are performed only at integer variables. It results in degradation of the exploration and growth in the number of subsequent continuous nonlinear programming (NLP) subproblems. To overcome the drawbacks of existing iterative heuristics, we propose a new scaling method based on the multi-path iterative heuristics introduced by Ha (2004). The scaling method is able to compute sensitivity factors for all decision variables and results in a decreased number of NLP subproblems. In addition, the approximation heuristic for NLP subproblems helps to avoid redundant computation of NLP subproblems caused by outlined solution candidates. Numerical experimental results show that the proposed heuristic is superior to the best existing heuristic in terms of solution quality and computation time.     

A simple heuristic for the multi item single level capacitated lotsizing problem

This paper presents a fast and flexible heuristic for the multi item capacitated lotsizing problem. The lotsizing step requires only O(NT) computations which is at least an order of magnitude faster than other well-known heuristics. The method is flexible since it allows the user to specify features such as how to sort items, which criterion to use in combining lots and how to search the demand matrix. Extensive computational results show that the new method outperforms existing heuristics both in terms of average solution quality and required computation times.     

Reissner厚板弹性弯曲的一般解析解

针对大型工程建设中的Reisner厚板弹性弯曲问题,本文采用复级数方法求解相应的常系数偏微分方程组的边值问题,并首次得到了任意边界条件下的一般解析解.该解形式简单,计算方便、可靠.以四边简支和三边固支一边自由两种支撑条件下厚板承受均布载荷为例进行了分析验算,与已有的计算结果相比,计算结果相当满意.同时本文还着重对解的收敛速度、正确性(合理性)及边界满足情况进行了考察.     

A new modified panoramic UAV image stitching model based on the GA-SIFT and adaptive threshold method

This paper presents panoramic unmanned aerial vehicle (UAV) image stitching techniques based on an optimal Scale Invariant Feature Transform (SIFT) method. The image stitching representation associates a transformation matrix with each input image. In this study, we formulate stitching as a multi-image matching problem, and use invariant local features to find matches between the images. An improved Geometric Algebra (GA-SIFT) algorithm is proposed to realize fast feature extraction and feature matching work for the scanned images. The proposed GA-SIFT method can locate more feature points with greater accurately than the traditional SIFT method. The adaptive threshold value method proposed solves the limitation problem of high computation load and high cost of stitching time by greater feature points extraction and stitching work. The modified random sample consensus method is proposed to estimate the image transformation parameters and to determine the solution with the best consensus for the data. The experimental results demonstrate that the proposed image stitching method greatly increases the speed of the image alignment process and produces a satisfactory image stitching result. The proposed image stitching model for aerial images has good distinctiveness and robustness, and can save considerable time for large UAV image stitching.     

非线性Kundu方程的弱守恒差分格式

本文考察了一类非线性Kundu方程的周期初值问题,提出了一种弱守恒的差分格式,对其差分解作了先验估计,证明了格式的收敛性与稳定性,最后,通过数值计算检验了格式的可信性.     

On the Remaining Service Time upon Reaching a Given Level in M/G/1 Queues

The ability of effectively finding the distribution of the remaining service time upon reaching a target level in M/G/1 queueing systems is of great practical importance. Among other things, it is necessary for the estimation of the Quality-of-Service (QoS) provided by Asynchronous Transfer Mode (ATM) networks. The previous papers on this subject did not give a comprehensive solution to the problem. In this paper an explicit formula for this distribution is given. This formula is general as it includes any initial level of the length of the queue, any type of service distribution (heavy tails) and any traffic intensity ρ. Moreover, it is easy to use and fast in computation. To show this several numerical examples are presented. In addition, a solution of the similar problem in G/M/1 queues (which is the distribution of the remaining interarrival time) is given.     

基于局部多项式展开的多元非参数模型贝叶斯带宽选择

在多元非参数模型中带宽和阶的选择对局部多项式估计量的表现十分重要。本文基于交叉验证准则提出一个自适应贝叶斯带宽选择方法。在给定的误差密度函数下,该方法可推导出对应的似然函数,并构造带宽参数的后验密度函数。随后,通过带宽的后验期望可同时获得阶和带宽的估计。数值模拟的结果表明,该方法不仅比大拇指准则方法精确,且比交叉验证方法耗时更少。与此同时,与Nadaraya-Watson估计相比,所提带宽选择方法对多元非参数模型的适应性要更好。最后,本文通过一组实际数据说明有限样本下所提贝叶斯带宽选择的表现很好。     

非线性Gerdjikov-Ivanov方程的守恒差分格式

本文考察了一类非线性Gerdjikov-Ivanov方程的周期初值问题，提出了一种守恒的差分格式，对其差分解作了先验估计．证明了格式的收敛性与稳定性，最后，通过数值计算检验了格式的可信性。     

Heuristics for matrix bandwidth reduction

In this work, we provide two heuristic algorithms for the matrix bandwidth reduction problem. The first is a genetic algorithm and the second uses node label adjustments. Experiments show these heuristics improve solution quality when compared with the well-known GPS algorithm and recently-developed methods using tabu search and GRASP with Path Relinking. Further, the node adjustment approach obtains solutions at speeds comparable to the fast GPS algorithm.     

An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.     

Evaluating Nearly Singular Multinormal Expectations with Application to Wave Distributions

The numerical computation of expectations for (nearly) singular multivariate normal distribution is a difficult problem, which frequently occurs in widely varying statistical contexts. In this article we discuss several strategies to improve the algorithm proposed by Genz and Kwong (2000) when either a moderate accuracy is requested, the correlation structure is strong, and, most importantly, the dimension of the integral is large. Test results for typical problems show an average speedup of 10 using the modified algorithm, but even more is gained as the dimension of the problem increases. We apply the modified algorithm to compute long-run distributions of Gaussian wave characteristics, a difficult problem where previous algorithms fail to compute accurate values in reasonable time. AMS 2000 Subject Classification 65C60, 65D15, 68W25     

A penalty function heuristic for the resource constrained shortest path problem

The resource constrained shortest path problem (RCSP) consists of finding the shortest path between two nodes of an assigned network, with the constraint that traversing an arc of the network implies the consumption of certain limited resources. In this paper we propose a new heuristic for the solution of the RCSP problem in medium and large scale networks. It is based on the extension to the discrete case of the penalty function heuristic approach for the fast ε-approximate solution of difficult large-scale continuous linear programming problems. Computational experience on test instances has shown that the proposed penalty function heuristic (PFH) is very effective in the solution of medium and large scale RCSP instances. For all the tests reported it provides very good upper bounds (in many cases the optimal solution) in less than 26 iterations, where each iteration requires only the computation of a shortest path.