AN IMPROVED FULLY PARALLEL STOCHASTIC GRADIENT ALGORITHM FOR SUBSPACE TRACKING

A new algorithm is presented for principal component anal-ysis and subspace tracking, which improves upon classical stochastic gradient based algorithms (SGA) as well as several other related algorithms that have been presented in the liter-ature. The new algorithm is based on and inherits its main properties from a continuous-time algorithm, closely related to the QR flow. It gives the same estimates as classical SGA algorithms but requires only ON · κ operations per update instead of ON · κ2, where N is the dimension of the in-put vector and κ is the number of principal components to be estimated. A parallel version with Oκ parallelism (pro-cessors) and throughputON−1 and is straightforwardly de-rived. A fully parallel version, with throughput independent of the problem size (O1), may be obtained at the expense of ON2 additional operations.