Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noise
This work addresses dimensionality reduction challenges in high-dimensional noisy data, offering a novel perspective that treats noise as beneficial, though it is incremental in extending existing embedding methods.
The paper tackles the problem of dimensionality reduction for noisy vectors using sparse embeddings like subsampling and hashing, showing that noise can be exploited to relax constraints on vector properties, leading to similar performance as dense embeddings with theoretical bounds and numerical improvements.
This paper investigates theoretical properties of subsampling and hashing as tools for approximate Euclidean norm-preserving embeddings for vectors with (unknown) additive Gaussian noises. Such embeddings are sometimes called Johnson-lindenstrauss embeddings due to their celebrated lemma. Previous work shows that as sparse embeddings, the success of subsampling and hashing closely depends on the $l_\infty$ to $l_2$ ratios of the vector 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 approximate norm-preserving dimensionality-reduction properties. The key is that the noise should be treated as an information to be exploited, not simply something to be removed. Theoretical bounds for subsampling and hashing to recover the approximate norm of a high dimension vector in the presence of noise are derived, with numerical illustrations showing better performances are achieved in the presence of noise.