Fast Signal-subspace Decomposition without Eigendecompositiont
Thomas Icailath · 1990
Many m odern algorithms in various signal procrssirig areas, e.g. spectral e stimation, array signal pro- cessing, system identification, arid speccli processiiig, re- qirire n signnl suhpnce dc?coiril)osit,ir,ii, wliicli is coiiveii- tionally accoinplislied by an eigeiidecoriipositioii. Since the eigentiecoinpoPitioii is very coinputatioiially intensive (0(M3) flops for an AfxM matrix) aiid difficnlt to irnple- rrient, it imposes a fundamental harrier for real-tiiiie ini- plernent,at.iom of these lrigli-performa~ice algorit,hrris. In this paper, we present a fast aiid parallel approach for the sigii nl sli bspaw tlccom posi t ion iuitho IL t an eigeiid eroiii posi- t,ioti. The new tecliriiqiie teriiied FSD, exploits the iiiatrix st.riictiire associated with signal subspace algorithins and requires only O(M2d) flops, where d(< M) denotes tIic Fig- rial subspace dinieiision. Our new approach can be easily irnplpirieirted in parallel to further reduce the coinpiita- tioti time to as sinal1 as O(Md) or O(logAfd) by usiiig O(Af) or O(AP) niiiitipliers respectively.