Fast subspace decomposition and its applications.

摘要

In the area of detection and estimation, there is a class of so-called signal subspace algorithms that has various applications in cellular/mobile communications, target tracking and signal estimation, system identification, ARMA modeling, adaptive filtering, among others. Though signal subspace algorithms have been shown to perform significantly better than the traditional least-squares methods, they are rarely implemented in real-time. The main reason is that they all incorporate the common key step of estimating the signal subspace, termed signal subspace decomposition, which is conventionally achieved by eigendecomposition (ED) or SVD. The ED or SVD of an M x M matrix requires at least O({dollar}Msp3{dollar}) multiplications which are quite significant for large M. They also involve global communication and significant amounts of local storage, properties that make VLSI parallel implementation difficult.; In this thesis, we present a class of Fast Subspace Decomposition (FSD) algorithms by exploiting the matrix structure associated with signal subspace algorithms. The new FSD techniques, based on the well-known Lanczos algorithm, require only O({dollar}Msp{lcub}2{rcub}d{dollar}) multiplications for an M x M matrix, where d is the dimension of the signal subspace. In the aforementioned applications, {dollar}Mll d{dollar} and FSD achieves an order of magnitude reduction in computational complexity. If the matrix under consideration has additional structure common in signal processing and communications, e.g., Toeplitz and Hankel, FSD can exploit it and achieve another order of magnitude computational reduction. New detection schemes for estimating d are also presented, which can be carried out during the process of signal subspace decomposition. More importantly, the FSD approach can be easily implemented in parallel using simple array processors, and the computation time can be reduced further to O(Md) or O(log Md) using O(M) or O({dollar}Msp2{dollar}) multipliers. The computational efficiency of FSD and its ease of implementation shed light on real-time implementations of various signal subspace algorithms.; Rigorous performance analysis FSD has also been carried out. Unlike many fast algorithms that trade performance for speed, the performance analysis shows that FSD has the same asymptotic performance as its more costly counterparts, ED and SVD, and that the new detection schemes are strongly consistent.