Convergence of a Randomized Sampling Method for Identifying a Subspace of R^n.

Stephen Wright
University of Wisconsin-Madison
Computer Science

The GROUSE algorithm for identifying a subspace 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 methods of incremental SVD type.

Presentation (PDF File)

Back to Structure and Randomness in System Identification and Learning