An improved fully parallel stochastic gradient algorithm for subspace tracking

A new algorithm is presented for principal component analysis 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 literature. 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 O(Ν·κ) operations per update instead of O(N · κ²), where N is the dimension of the input vector and κ is the number of principal components to be estimated. A parallel version with O(κ) parallelism (processors) and throughput O(N∼¹) and is straightforwardly derived. A fully parallel version, with throughput independent of the problem size (O(1)), may be obtained at the expense of O(N²) additional operations.