Fastiterative methods for least squares estimations

Least squares estimations have been used extensively in many applications, e.g. system identification and signal prediction. When the stochastic process is stationary, the least squares estimators can be found by solving a Toeplitz or near-Toeplitz matrix system depending on the knowledge of the data statistics. In this paper, we employ the preconditioned conjugate gradient method with circulant preconditioners to solve such systems. Our proposed circulant preconditioners are derived from the spectral property of the given stationary process. In the case where the spectral density functions() of the process is known, we prove that ifs() is a positive continuous function, then the spectrum of the preconditioned system will be clustered around 1 and the method converges superlinearly. However, if the statistics of the process is unknown, then we prove that with probability 1, the spectrum of the preconditioned system is still clustered around 1 provided that large data samples are taken. For finite impulse response (FIR) system identification problems, our numerical results show that annth order least squares estimator can usually be obtained inO(n logn) operations whenO(n) data samples are used. Finally, we remark that our algorithm can be modified to suit the applications of recursive least squares computations with the proper use of sliding window method arising in signal processing applications.Research supported in part by HKRGC grant no. 221600070, ONR contract no. N00014-90-J-1695 and DOE grant no. DE-FG03-87ER25037.     

Complete solutions of a family of quartic Thue and index form equations

Continuing the recent work of the second author, we prove that the diophantine equation

for has exactly 12 solutions except when , when it has 16 solutions. If denotes one of the zeros of , then for we also find all with .

     

Almost linearity of -bi-Lipschitz maps between real Banach spaces

Let and be real Banach spaces. A map between and is called an -bi-Lipschitz map if for all . In this note we show that if is an -bi-Lipschitz map with from onto , then is almost linear. We also show that if is a surjective -bi-Lipschitz map with , then there exists a linear isomorphism such that

where as and .

     

An Arithmetic Reduction of Finite Rank 3 Geometries with Linear Spaces as Plane Residues and with Dual Linear Spaces as Point Residues

Let be a rank three incidence geometry of points, lines and planes whose planes are linear spaces and whose point residues are dual linear spaces (notice that we do not require anything on the line residues). We assume that the residual linear spaces of belong to a natural class of finite linear spaces, namely those linear spaces whose full automorphism group acts flag-transitively and whose orders are polynomial functions of some prime number. This class consists of six families of linear spaces. In the amalgamation of two such linear spaces imposes an equality on their orders leading, in particular, to a series of diophantine equations, the solutions of which provide a reduction theorem on the possible amalgams of linear spaces that can occur in .We prove that one of the following holds (up to a permutation of the words point and plane):A) the planes of and the dual of the point residues belong to the same family and have the same orders,B) the diagram of is in one of six families,C) the diagram of belongs to a list of seven sporadic cases.Finally, we consider the particular case where the line residues of are generalized digons.     

A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.     

On representations of affine Kac-Moody groups and related loop groups

We demonstrate a one to one correspondence between the irreducible projective representations of an affine Kac-Moody group and those of the related loop group, which leads to the results that every non-trivial representation of an affine Kac-Moody group must have its degree greater than or equal to the rank of the group and that the equivalence appears if and only if the group is of type for some . Moreover the characteristics of the base fields for the non-trivial representations are found being always zero.

     

Primal-dual interior point approach for computingl 1-solutions andl ∞-solutions of overdetermined linear systems

This paper concerns solving an overdetermined linear systemA ^T x=b in the leastl ₁-norm orl -norm sense, whereA ^m×n ,m<n. We show that the primal-dual interior point approach for linear programming can be applied, in an effective manner, to linear programming versions of thel ₁ andl -problems. The resulting algorithms are simple to implement and can attain quadratic or superlinear convergence rate. At each iteration, the algorithms must solve a linear system with anm×m positive-definite coefficient matrix of the formADA ^T , whereD is a positive diagonal matrix. The preliminary numerical results indicate that the proposed algorithms offer considerable promise.This research was supported in part by Grants NSF DMS-91-02761 and DOE DE-FG05-91-ER25100.     

Interior-point algorithm for quadratically constrained entropy minimization problems

In this paper, we develop an interior point algorithm for quadratically constrained entropy problems. The algorithm uses a variation of Newton's method to follow a central path trajectory in the interior of the feasible set. The primal-dual gap is made less than a given in at most steps, wheren is the dimension of the problem andm is the number of quadratic inequality constraints.     

On the Landau-Teller approximation for energy exchanges with fast degrees of freedom

We revisit the Landau-Teller heuristic approach to adiabatic invariants and, following Rapp, use it to investigate the energy exchanges between the different degrees of freedom, in simple Hamiltonian systems describing the collision of fast rotating or vibrating molecules with a fixed wall. We critically compare the theoretical results with particularly accurate numerical computations (quite small energy exchanges, namely of one part over 10³⁰, are measured).     

RELATIONSHIPS BETWEEN X—H STRETCHING OVERTONE FREQUENCIES AND BOND LENGTHS/BOND ANGLES

A relationship between the X-H (X = N, O, C, and so on) equilibrium bond length in a Morse oscillator and the X-H stretching overtone frequency shifts is obtained theoretically. We use the equation to discuss the empirical linear relationships that have been proposed for heterocyclics, alkanes and fluorinated benzenes. On the other hand, a unified relationship between the X-H bond angles and the experimental quantities (ω(?) and the coupling strength λ) is also presented for XH2, XH, and XH4 molecules or molecular fragments. Calculations of X-H bond angles for a number of molecules show that the results from our equations are in excellent agreement with the experimental values. Also we can extract the information of relative magnitude of bond coupling force field.