Subspace Learning from Extremely Compressed Measurements

2014/04/03 by Krishnamurthy, Akshay, Azizyan, Martin, Singh, Aarti
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1404.0751

Abstract

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.

Related

• On the Sample Complexity of Subspace Learning
• Compressed Covariance Estimation With Automated Dimension Learning
• Compressed Subspace Learning Based on Canonical Angle Preserving Property
• Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model
• An Approach to One-Bit Compressed Sensing Based on Probably\n Approximately Correct Learning Theory