Advances in sliding window subspace tracking

This dissertation is concerned with the task of efficiently and accurately tracking the singular values and left singular vectors of a rapidly changing dominant column space of a matrix, in which a column of the matrix is replaced each time step. As part of this task, the dimension of this dominant subspace is determined automatically for each time step. Two methods for determining the singular values and left singular vectors of this dominant columnspace are presented. The first method, which is an exact method, will update all of the singular values and left singular vectors using the rank-two secular function. The derivation of this function, and its properties, are original contributions of this dissertation. This method requires a single O(n3) matrix product to rotate the singular vectors using direct multiplication, and all other computation is O(n2). The second method, the Improved Fast Adaptive Subspace Tracking (IFAST) method, will give accurate approximations of the r largest singular values and corresponding left singular vectors in O( nr2) time. An accuracy analysis of the approximation error of the second method, using the rank-two secular function from the first method, is presented. The block Hankel matrix structure is presented, which can give improved SNR for exponential signals in sensor arrays, at the expense of beam-width. The two rank determination methods of Shah and Tufts, where one is for time-series (Hankel) data and the other is for unstructured sensor array data, are combined into a single general method which works with unstructured, Hankel, and block Hankel matrices. An efficient way to calculate the thresholds used by this method is presented, allowing use in real-time applications