Fast algorithms for multidimensional linear least-squares problems.

Abstract

The first part of this thesis concerns the development of fast algorithms for computing the linear least-squares prediction and smoothing estimates of two-dimensional random fields from noisy observations on a polar raster. These algorithms exploit an assumed Toeplitz-plus-Hankel structure of the covariance function of the random field, to reduce the enormous amount of computation that would otherwise have been required. To minimize time required, both the algorithms and hardware implementations must be taken into account as a whole. Hence, some VLSI hardware architectures are proposed to implement these highly parallelizable algorithms, to further minimize computation time. To utilize these fast algorithms, the covariance function must have a Toeplitz-plus-Hankel structure. So we propose some methods for Toeplitz-plus-Hankel approximation to the data covariance matrix. Smoothing filters are also recursively derived from the available prediction filters, with the aid of a discrete version of the Bellman-Siegert-Krein resolvent identity. The applications of these algorithms to image coding and restoration are also discussed, to demonstrate their validity. In the second part, 2-D linear prediction theory on a polar raster is further explored. A Radon transform approach is proposed to compute estimates of the 2-D power spectral density. This approach first interpolates the discrete data into continuous function using gaussian functions, computes the Radon transform of this continuous function, and applies familiar one-dimensional linear prediction techniques to each slice. This results in high-resolution spectral estimates for data defined on a polar raster. Generalizations of the lattice filter and spectral factorization problems to the polar raster are also addressed.