2022/12/13 by Moretti, Simone, Paolo Pellizzoni, Pellizzoni, Paolo +2
Engineering · Mathematics · Medicine · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Medical Imaging Techniques and Applications #Numerical methods in inverse problems #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2212.06605
openalex publication_date 2022/12/13 · openalex created_date 2022/12/27 · openalex updated_date 2026/07/28
The weighted Euclidean norm ‖x‖w of a vector x∈ ℝd with weights w∈ ℝd is the Euclidean norm where the contribution of each dimension is scaled by a given weight. Approaches to dimensionality reduction that satisfy the Johnson-Lindenstrauss (JL) lemma can be easily adapted to the weighted Euclidean distance if weights are known and fixed: it suffices to scale each dimension of the input vectors according to the weights, and then apply any standard approach. However, this is not the case when weights are unknown during the dimensionality reduction or might dynamically change. In this paper, we address this issue by providing a linear function that maps vectors into a smaller complex vector space and allows to retrieve a JL-like estimate for the weighted Euclidean distance once weights are revealed. Our results are based on the decomposition of the complex dimensionality reduction into several Rademacher chaos random variables, which are studied using novel concentration inequalities for sums of independent Rademacher chaoses.