Two- or three-stage least squares?

Two elements enter the choice between 2 and 3SLS for full-system estimation: statistical efficiency and computational cost. 2SLS always has the computational edge, but 3SLS can be more efficient, a relative advantage that increases with the strength of the interrelations among the error terms. A measure of these interrelations is thus helpful in making the choice, and, when there are only two equations, this has suggested using a high pairwise error correlation as an indicator of when to use 3SLS. In larger systems of equations, however, these pairwise correlations can remain small even though more general interrelations give 3SLS the relative advantage. More general indicators are therefore needed, and this paper suggests three such and demonstrates their efficacy.Professor of Economics, Boston College, and Principal Research Associate, Center for Computational Research in Economics and Management Science, MIT. All computation was done on the TROLL system at MIT. My thanks go to Josh Charap for his able research assistance. This research was sponsored in part by the National Science Foundation under grant #IST-8420614.     

An elementary proof of Sylvester’s double sums for subresultants

In 1853 Sylvester stated and proved an elegant formula that expresses the polynomial subresultants in terms of the roots of the input polynomials. Sylvester’s formula was also recently proved by Lascoux and Pragacz using multi-Schur functions and divided differences. In this paper, we provide an elementary proof that uses only basic properties of matrix multiplication and Vandermonde determinants.     

一种门限可追踪的匿名签密方案

为解决匿名签密算法中签密者身份的追踪问题,提出了一种门限可追踪的匿名签密方案.该方案借助范德蒙行列式生成成员的公钥和私钥,通过在匿名签密过程中附加一些与签密者身份相关的额外信息,实现签密者身份的门限追踪.在不可分模型下,证明了该方案满足匿名性、门限可追踪性、不可伪造性和不相关性.     

直线生成算法的改进

直线是图形的基本元素,研究其生成算法具有重要意义。由于经典的Bresenham直线生成算法一次计算只能生成一个像素点,效率较低。为了提高直线生成效率,通过对其进行改进,提出了一种利用直线前两行像素行的像素点数目来计算其余各像素行的像素点数目的算法。该算法在保持Bresenham算法不使用取整和小数运算的优点下,还提高了直线生成效率,一次计算可以生成一个像素行。     

基于相似性分析的SVM快速分类算法

针对支持向量机(SVM)分类速度取决于支持向量数目的应用瓶颈,提出一种SVM快速分类算法。通过引入支持向量在特征空间的相似性度量,构建特征空间中的最小支撑树,在此基础上将支持向量按相似性最大进行分组,依次在每组中找到决定因子和调整因子,用两者的线性组合拟合一组支持向量在特征空间的加权和,以减少支持向量的数量,提高支持向量机的分类速度。实验结果证明,该方法能以很小的分类精度损失换取较大的分类时间缩减,满足SVM实时分类的要求。     

Demons非刚性配准算法拓扑保持性的研究

在基于配准的图像分割应用中, 拓扑保持性是非刚性图像配准算法的一个重要约束. 本文从矢量场特性出发, 分析了Demons非刚性图像配准算法导致目标拓扑改变时变形场的特点. 根据变形场特点与其雅可比行列式之间的关系, 给出了校正该算法拓扑保持性的方法. 实验表明, 改进后的变形场具有了拓扑保持性.     

Maximum contrast analysis for nonnegative blind source separation

In this paper, we propose a maximum contrast analysis (MCA) method for nonnegative blind source separation, where both the mixing matrix and the source signals are nonnegative. We first show that the contrast degree of the source signals is greater than that of the mixed signals. Motivated by this observation, we propose an MCA-based cost function. It is further shown that the separation matrix can be obtained by maximizing the proposed cost function. Then we derive an iterative determinant maximization algorithm for estimating the separation matrix. In the case of two sources, a closed-form solution exists and is derived. Unlike most existing blind source separation methods, the proposed MCA method needs neither the independence assumption, nor the sparseness requirement of the sources. The effectiveness of the new method is illustrated by experiments using X-ray images, remote sensing images, infrared spectral images, and real-world fluorescence microscopy images.     

Certification of Numerical Computation of the Sign of the Determinant of a Matrix

Certified computation of the sign of the determinant of a matrix is a central problem in computational geometry. Certification by known methods is practically difficult because the magnitude of the determinant of an integer input matrix A may vary dramatically, from 1 to || A || ⁿ , and the round-off error bound of the determinant computation varies proportionally. Because of such a variation, high precision computation of \det A is required to ensure that the error bound is smaller than the magnitude of the determinant. We observe, however, that our certification task of determining only a single bit of \det A , that is, the bit carrying the sign, does not require us to estimate the latter round-off error. Instead, we solve a much simpler task of computing numerically the factorization of a matrix by Gaussian elimination with pivoting (which is a subroutine of LAPACK and LINPACK) and of estimating the minimum distance 1/||A ^-1 || from A to a singular matrix. Such an estimate gives us a desired range for the round-off error of the factorization such that the invariance of the sign of det A is ensured as long as the error varies in this range. Based on these simple but novel observations, we devise new effective arithmetic filters for the certification of the sign, compare them with the known filters, and confirm the efficiency of our techniques by some numerical tests. Received March 29, 1998; revised December 14, 1998.     

Cramer法则的另一应用

求高阶行列式的值一直是数学算法中的一个难题.通过实例对Cramer法则重新进行了探讨,给出了该法则的一种新的应用,并得出了通过构造一个含有n个未知数n个方程的线性方程组计算n阶行列式值的方法.     

H矩阵的Minkowski型不等式

用具体实例指出了文献[1]中给出的H矩阵的Minkowski型不等式的错误,同时修正了文献[1]中的错误,并拓广了H矩阵的Minkowski型不等式.