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 distrib...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-07
Main Authors: Duan, Juntao, Popescu, Ionel, Matzinger, Heinrich
Format: Article
Language:English
Subjects:
Norms
Random variables
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422