ON LOW-COMPLEXITY APPROXIMATION OF MATRICES

The operation of multiplication of a vector by a matrix can be represe nted by a computational scheme (or model) that acts sequentially on th e entries of the vector. The number of intermediate quantities (''stat es'') that are needed in the computations is a measure of the complexi ty of the model. If that complexity is low, then not only multiplicati on, but also other operations such as inversion, can be carried out ef ficiently using the model rather than the original matrix. In the intr oductory sections, we describe an algorithm to derive a computational model of minimal complexity that gives an exact representation of an a rbitrary upper triangular matrix. The main result of the paper is an a lgorithm for computing an approximating matrix with a model of (much) lower complexity than the original-as low as possible for a given tole rance on the approximation error. As measure for the tolerance we use a strong norm which we will call the Hankel norm. It is a generalizati on of the Hankel norm which is used in the classical model approximati on theory for complex analytical functions.