Compressing finite Lp data into subpolynomially many coordinates

← All digests

Family 094 · Convex and metric geometry
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-14

1. The question

A collection of data points may live in a space with thousands of coordinates, even when only their pairwise distances matter. Dimension reduction asks whether the points can be repositioned in fewer coordinates while approximately preserving every distance.

For Euclidean distance, the Johnson–Lindenstrauss lemma gives a remarkable answer: a fixed distortion above one requires only a constant times $\log n$ coordinates for $n$ points. What remains true when distance is measured by a different $L^p$ norm?

The manuscript in family 094 claims that, for every fixed $1<p<\infty$, a finite $n$-point subset of real $L^p$ can be embedded into the same type of coordinate space using $n^{o(1)}$ dimensions. The distortion may be any fixed number greater than one. The map need not be linear, and that freedom is essential.

2. Background and essential definitions

In $\ell_p^d=\mathbb R^d$, the norm is

$$\|x\|_p=\left(\sum_{j=1}^d|x_j|^p\right)^{1/p}.$$

An $L^p$ space replaces the sum by an integral. Its elements may be functions rather than finite coordinate vectors. The target in this theorem is specifically a finite coordinate space with the same exponent $p$.

An embedding of points $x_1,\ldots,x_n$ has distortion at most $D$ if there are target points $y_i$ and a common scale $s>0$ such that

$$s\|x_i-x_j\|_p\leq\|y_i-y_j\|_p \leq Ds\|x_i-x_j\|_p$$

for every pair. The common rescaling does not affect distortion. At $D=1$, all distances are preserved exactly up to that scale.

Let $d_p(n,D)$ be the smallest dimension that works for every such $n$-point set. It is a worst-case quantity: some individual sets, such as points on a line, need far fewer coordinates.

The notation $n^{o(1)}$ means growth slower than every fixed positive power of $n$. Equivalently, $\log d/\log n\to0$. It does not mean a bounded dimension or necessarily a logarithmic one. For example, $\exp(C\sqrt{\log n})$ is subpolynomial, but eventually exceeds every fixed power of $\log n$.

3. Development history and previous partial results

Johnson and Lindenstrauss’s 1984 paper established the Hilbert-space result and asked about other Banach spaces. Hilbert space corresponds to $p=2$, where inner products and random linear projections give unusually strong tools.

For exact embeddings, Ball’s Isometric embedding in lᵖ-spaces (1990) gave a coordinate upper bound of $\binom n2$, with quadratic-order sharpness in the range $1\leq p<2$. This bound reflects the number of pairwise distance constraints. Allowing a small distortion can change the problem dramatically.

Below two, Schechtman developed approximate finite-set bounds, eventually reaching a dimension proportional to $n$ for fixed parameters. Other classical results discretize an entire finite-dimensional linear subspace of $L^p$. Those must preserve every vector in the subspace, whereas the present problem only asks to preserve distances between the selected points.

Linearity creates another restriction. For $p\ne2$, fixed-distortion linear maps on some finite configurations require dimension proportional to the number of points. A nonlinear repositioning is not covered by those lower bounds.

At $p=1$, Brinkman and Charikar’s impossibility theorem obstructs strong dimension reduction even for nonlinear maps. The new theorem excludes that endpoint. For $p>2$, a 2026 lower bound of Naor and Ren rules out a universal logarithmic coordinate bound at fixed distortion. A subpolynomial upper bound is compatible with that obstruction.

The manuscript’s method uses electrical-flow localization from Gurel-Gurevich, Nachmias and Sachdeva’s 2026 paper, together with empirical sampling ideas going back to Maurey. Its contribution is a relative-error construction uniform over all pairs in an arbitrary finite configuration.

4. What the new manuscripts claim

Fix $1<p<\infty$, $p\ne2$, and define

$$\gamma(p)= \begin{cases} 2-p,&1<p<2,\\ 1-2/p,&2<p<\infty. \end{cases}$$

M1 states that for every fixed $D>1$, a finite constant $C_{p,D}$ exists such that

$$\frac{\log n}{\log(1+2D)} \leq d_p(n,D) \leq\exp\left(C_{p,D}(\log n)^{\gamma(p)}\right).$$

Because $0<\gamma(p)<1$, the upper bound is subpolynomial. For example, both $p=3/2$ and $p=4$ give the form $\exp(C_{p,D}\sqrt{\log n})$. The constants depend on the fixed exponent and distortion.

For exact embeddings with $D=1$ and $p\ne2$, M1 gives quadratic-order lower and upper bounds:

$$d_p(n,1)\asymp n^2.$$

Its lower construction also includes even integers $p>2$. Thus the logarithmic growth exponent of the necessary dimension changes from two at exact distortion to zero at every fixed distortion strictly above one.

The case $p=2$ remains governed by the stronger classical bound $d_2(n,D)=O_D(\log n)$ for $D>1$. The manuscript is an existence theorem and does not claim an efficient algorithm for finding its nonlinear embeddings.

