It takes of the order of N3 operations to solve a set of N linear equations in N unknowns or to invert the corresponding coefficient matrix. When the underlying physical problem has some time- or shift-invariance properties, the coefficient matrix is of Toeplitz (or difference or convolution) type and it is known that it can be inverted with O(N2) operations. However non-Toeplitz matrices often arise even in problems with some underlying time-invariance, e.g., as inverses or products or sums of products of possibly rectangular Toeplitz matrices. These non-Toeplitz matrices should be invertible with a complexity between O(N2) and O(N3). In this paper we provide some content for this feeling by introducing the concept of displacement ranks, which serve as a measure of how 'close' to Toeplitz a given matrix is.

In this part, a comparison between the different state-space models is presented. We discuss proper definitions of state, controllability and observability and their relations to minimality of 2-D systems. We also present new circuit realizations and 2-D digital filter hardware implementation of 2-D transfer functions.

Recursive least squares ladder estimation algorithms have attracted much attention recently because of their excellent convergence behavior and fast parameter tracking capability, compared to gradient based algorithms. We present some recently developed square root normalized exact least squares ladder form algorithms that have fewer storage requirements, and lower computational requirements than the unnormalized ones. A Hilbert space approach to the derivations of magnitude normalized signal and gain recursions is presented. The normalized forms are expected to have even better numerical properties than the unnormalized versions. Other normalized forms, such as joint process estimators (e.g., "adaptive line enhancer") and ARMA (pole-zero) models, will also be presented. Applications of these algorithms to fast (or "zero") startup equalizers, adaptive noise- and echo cancellers, non-Gaussian event detectors, and inverse models for control problems are also mentioned.

We describe several interconnections between the topics mentioned in the title. In particular, we show how some previously known formulas for inverting Toeplitz operators in both discrete- and continuous- time can be interpreted as versions of the Christoffel-Darboux formula for the biorthogonal Szegö and Krein polynomials on the circle and the line, respectively. The discrete-time inversion result is often known as Trench’s formula, while the continuous-time result was apparently first deduced (in radiative transfer theory) by Sobolev. The concept of innovations is used to motivate the definitions of the Szego and especially the Krein orthogonal functionals, and connections to work on the fitting of autoregressive models and inversion of the associated covariance matrices are also noted. This review was motivated by the hope that the nice properties of Toeplitz operators extend to certain classes of non-Toeplitz operators.

A sequence of vectors {x(t)} with dimension N is given, such that x(t+1) is obtained from x(t) by introducing p new elements, deleting p old ones, and shifting the others in some fashion. The sequence of vectors $ is sought. This paper presents a method of calculating these vectors with proportional-to-Np operations and memory locations, in contrast to the conventional way which requires proportional-to-N 2 operations and memory locations. A non-symmetric case is also treated.