Complex Dimensionality Reduction for the Estimation of Dynamically-Weighted Norms

The weighted p-norm of a vector can easily be computed when the weights are known in advance: it sufficies to scale the contribution of each component by the correspondent weight. However, such computation becomes challenging when, due to space or privacy constraints, only a compressed version of the vector is made available. This work is meant to elaborate on the paper "Dimensionality reduction on complex vector spaces for Euclidean distance with dynamic weights" by Pellizzoni, Moretti and Silvestri, which presents a dimensionality reduction technique inspired by the Johnson-Lindenstrauss Lemma to smartly compress very large vectors, while still enabling the computation of the weighted Euclidean norm. Here, an extension to compute an estimate of the generic weighted p-norms is introduced, as well as an experimental evaluation of strategies to reduce the variance of such estimators.