Subspace Learning from Extremely Compressed Measurements
This addresses the challenge of efficient data compression and subspace estimation for large datasets, though it appears incremental as it builds on existing compressive sensing and subspace learning methods.
The paper tackles the problem of learning the principal subspace from vectors with extremely few compressive measurements per vector, showing that a constant number of measurements suffices for arbitrary precision as the number of vectors increases.
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.