Simple, unified analysis of Johnson-Lindenstrauss with applications
We present a simplified and unified analysis of the Johnson-Lindenstrauss (JL) lemma, a cornerstone of dimensionality reduction for managing high-dimensional data. Our approach simplifies understanding and unifies various constructions under the JL framework, including spherical, binary-coin, sparse JL, Gaussian, and sub-Gaussian models. This unification preserves the intrinsic geometry of data, essential for applications from streaming algorithms to reinforcement learning. We provide the first rigorous proof of the spherical construction's effectiveness and introduce a general class of sub-Gaussian constructions within this simplified framework. Central to our contribution is an innovative extension of the Hanson-Wright inequality to high dimensions, complete with explicit constants. By using simple yet powerful probabilistic tools and analytical techniques, such as an enhanced diagonalization process, our analysis solidifies the theoretical foundation of the JL lemma by removing an independence assumption and extends its practical applicability to contemporary algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionLEMMASimilar Papers 제목 키워드 기반
Simple Analysis of Johnson-Lindenstrauss Transform under Neuroscience Constraints
The paper re-analyzes a version of the celebrated Johnson-Lindenstrauss Lemma, in which matrices are subjected to constraints that naturally emerge from neuroscience applications: a) sparsity and b) sign-consistency. Thi…
LEMMADimensionality reduction with subgaussian matrices: a unified theory
We present a theory for Euclidean dimensionality reduction with subgaussian matrices which unifies several restricted isometry property and Johnson-Lindenstrauss type results obtained earlier for specific data sets. In p…
Dimensionality ReductionToward a unified theory of sparse dimensionality reduction in Euclidean space
Let $\Phi\in\mathbb{R}^{m\times n}$ be a sparse Johnson-Lindenstrauss transform [KN14] with $s$ non-zeroes per column. For a subset $T$ of the unit sphere, $\varepsilon\in(0,1/2)$ given, we study settings for $m,s$ requi…
compressed sensingDimensionality ReductionLEMMAClark Hash: Stateless Sparse Johnson-Lindenstrauss Quantization for Neural Embeddings
Clark Hash is a small method for storing neural embeddings in less space. It normalizes each database vector, applies a deterministic sparse signed Johnson-Lindenstrauss projection, clips the result, and stores a fixed-w…
Randomized Projection Learning Method forDynamic Mode Decomposition
A data-driven analysis method known as dynamic mode decomposition (DMD) approximates the linear Koopman operator on projected space. In the spirit of Johnson-Lindenstrauss Lemma, we will use random projection to estimate…
LEMMA