FAST SUBSPACE DECOMPOSITION

Many recent signal processing techniques in various areas, e.g., array signal processing, system identification, and spectrum estimation, re quire a step of extracting the low-dimensional subspace from a large s pace. This step is usually called subspace decomposition, which is con ventionally accomplished by an eigendecomposition (ED). Since an ED re quires O(M3) flops for an M x M matrix, it may represent a barrier to the real-time implementation of these algorithms. In this paper, we pr esent a fast algorithm for signal subspace decomposition, which is ter med FSD, that exploits the special matrix structure (low-rank plus ide ntity) associated with signal subspace algorithms and requires only O( M2d) flops, where d(often << M) denotes the signal subspace dimension. Unlike most of alternatives, the dimension of the signal subspace is not assumed known apriori and is estimated as part of the procedure. M oreover, theoretical analysis has been conducted, and its results show the strong consistency of the new detection scheme and the asymptotic equivalence between FSD and ED in estimating the signal subspace. Our new approach can also exploit other matrix structure common in signal processing areas, e.g., Toeplitz or Hankel, and thus achieve another order of computational reduction. Moreover, it can be easily implement ed in parallel to reduce further the computation time to as little as O(Md) (using O(M) simple processors).