2022/09/01 by Zhen Shao, Shao, Zhen
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Probability (math.PR) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2209.01006
openalex publication_date 2022/09/01 · openalex created_date 2022/09/06 · openalex updated_date 2026/07/28
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_∞ to l2 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.