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

Abstract

Dimension reduction plays an essential role when decreasing the complexity of solving large-scale problems. The well-known Johnson-Lindenstrauss (JL) Lemma and Restricted Isometry Property (RIP) admit the use of random projection to reduce the dimension while keeping the Euclidean distance, which leads to the boom of Compressed Sensing and the field of sparsity related signal processing. Recently, successful applications of sparse models in computer vision and machine learning have increasingly hinted that the underlying structure of high dimensional 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 the compression of two subspaces based on the generalized projection $F$-norm distance. We theoretically prove that with high probability the affinity or distance between two projected subspaces are concentrated around their estimates. When the ambient dimension after projection is sufficiently large, the affinity and distance between two subspaces almost remain unchanged after random projection. Numerical experiments verify the theoretical work.

37 pages, 11 figures

References in corpus (9)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Sparsity and Incoherence in Compressive Sampling
• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Structured Compressed Sensing: From Theory to Applications
• A geometric analysis of subspace clustering with outliers
• Time Delay Estimation from Low Rate Samples: A Union of Subspaces Approach
• Information theoretic bounds for Compressed Sensing
• Achievable Angles Between two Compressed Sparse Vectors Under Norm/Distance Constraints Imposed by the Restricted Isometry Property: A Plane Geometry Approach
• A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data

Cited by in corpus (7)

• Deep Learning Methods for Solving Linear Inverse Problems: Research Directions and Paradigms
• Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
• Rigorous Restricted Isometry Property of Low-Dimensional Subspaces
• Unraveling the Veil of Subspace RIP Through Near-Isometry on Subspaces
• Compressed Subspace Learning Based on Canonical Angle Preserving Property
• Optimal Projections for Discriminative Dictionary Learning using the JL-lemma
• Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph