Randomized Subspace Learning with Structure Preservation
Devansh Arpit, Gaurav Srivastava, Venu Govindaraju · arXiv (Cornell University) · 2014
Modeling data as being sampled from a union of independent or disjoint sub-spaces has been widely applied to a number of real world applications. Recently, high dimensional data has come into focus because of advancements in computa-tional power and storage capacity. However, a number of algorithms that assume the aforementioned data model have high time complexity which makes them slow. Dimensionality reduction is a commonly used technique to tackle this problem. In this paper, we first formalize the concept of Independent Subspace Structure and then we propose two randomized algorithms (supervised and unsupervised) for subspace learning that theoretically preserve this structure for any given dataset. Under supervised setting, we show that 2K projection vectors are sufficient for structure preservation ofK class data. On the other hand for unsupervised frame-work, we show that random projection preserves this structure without the knowl-edge of labels. We support our theoretical analysis with empirical results on both synthetic and real world data. 1