file.pdf (410.35 kB)

Subspace Learning from Extremely Compressed Measurements

Download (410.35 kB)
journal contribution
posted on 04.04.2014 by Akshay Krishnamurthy, Martin Azizyan, Aarti Singh

We consider learning the principal subspace of a large set of vectors from an extremely small number of compressive measurements of each vector. Our theoretical results show that even a constant number of measurements per column suffices to approximate the principal subspace to arbitrary precision, provided that the number of vectors is large. This result is achieved by a simple algorithm that computes the eigenvectors of an estimate of the covariance matrix. The main insight is to exploit an averaging effect that arises from applying a different random projection to each vector. We provide a number of simulations confirming our theoretical results