Rigorous restricted isometry property of low-dimensional subspaces

DOI10.1016/J.ACHA.2019.11.002zbMATH Open1448.94067OpenAlexW2988189944MaRDI QIDQ778034FDOQ778034

Authors: Gen Li, Y. T. Gu, Qing-hua Liu 

Publication date: 30 June 2020

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: Dimensionality reduction is in demand to reduce the complexity of solving large-scale problems with data lying in latent low-dimensional structures in machine learning and computer version. Motivated by such need, in this work we study the Restricted Isometry Property (RIP) of Gaussian random projections for low-dimensional subspaces in $mathbb{R}^N$, and rigorously prove that the projection Frobenius norm distance between any two subspaces spanned by the projected data in $mathbb{R}^n$ ($n<N$) remain almost the same as the distance between the original subspaces with probability no less than $1-{me}^{-mathcalO(n)}$. Previously the well-known Johnson-Lindenstrauss (JL) Lemma and RIP for sparse vectors have been the foundation of sparse signal processing including Compressed Sensing. As an analogy to JL Lemma and RIP for sparse vectors, this work allows the use of random projections to reduce the ambient dimension with the theoretical guarantee that the distance between subspaces after compression is well preserved.

Full work available at URL: https://arxiv.org/abs/1801.10058

Recommendations

• Random projections of smooth manifolds
• Dimensionality reduction with subgaussian matrices: a unified theory
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Randomized large distortion dimension reduction
• Tighter bounds for random projections of manifolds

zbMATH Keywords

dimensionality reductionsubspace clusteringrandom projectionrestricted isometry propertyGaussian random matrixlow-dimensional subspaces

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52) Applications of operator theory in systems, signals, circuits, and control theory (47N70)

Cites Work

• Title not available (Why is that?)
• A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data
• A geometric analysis of subspace clustering with outliers
• A simple proof of the restricted isometry property for random matrices
• Compressed sensing
• Decoding by Linear Programming
• Dimensionality reduction with subgaussian matrices: a unified theory
• Dimensionality-reduced subspace clustering
• Embeddings of surfaces, curves, and moving points in euclidean space
• Extensions of Lipschitz mappings into a Hilbert space
• Information Theoretic Bounds for Compressed Sensing
• Jordan's principal angles in complex vector spaces
• Local operator theory, random matrices and Banach spaces.
• New analysis of manifold embeddings and signal recovery from compressive measurements
• Numerical Methods for Computing Angles Between Linear Subspaces
• Restricted Isometry Property of Gaussian Random Projection for Finite Set of Subspaces
• Robust Subspace Clustering via Thresholding
• Robust dimension reduction, fusion frames, and Grassmannian packings
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
• Sparsity and incoherence in compressive sampling
• The Geometry of Algorithms with Orthogonality Constraints
• The restricted isometry property and its implications for compressed sensing
• What happens to a manifold under a bi-Lipschitz map?

Cited In (5)

• Dimensionality reduction with subgaussian matrices: a unified theory
• Random projections of smooth manifolds
• A lower bound on the error in dimensionality reduction resulting from projection onto a restricted subspace
• Certifying the Restricted Isometry Property is Hard
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property

This page was built for publication: Rigorous restricted isometry property of low-dimensional subspaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778034)