Rigorous restricted isometry property of low-dimensional subspaces

DOI10.1016/J.ACHA.2019.11.002zbMATH Open1448.94067arXiv1801.10058OpenAlexW2988189944MaRDI 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

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

Cited In (5)

• 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
• The Restricted Isometry Property of Subsampled Fourier Matrices

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)