AN UPDATING ALGORITHM FOR SUBSPACE TRACKING

In certain signal processing applications it is required to compute the null space of a matrix whose rows are samples of a signal with p components. The usual tool for doing this is the singular value decomposition. However, the singular value decomposition has the drawback that it requires O(p3) operations to recompute when a new sample arrives. In this paper, we show that a different decomposition, called the URV decomposition, is equally effective in exhibiting the null space and can be updated in O(p2) time. The updating technique can be run on a linear array of p processors in O(p) time.