IMPROVED FAST ADAPTIVE SUBSPACE TRACKING

A new subspace tracking algorithm which gives accurate estimates of the r largest singular values and corresponding left singular vectors of overlapping rectangular matrices is presented. This algorithm has evolved from the Fast Ap-proximate Subspace Tracking (FAST) algorithm by Real, Tufts, and Cooley, but has significantly better accuracy and computational efficiency. When there are abrupt changes in data, or the data is changing rapidly, a rectangular window can often give better performance than an exponential window because it can limit exactly how much older data is included. Some methods for estimating the signal subspace dimension require the singular values of the strong subspace. This algorithm can update the r largest singular values and corresponding left singular vectors in O(nr2), where n is the number of channels and r is the dimension of the strong subspace that we are tracking. There are no assumptions made about the strong subspace, but the accuracy of our singular vector and singular value estimates is related to the separation between the strong ”signal ” subspace and the weak ”noise ” subspace, which is just the signal to noise ratio. In this paper we present, (a) why this algorithm works, (b) why it is fast, and (c) how to use it to track a strong subspace. 1