Abstract
Convergence of a Randomized Sampling Method for Identifying a Subspace of R^n.
Stephen Wright
University of Wisconsin-Madison
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.
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.
No video available