Robustness Properties of Dimensionality Reduction with Gaussian Random Matrices
For researchers in compressed sensing and dimensionality reduction, this work provides theoretical guarantees for robustness against row erasures, which is important for applications with missing data.
This paper studies the robustness of dimensionality reduction using Gaussian random matrices with erased rows, deriving optimal erasure ratios for norm preservation and establishing robust Johnson-Lindenstrauss lemma and restricted isometry property (RIP) with corruption. It also provides sharp bounds for norm distortion rates under erasure, leading to strong RIP with near-optimal constants for phaseless compressed sensing.
In this paper we study the robustness properties of dimensionality reduction with Gaussian random matrices having arbitrarily erased rows. We first study the robustness property against erasure for the almost norm preservation property of Gaussian random matrices by obtaining the optimal estimate of the erasure ratio for a small given norm distortion rate. As a consequence, we establish the robustness property of Johnson-Lindenstrauss lemma and the robustness property of restricted isometry property with corruption for Gaussian random matrices. Secondly, we obtain a sharp estimate for the optimal lower and upper bounds of norm distortion rates of Gaussian random matrices under a given erasure ratio. This allows us to establish the strong restricted isometry property with the almost optimal RIP constants, which plays a central role in the study of phaseless compressed sensing.