No uniformity is asserted as $D\downarrow1$, $p\downarrow1$, or $p\to\infty$. One cannot choose these parameters to vary with $n$ and retain the same asymptotic conclusion without additional estimates.

5. Why the advance matters

Importance: 5/5. The claim would establish substantial finite-set dimension reduction throughout the open range $1<p<\infty$, while preserving the original exponent of the target norm. It addresses a longstanding extension of the Euclidean phenomenon beyond Hilbert geometry.

The contrast with exact embeddings is particularly sharp. A fixed tolerance, however small, would permit a worst-case coordinate count smaller than every positive power of the data size, whereas exact preservation can require quadratic dimension. The theorem does not say the constants are mild for a tiny tolerance, but it identifies a qualitative asymptotic transition.

The nonlinear nature of the embedding is also informative. A failure of random linear projection does not imply that the finite metric itself needs many coordinates. The points may admit a compact representation after a more flexible rearrangement.

This is a geometric existence result, rather than an immediate data-compression procedure. The upper bound is not claimed optimal, and for $p>2$ the known lower bounds already show that the Euclidean logarithmic answer cannot simply carry over unchanged.

6. The main idea

Build scalar coordinates through their pairwise increments

A single target coordinate assigns one real label $z_i$ to each point. Its normalized increment on a pair is

$$\frac{z_i-z_j}{\|x_i-x_j\|_p}.$$

Randomly choosing such labels gives random increments. If their $p$-th absolute moments are nearly equal for every pair, then repeated independent samples can serve as coordinates of a distance-preserving embedding.

The increments cannot be chosen independently on all pairs: they must come from one consistent list of vertex labels. Around a cycle, unnormalized differences must telescope to zero. Preserving this consistency is a central geometric constraint.

Replace simultaneous constraints by weighted tests

The manuscript first considers an arbitrary positive weighting of all pairs. It constructs bounded random consistent increments whose weighted average moment error is small. The crucial quantities—the common target moment and the bound on increment size—are uniform over the choice of weights.

A convex-separation argument then turns these weighted tests into one distribution whose moments work for every pair simultaneously. Independent sampling and a concentration estimate supply finitely many coordinates. This is the empirical-method step; the main challenge is constructing the bounded distribution with sufficiently favorable parameters.

Use electrical flows to repair consistency

A projection onto the space of consistent increments is built using a suitable reweighting of the complete graph on the data points. It is contractive in a weighted square norm and has a logarithmic bound in the maximum norm. Electrical-flow localization provides the input for this second estimate, and a fixed-point argument chooses compatible weights.

Below $p=2$, the random construction starts with symmetric $p$-stable variables, whose distributions interact naturally with $L^p$ distances. Their heavy tails are clipped to obtain bounded increments. Projection repairs the consistency lost during clipping, while the two norm estimates control the error.

Above $p=2$, the manuscript uses overlapping magnitude truncations and signed Poisson sampling. The overlap increases useful moment mass relative to projection error. A refined independent-sum moment estimate retains a leading coefficient arbitrarily close to one, which is necessary to allow distortions arbitrarily close to one.

Substituting the resulting moment and magnitude bounds into the sampling estimate produces the stated subpolynomial exponent. The exact-embedding lower bound follows a separate route, using configurations whose equality relations force many disjoint coordinate contributions.

7. Scope, limitations, and open questions

The input is a finite subset of a real $L^p$ space, and the target is real $\ell_p^d$. The map may depend on the entire finite set and need not extend linearly, or even be defined, on the surrounding space.

The number of points $n$ is different from the dimension of their linear span. A theorem about all vectors in a subspace cannot be substituted for this finite-distance statement. Conversely, preserving the finite set does not preserve its span.

The endpoint $p=1$ is excluded, as is $p=\infty$. For fixed interior $p$, the bound remains subpolynomial but may approach polynomial-looking behavior over finite ranges when $p$ is near an endpoint. The theorem gives no practical complexity guarantee.

An infinite doubling subset of Hilbert space may fail to embed into any fixed finite-dimensional Euclidean space, as addressed separately in family 098. There is no contradiction: the finite-set dimension bound is allowed to grow with cardinality.

Determining the optimal dimension dependence and constructing efficient embeddings remain further questions. The digest takes the manuscript’s estimates as stated without verifying its probabilistic or electrical-flow arguments.

8. Sources and further reading

M1 states the approximate and exact dimension bounds, develops the weighted-moment criterion, and treats the two exponent ranges separately. Its appendices record the electrical-flow and refined moment estimates used in the construction.

The linked Johnson–Lindenstrauss and Brinkman–Charikar papers mark the classical positive Hilbert result and the negative $L^1$ endpoint. Naor’s survey of metric dimension reduction explains the distinctions between finite coordinate targets, arbitrary subspaces and linear embeddings.

Source manuscripts

• M1. OpenAI, Subpolynomial dimension reduction in Lp (September 23, 2026).

Sources consulted on 14 October 2026 at repository revision 1581d4c. Download the manuscript citations.