Restricted Isometry Property of Gaussian Random Projection for Finite Set of Subspaces

摘要

Dimension reduction plays an essential role when decreasing the complexity ofsolving large-scale problems. The well-known Johnson-Lindenstrauss (JL) Lemmaand Restricted Isometry Property (RIP) admit the use of random projection toreduce the dimension while keeping the Euclidean distance, which leads to theboom of Compressed Sensing and the field of sparsity related signal processing.Recently, successful applications of sparse models in computer vision andmachine learning have increasingly hinted that the underlying structure of highdimensional data looks more like a union of subspaces (UoS). In this paper,motivated by JL Lemma and an emerging field of Compressed Subspace Clustering(CSC), we study for the first time the RIP of Gaussian random matrices for thecompression of two subspaces based on the generalized projection $F$-normdistance. We theoretically prove that with high probability the affinity ordistance between two projected subspaces are concentrated around theirestimates. When the ambient dimension after projection is sufficiently large,the affinity and distance between two subspaces almost remain unchanged afterrandom projection. Numerical experiments verify the theoretical work.