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

Laura Balzano
University of Michigan
Electrical and Computer Engineering

Laura Balzano (speaker) and Stephen Wright 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 Adaptive Data Analysis and Sparsity