Tue, 24 Jan 2023
14:30
L3

Smoothed analysis of sparse Johnson-Lindenstrauss embeddings

Zhen Shao
Abstract

We investigate the theoretical properties of subsampling and hashing as tools for approximate Euclidean norm-preserving embeddings for vectors with (unknown) additive Gaussian noises. Such embeddings are called Johnson-Lindenstrauss embeddings due to their celebrated lemma. Previous work shows that as sparse embeddings, if a comparable embedding dimension to the Gaussian matrices is required, the success of subsampling and hashing closely depends on the $l_\infty$ to $l_2$ ratios of the vectors to be mapped. This paper shows that the presence of noise removes such constrain in high-dimensions; in other words, sparse embeddings such as subsampling and hashing with comparable embedding dimensions to dense embeddings have similar norm-preserving dimensionality-reduction properties, regardless of the $l_\infty$ to $l_2$ ratios of the vectors to be mapped. The key idea in our result is that the noise should be treated as information to be exploited, not simply a nuisance to be removed. Numerical illustrations show better performances of sparse embeddings in the presence of noise.

Geodesics in nonexpanding impulsive gravitational waves with Λ, part I
Sämann, C Steinbauer, R Lecke, A Podolský, J Classical and Quantum Gravity volume 33 issue 11 115002 (09 Jun 2016)
Global algebras of nonlinear generalized functions with applications in
general relativity
Nigsch, E Sämann, C (05 Sep 2013) http://arxiv.org/abs/1309.1451v2
The global existence, uniqueness and C^1-regularity of geodesics in
nonexpanding impulsive gravitational waves
Podolsky, J Sämann, C Steinbauer, R Svarc, R (05 Sep 2014) http://arxiv.org/abs/1409.1782v2
Geodesics in nonexpanding impulsive gravitational waves with $Λ$,
Part I
Sämann, C Steinbauer, R Lecke, A Podolský, J (16 Sep 2015) http://arxiv.org/abs/1509.04914v2
The global uniqueness and $C^1$-regularity of geodesics in expanding
impulsive gravitational waves
Podolsky, J Sämann, C Steinbauer, R Svarc, R (16 Feb 2016) http://arxiv.org/abs/1602.05020v2
Subscribe to