Invariance principle of random projection for the norm
Johnson-Lindenstrauss guarantees certain topological structure is preserved under random projections when project high dimensional deterministic vectors to low dimensional vectors. In this work, we try to understand how random matrix affect norms of random vectors. In particular we prove the distribution of the norm of random vector $X \in \mathbb{R}^n$, whose entries are i.i.d. random variables, is preserved by random projection $S:\mathbb{R}^n \to \mathbb{R}^m$. More precisely, \[ \frac{X^TS^TSX - mn}{\sqrt{\sigma^2 m^2n+2mn^2}} \xrightarrow[\quad m/n\to 0 \quad ]{ m,n\to \infty } \mathcal{N}(0,1) \] We also prove a concentration of the random norm transformed by either random projection or random embedding. Overall, our results showed random matrix has low distortion for the norm of random vectors with i.i.d. entries.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Simple, Fast and Efficient Injective Manifold Density Estimation with Random Projections
We introduce Random Projection Flows (RPFs), a principled framework for injective normalizing flows that leverages tools from random matrix theory and the geometry of random projections. RPFs employ random semi-orthogona…
Density EstimationJohnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey
This is a tutorial and survey paper on the Johnson-Lindenstrauss (JL) lemma and linear and nonlinear random projections. We start with linear random projection and then justify its correctness by JL lemma and its proof. …
Dimensionality ReductionLEMMAEfficient Hyperparameter Tuning via Trajectory Invariance Principle
As hyperparameter tuning becomes increasingly costly at scale, efficient tuning methods are essential. Yet principles for guiding hyperparameter tuning remain limited. In this work, we seek to establish such principles b…
Random Projections and Natural Sparsity in Time-Series Classification: A Theoretical Analysis
Time-series classification is essential across diverse domains, including medical diagnosis, industrial monitoring, financial forecasting, and human activity recognition. The Rocket algorithm has emerged as a simple yet …
Activity Recognitioncompressed sensingComputational EfficiencyHuman Activity Recognition+3Interpreting Equivariant Representations
Latent representations are used extensively for downstream tasks, such as visualization, interpolation or feature extraction of deep learning models. Invariant and equivariant neural networks are powerful and well-establ…
Graph Generationimage-classificationImage ClassificationInductive Bias