QUASI-separability and hierarchical QUASI-separability in stochastic signal processing

Stochastic signal processing has reached the age of ´array processing´, where the various properties of the relevant system matrix play a predominant role in the efficiency of the filtering or estimation algorithm. Classical is the Toeplitz structure, and structures that are derived from it such as ´quasi-stationarity´. In this paper we focus on a different structure of equally great importance, namely ´quasi-separability´. We start out with an introduction to basic properties and algorithms, foremost of which is an extension of the square root algorithm known from Kalman filtering. Although extremely important and useful when applicable, in many applications the notion of quasi-separability has to be extended. We discuss two main classes of extensions, which both deal with hierarchy but in very different ways. One has been called ´hierarchical semi-separable´ or HSS, the other is of more recent date and can be termed ´hierarchies of quasi-separable form´ - they look like quasi-separable but lack the main properties. We give ways of dealing with this situation which occurs in many systems characterized by partial differential equations. An example taken from image processing (optic flow analysis) puts the problem squarely in the realm of stochastic signal processing