Implicit Scaling of Linear Least Squares Problems

We consider the solution of weighted linear least squares problems by Householder transformations with implicit scaling, that is, with the weights stored separately. By holding inverse weights, the constrained case can be accommodated. The error analysis of the weighted and unconstrained case is readily extended and we show that iterative refinement may be applied.     

Accuracy and Stability of the Null Space Method for Solving the Equality Constrained Least Squares Problem

The null space method is a standard method for solving the linear least squares problem subject to equality constraints (the LSE problem). We show that three variants of the method, including one used in LAPACK that is based on the generalized QR factorization, are numerically stable. We derive two perturbation bounds for the LSE problem: one of standard form that is not attainable, and a bound that yields the condition number of the LSE problem to within a small constant factor. By combining the backward error analysis and perturbation bounds we derive an approximate forward error bound suitable for practical computation. Numerical experiments are given to illustrate the sharpness of this bound.     

On the Convergence of the Generalized Linear Least Squares Algorithm

This paper considers the issue of parameter estimation for biomedical applications using nonuniformly sampled data. The generalized linear least squares (GLLS) algorithm, first introduced by Feng and Ho (1993), is used in the medical imaging community for removal of bias when the data defining the model are correlated. GLLS provides an efficient iterative linear algorithm for the solution of the non linear parameter estimation problem. This paper presents a theoretical discussion of GLLS and introduces use of both Gauss Newton and an alternating Gauss Newton for solution of the parameter estimation problem in nonlinear form. Numerical examples are presented to contrast the algorithms and emphasize aspects of the theoretical discussion. AMS subject classification (2000) 65F10.R. A. Renaut: This work was partially supported by the Arizona Center for Alzheimer’s Disease Research, by NIH grant EB 2553301 and for the second author by NSF CMG-02223.Received December 2003. Revised November 2004. Communicated by Lars Eldén.     

An Exact Algorithm for Blockmodeling of Two-Mode Network Data

We consider problems where relationships between two sets (or modes) of objects are available in the form of a binary matrix with elements of 1 (0) indicating a bond (lack of a bond) between corresponding row and column objects. The goal is to establish a partition of the row objects and, simultaneously, a partition of the column objects to form blocks that consist of either exclusively 1s or exclusively 0s to the greatest extent possible. This two-mode blockmodeling problem arises in several scientific domains. In the social sciences, two-mode blockmodeling is particularly relevant for social network analysis, where the goal is to simultaneously partition a set of individuals and another set of objects (e.g., events they attended, organizations they are affiliated with, etc.). The inherent computational challenge of simultaneously constructing partitions for two distinct sets of objects has fostered a reliance on heuristics for two-mode blockmodeling. We offer an exact algorithm and demonstrate its efficacy in a simulation study. Two applications to real-world networks are also provided.     

A Lanczos‐type algorithm for the QR factorization of regular Cauchy matrices

We present a fast algorithm for computing the QR factorization of Cauchy matrices with real nodes. The algorithm works for almost any input matrix, does not require squaring the matrix, and fully exploits the displacement structure of Cauchy matrices. We prove that, if the determinant of a certain semiseparable matrix is non‐zero, a three term recurrence relation among the rows or columns of the factors exists. Copyright © 2002 John Wiley & Sons, Ltd.     

Consistency of a numerical approximation to the first principal component projection pursuit estimator

We generalize to functional data, the approach given by Croux and Ruiz-Gazen (1996) to compute robust projection-pursuit principal direction estimators, allowing also for smoothness in the estimators. Consistency of the approximated first principal direction estimator is derived.     

Weighted Profile Least Squares Estimation for a Panel Data Varying-Coefficient Partially Linear Model

This paper is concerned with inference of panel data varying-coefficient partially linear models with a one-way error structure. The model is a natural extension of the well-known panel data linear model （due to Baltagi 1995） to the setting of semiparametric regressions. The authors propose a weighted profile least squares estimator （WPLSE） and a weighted local polynomial estimator （WLPE） for the parametric and nonparametric components, respectively. It is shown that the WPLSE is asymptotically more efficient than the usual profile least squares estimator （PLSE）, and that the WLPE is also asymptotically more efficient than the usual local polynomial estimator （LPE）. The latter is an interesting result. According to Ruckstuhl, Welsh and Carroll （2000） and Lin and Carroll （2000）, ignoring the correlation structure entirely and ＂pretending＂ that the data are really independent will result in more efficient estimators when estimating nonparametric regression with longitudinal or panel data. The result in this paper shows that this is not true when the design points of the nonparametric component have a closeness property within groups. The asymptotic properties of the proposed weighted estimators are derived. In addition, a block bootstrap test is proposed for the goodness of fit of models, which can accommodate the correlations within groups illustrate the finite sample performances of the Some simulation studies are conducted to proposed procedures.     

Linear Least Squares Estimation of Regression Models for Two-Dimensional Random Fields

