Extracting inherent patterns from large data using decompositions of
data matrix by a sampled subset of exemplars has found many applications
in machine learning. We propose a computationally efficient
algorithm for adaptive exemplar sampling, called fast exemplar selection
(FES). The proposed algorithm can be seen as an efficient
variant of the oASIS algorithm (Patel et al). FES iteratively selects incoherent
exemplars based on the exemplars that are already sampled.
This is done by ensuring that the selected exemplars forms a positive
definite Gram matrix which is checked by exploiting its Cholesky
factorization in an incremental manner. FES is a deterministic rank
revealing algorithm delivering a tighter matrix approximation bound.
Further, FES can also be used to exactly represent low rank matrices
and signals sampled from a unions of independent subspaces. Experimental
results show that FES performs comparable to existing
methods for tasks such as matrix approximation, feature selection,
outlier detection, and clustering.