Subspace Learning from Extremely Compressed Measurements
  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.