We consider the problem of estimating regression models of two-dimensional random fields. Asymptotic properties of the least squares estimator of the linear regression coefficients are studied for the case where the disturbance is a homogeneous random field with an absolutely continuous spectral distribution and a positive and piecewise continuous spectral density. We obtain necessary and sufficient conditions on the regression sequences such that a linear estimator of the regression coefficients is asymptotically unbiased and mean square consistent. For such regression sequences the asymptotic covariance matrix of the linear least squares estimator of the regression coefficients is derived.     

An observer for a class of disturbance driven nonlinear systems

An observer design for a class of nonlinear systems driven by disturbances or uncertainties is presented. The design is based on a high gain strategy, and the gain of the proposed observer is explicitly given.     

基于最小二乘法的长周期实物期权精确估值迭代模拟算法

提出了一种基于最小二乘法的长周期实物期权精确估值迭代模拟算法,并通过一个商用通信卫星在轨服务投资决策的算例对该算法的实现进行了说明.算法将一个需要一次进行大量运算的问题转变为一个需要进行多次运算但每次运算的计算量相对较小的问题,能够很好地解决在缺乏并行计算的条件下大量模拟运算所面临的计算资源瓶颈问题,不仅能够得到较为精确的实物期权价值的点估计值和区间估计值,也便于推导最优的投资策略.     

求矩阵方程组的反对称最小二乘解的递推算法

讨论了矩阵方程组A_1XB_1=D_1,A_2XB_2=D_2反对称最小二乘解的递推算法,该算法不仅能够用于计算反对称最小二乘解,而且在选取特殊的初始矩阵时,算法能够求出矩阵方程组的极小范数反对称最小二乘解,以及对给定的矩阵进行最佳逼近的反对称解.     

An Adaptive Version for the Metropolis Adjusted Langevin Algorithm with a Truncated Drift

This paper extends some adaptive schemes that have been developed for the Random Walk Metropolis algorithm to more general versions of the Metropolis-Hastings (MH) algorithm, particularly to the Metropolis Adjusted Langevin algorithm of Roberts and Tweedie (1996). Our simulations show that the adaptation drastically improves the performance of such MH algorithms. We study the convergence of the algorithm. Our proves are based on a new approach to the analysis of stochastic approximation algorithms based on mixingales theory.      

一类半正定多项式的配平方和算法

以牛顿多胞型技术为基础,根据牛顿多胞型中的点与点之间的相关性,给出了直接搜索多项式配平方和所需的最基本的项集Xs的算法,利用精确的符号算法PCAD,可将一类半正定多项式配成平方和,并编写了Maple程序"ASSOS",实现了多项式配平方和的自动生成.由多项式结构的稀疏性,此算法更能有效处理稀疏多项式.这一算法提高了多项式配平方和的效率,从而促进了一类代数不等式可读性证明的自动生成.除此之外,还给出了多项式不能表示为平方和的一个充分条件.     

An elementary algorithm for reporting intersections of red/blue curve segments

Let E_r and E_b be two sets of x-monotone and non-intersecting curve segments, E=E_rE_b and |E|=n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(nlogn+kloglogn) and it requires O(n) space.     

An Efficient Algorithm for a Sparse k-Edge-Connectivity Certificate

We present an efficient algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)²(log n)²) time using O(k(n + m′)) processors on an ARBITRARY CRCW PRAM, where n and m′ stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.     

An Algorithm for Minimizing the Range of Lateness on a Single Machine

This paper considers the problem of minimizing the range of lateness on a single machine. All the algorithms in the literature for solving this problem are based on the branch-and-bound approach, which has an exponential time complexity. In this paper, we demonstrate that this problem can actually be solved in pseudo-polynomial time, and develop such an algorithm. Computational performance of this algorithm on problems with various sizes is provided.     

An Exact Solution Algorithm for a Class of Production Planning and Scheduling Problems

This paper presents a formulation and an exact solution algorithm for a class of production planning and scheduling problems. The problem is one of optimally specifying production levels for each product in each period of the planning horizon. The objective is to minimize the sum of the set-up, regular time production, overtime and inventory holding costs. The problem has been formulated as a variation of fixed charge transportation problem. The problem discussed here is NP-hard in computational complexity. A numerical example is presented for better understanding of the algorithm.     

计算最小支撑出树的一种简便算法

本文通过对网络中有向支撑出树性质的研究,提出了在有向网络图中寻找以某一定点为根的最小有向支撑出树一种较简便的计算方法,并给出了应用该算法进行实际操作的一个算例．     

An Efficient Algorithm for Exact Distribution of Discrete Scan Statistics

Waiting time random variables and related scan statistics have a wide variety of interesting and useful applications. In this paper, exact distribution of discrete scan statistics for the cases of homogeneous two-state Markov dependent trials as well as i.i.d. Bernoulli trials are discussed by utilizing probability generating functions. A simple algorithm has been developed to calculate the distributions. Numerical results show that the algorithm is very efficient and is capable of handling large problems. AMS 2000 Subject Classification 60J22, 60E05, 60J10     

在有向网络中寻找最小支撑入树的计算方法

本文研究了有向网络中支撑入树的性质 ,提出了在有向网络图中寻找以某一指定点为根的最小支撑入树的一种较简便的算法 ,并给出了应用该算法的一个实际算例