Research map / Learning theory and algorithms / Matrix and tensor methods

Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights

ICML 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: High-dimensional estimation theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a linear map from R^d to a low-dimensional complex space (random complex ±1/±i matrix) that lets weights be supplied after reduction, yielding an unbiased JL-like estimator of dynamically weighted squared Euclidean norms, backed by new concentration bounds for Rademacher chaoses.

Problem

Dimensionality reduction for Euclidean distance when weights are unknown at reduction time or change dynamically; existing JL-based methods require weights fixed beforehand and the non-linear alternative cannot estimate pairwise distances.

Approach

Use a random complex matrix with entries in {1,-1,i,-i} as a linear map; the weighted norm is estimated after weights are revealed by an estimator built from squared reduced coordinates and the squared random matrix applied to w⊙w, whose expectation equals the weighted norm. Analysis decomposes the error into Rademacher chaoses, bounded via novel tail inequalities; a sparse block variant improves

Key results

• Proves E[rho(g(x),w)] = ||x||_w^2 exactly for the complex map and gives high-probability error bound |rho - ||x||_w^2| < eps ||w||_4^2 ||x||_2^2 / Delta with k = O(max{Delta^2 ln(8/delta)/eps^2, Delta ln(8/delta)^2/eps}).
• Near-uniform block-sparse variant reduces output dimension to Theta(Delta) with Delta = Theta(sqrt(d)) for weights in [1/sqrt(zeta), sqrt(zeta)].
• Experiments with d=2*10^4 and 1000 random matrices show the sparse block map reduces estimator variance and nearly closes the gap to the non-linear JL estimator.

Measured effects reported in the paper

Surprising findings

• The natural non-linear estimator g'(x)=A(x⊙x) cannot be used for pairwise distances, while the complex linear map trades accuracy (2-norm of x instead of 4-norm) for linearity.
• For near-uniform weights the basic complex method yields no dimensionality reduction (k must be Theta(d)), motivating the block-sparse construction.

Limitations

• Multiplicative guarantee requires bounded ||x||_2^2 ||w||_4^2 / ||x||_w^2 <= Delta, which can force k=Theta(d) for near-uniform weights.
• Dimension guarantee for the block variant needs near-uniform input vectors x, which is a strong assumption on data.
• Experiments are proof-of-concept only on synthetic random vectors.

Experimental setup

Metrics: empirical distribution of estimator error variance of estimator

Baselines: non-linear JL estimator g'(x)=A(x⊙x)

Builds on: Johnson-Lindenstrauss lemma Bonami hypercontractive inequality sub-Weibull concentration

Closest papers by meaning

• Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry (NeurIPS 2025 · similarity 0.87)
• The Noisy Laplacian: a Threshold Phenomenon for Non-Linear Dimension Reduction (ICML 2025 · similarity 0.84)
• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.83)
• Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures (ICML 2025 · similarity 0.83)
• Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance (AAAI 2025 · similarity 0.83)
• Neuc-MDS: Non-Euclidean Multidimensional Scaling Through Bilinear Forms (NeurIPS 2024 · similarity 0.83)