Fast multiscale statistical signal processing algorithms

It is shown that a large set of (non necessarily stationary) correlation matrices may be transformed into a matrix that consists of essentially banded subblocks. The transformation is accompanied by pre- and postmultiplication with an orthogonal matrix whose elements are derived from the impulse responses of a suitably designed cascade of alias free multirate analysis filter banks. It is further proved that the Cholesky factor of the transformed matrix also consists of essentially banded subblocks. These two observations are combined to show that the linear positive definite systems of equations that arise in statistical signal processing can be solved in O(max{N log ²(N), N²}) operations while matrix-vector multiplication steps may be implemented in O(n log (N)) operations. An error analysis of the proposed linear positive definite system solver is also provided