Convergence of a randomized sampling method for identifying a subspace of R^n.

Research on incremental gradient algorithms and gradient algorithms on manifolds are both gaining popularity in the last decade; incremental gradient because of its speed, adaptivity to realtime data, and low storage requirements, and manifold modeling in general because of its generality while still maintaining a belief that high-dimensional data may exhibit some structure that we can leverage for prediction and estimation. In this talk I'll briefly review some of the convergence results in those areas that we all should know. Then I will discuss convergence of the GROUSE algorithm for identifying subspaces. GROUSE takes as input a sequence of vectors which, as a collection, lie in a fixed subspace. Each vector is observed only on a subset of the vector's coordinates. The algorithm generates a sequence of orthonormal matrices whose columns span the latest estimate of the subspace. We present a local convergence analysis for the case in which both the vector and the subset of observed coordinates are selected randomly and independently at each iteration, showing that the method exhibits an almost linear convergence rate. Additionally, we describe the relationship between GROUSE and methods of incremental SVD type.