Subpolynomial dimension reduction in Lp

1 Introduction

The Johnson–Lindenstrauss lemma places every n-point subset of a Hilbert space in O_D(\log n) Euclidean dimensions with any prescribed distortion D>1 [11, Lemma 1]. Johnson and Lindenstrauss also asked what analogues of their lemma hold in other Banach spaces [11, Problem 3]. For other L_p spaces, the corresponding finite-metric question must be distinguished both from discretizing an entire linear subspace and from requiring the embedding itself to be linear. We study the coordinate-target version: the points may be repositioned freely, but their images must lie in \ell_p^d with the same exponent p. For the broader dimension-reduction landscape and the distinction between coordinate targets and arbitrary subspaces, see Naor [15].

All spaces and maps in this paper are real. For 1<p<\infty, an integer n\ge2, and D\ge1, let d_p(n,D) be the least integer d such that every n-point subset \{x_1,\ldots,x_n\} of any L_p space admits images y_1,\ldots,y_n\in\ell_p^d and a number s>0 satisfying

The maps are unrestricted; in particular, they need not extend linearly to the ambient space. Lemma 2.1 below shows that the same quantity results if the input sets are restricted to finite coordinate spaces \ell_p^m.

The constants in the upper bound depend on the fixed parameters p,D; no uniformity as p approaches an endpoint or D approaches 1 is asserted. For p=2, the classical Hilbert result gives the stronger bound d_2(n,D)=O_D(\log n) for every fixed D>1. The theorem is existential and does not assert an efficient embedding algorithm.

1.1 Earlier results and the exact-distortion contrast

Ball proved the exact-coordinate upper bound \binom n2 and its quadratic-order sharpness for 1\le p<2 [1]. Lemma 2.1 recalls the distance-cone and Carathéodory argument for that upper bound. The lower bound in (1.3) uses an antipodal row-and-column configuration. Its disjoint-support test is the classical equality criterion for the p-parallelogram defect [12, Corollary 2.1]; in particular, the argument includes even integers p>2.

Approximate finite-set bounds and linear-subspace discretization have different dimension parameters. Below 2, Schechtman’s finite-set estimates progressed from O_D(n\log n) coordinates to O_{p,D}(n) [22, 23]. The subspace results of Bourgain–Lindenstrauss–Milman and Talagrand instead preserve all vectors in a given r-dimensional subspace by a linear map [3, 25]. Applying such a theorem to the span of the translated data gives r\le n-1; it does not give the present subpolynomial bound in cardinality. Bourgain’s embedding of arbitrary finite metrics into Hilbert space allows distortion growing with n [2], another different guarantee.

The absence of a linearity requirement is essential: fixed-distortion linear maps on selected L_p configurations can require dimension proportional to their cardinality when p\ne2 [13, Section 3]. At the endpoint p=1, the obstruction of Brinkman–Charikar applies even to nonlinear maps; see also Lee–Naor’s proof [4, 14]. For p>2, Naor–Ren’s recent lower bound [16, Section 1.1, equation (2)] rules out O_{p,D}(\log n) coordinate dimension: along arbitrarily large cardinalities it requires dimension of order at least (\log n/(\log\log n)^2)^{p/2} at fixed distortion. This is compatible with (1.2); neither its upper exponent nor its elementary logarithmic lower bound is asserted to be optimal.

The dependence on cardinality also distinguishes this problem from embedding one infinite space into a fixed finite-dimensional target. A metric space is doubling if every ball can be covered by a fixed number of balls of half its radius. A separate construction gives an infinite doubling subset of real Hilbert space with no bi-Lipschitz embedding into any finite-dimensional Euclidean space at any finite distortion [17]. This is compatible with finite-set dimension reduction and is not an input to our proof.

1.2 Method and organization

Our starting point is a bounded distribution of scalar images of the input points. After dividing each increment by the corresponding original distance, we seek nearly equal pth moments for every pair. Lemma 3.1 reduces this simultaneous requirement to a weighted-average condition for each strictly positive probability on the pairs. Crucially, the common moment b and magnitude bound K are uniform over those probabilities. Convex separation produces one distribution working for all pairs; independent sampling then supplies the coordinates of a finite embedding. This sampling step belongs to Maurey’s empirical method, as presented by Pisier [19]. A close distance-matrix antecedent is Eskenazis’s use of that method for incompressible sets [6, Sections 1.3 and 2.1]; that theorem controls additive errors, with a bound depending on the incompressibility of the data. Here the weighted-moment construction supplies the uniform relative control needed for arbitrary configurations.

The geometric input in Section 4 is a projection onto normalized increments that come from scalar labels on the points. It is an L_2 contraction for a suitable choice of pair weights, and its L_\infty norm is O(\log n). We obtain the latter property by a fixed-point reweighting of the electrical-flow localization estimate of Gurel-Gurevich, Nachmias, and Sachdeva [7, Theorem 1.3]. Their estimate improves the earlier O(\log^2 n) localization bound of Schild–Rao–Srivastava [24, Theorem 1.5, preprint version]. Appendix A presents the heat-kernel and entropy proof from [7, Sections 2–4] in our notation.

After the common homogeneous-increment and signed-Poisson setup, the two ranges require different random increments. Section 6 constructs symmetric p-stable marginals, clips them, and projects back to consistent increments. Stable projections and truncated heavy-tail moments have earlier geometric uses, including Indyk’s work [10]; the required marginal construction and tail bounds are proved here. For p>2, Section 7 uses overlapping magnitude truncations followed by signed Poisson sampling. Their overlap enlarges the input energy relative to the projection error. The moment comparison is of Rosenthal type [21, 18]; Appendix B proves the specific leading coefficient 1+\epsilon needed for distortion arbitrarily close to one. The final main-text section inserts the resulting b,K into the sampling estimate and proves the packing and exact embedding lower bounds.

We use finite-dimensional convexity, Brouwer’s fixed-point theorem, and standard probability; the specialized electrical-localization and Poisson-moment arguments are supplied in the appendices.

Throughout, logarithms are natural. Constants C,c>0 are absolute; subscripts indicate the parameters on which a constant may depend. Their values may change from line to line.

2 Finite coordinates and normalized increments

For the upper bound in (1.2), we may therefore fix distinct points x_1,\ldots,x_n\in\ell_p^m for some finite m. Give the complete graph on \{1,\ldots,n\} an arbitrary orientation, and use e=ij to denote an edge with this ordering. Set

We call elements of V normalized gradients. Each such vector determines scalar labels z_i uniquely after imposing z_n=0; this choice is linear in the vector. Thus a collection of normalized gradients can always be used as the coordinates of one map on the given points.

For a strictly positive probability vector \sigma=(\sigma_e)_{e\in E}, write

We first state the moment criterion that our random gradients must satisfy.

3 From weighted moments to an embedding

A random normalized gradient gives candidate scalar coordinates. We seek one bounded distribution whose pth moments are nearly equal on every edge. The next lemma shows that it is enough to meet each weighted test separately, even though the distribution may change with the test probability. The common moment and magnitude bound must remain fixed.

The common moment b below is allowed to grow: multiplying all distances by the same factor does not change distortion. This freedom will let us absorb an additive error in the moment estimates.

4 A projection with controlled row sums

The projection estimate follows from the electrical-flow localization theorem of Gurel-Gurevich, Nachmias, and Sachdeva [7, Theorem 1.3]. For a matrix T, write |T| for its entrywise absolute value.

The proof is given in Appendix A.

We now apply this estimate to the normalized-gradient space V. Set

For the rest of the upper-bound argument, fix D>1 and choose 0<\eta<1/6 so that

For each strictly positive test probability \lambda, we will use \sigma and P from Lemma 4.2. It suffices to construct F with weighted error at most \eta b/2 under \sigma, since \lambda\le2\sigma coordinatewise. The parameters b and K will depend only on p,\eta,n.

5 Homogeneous increments and signed Poisson sampling

The following measure gives every normalized increment the same magnitude distribution. On \Omega=(0,\infty)\times\{1,\ldots,m\}, set

For every (r,t), the vector v(r,t) belongs to V. Since \sum_{t=1}^m|g_e(t)|^p=1, direct integration gives

More generally, for every nonnegative measurable function \phi:(0,\infty)\to[0,\infty],

In particular, \nu(\max_e|v_e|>a)\le|E|a^{-p}. The measure \nu is not a probability measure. The second moment of the small jumps is finite precisely when p<2; for p>2, the useful finite second moment is instead in the large jumps. This leads to two different uses of the same homogeneous increments.

We record the elementary sampling facts used in both ranges. On a measurable region of finite mass M, signed Poisson sampling of a vector function h means

where N has Poisson law of mean M, the \omega_j are independent with law \nu/M restricted to the region, and the \varepsilon_j are independent uniform signs. All these choices are independent. For M=0 the sum is zero. Sampling on disjoint regions is independent: indeed, subdividing a Poisson number of independent samples gives independent Poisson counts, as is seen from their joint probability generating function. In particular, sampling a V-valued function produces a vector in V.

6 The range 1<p<2

Fix 1<p<2. We construct the random normalized gradient required by Lemma 3.1, with \eta as chosen in (4.5).

6.1 A common heavy-tailed marginal

We first construct a random vector Y\in V by symmetric Poisson sampling of the vector v against the intensity \nu. On the region \{\|v\|_\infty>1\}, this is an ordinary signed compound Poisson sum: the region has measure at most |E| by (5.1). For each j\ge0, independently sample the region

and denote its signed compound Poisson sum by Y^{(j)}. Each A_j has finite measure, at most |E|2^{p(j+1)}. These are centered independent vectors. For every edge e,

Consequently \sum_{j\ge0}Y^{(j)} converges in L_2 with values in the finite dimensional space \R^E. Adding the sum on \{\|v\|_\infty>1\} defines Y. Every partial sum belongs to V; since V is closed, Y\in V almost surely.

The compound Poisson formula and convergence in probability give

The integrals converge absolutely: near zero the integrand is O_\theta(u^{1-p}), and at infinity it is O(u^{-p-1}). The second equality follows from (5.2) and the evenness of cosine. In particular, uniqueness of characteristic functions [5, Theorem 3.3.11] shows that all the Y_e have the same distribution, depending only on p.

For later use we prove directly that

Fix e and a\ge1. By Poisson splitting, or by the characteristic function (6.1), Y_e has the distribution of an independent sum B_a+S_a. Here B_a is the signed compound Poisson sum on \{|v_e|>a\}, whose number N_a of jumps is Poisson with mean a^{-p}, while S_a is the L_2 limit of the small-jump sums on \{0<|v_e|\le a\}. Thus

Chebyshev’s inequality gives

For the reverse inequality, condition on N_a=1, the magnitude u>a of its jump, and S_a=s. At least one of |s+u| and |s-u| exceeds a, and the jump’s two signs are equally likely. Therefore

This proves (6.2).

6.2 Clipping and projection

Let \lambda be a strictly positive probability on E, and choose \sigma and P from Lemma 4.2. Thus \sigma\ge\lambda/2, and P has absolute row sums at most H. For T>1, let [Y]_T denote coordinatewise clipping to [-T,T], and set

Then F\in V and \|F\|_\infty\le HT almost surely. Since Y=PY and p>1, integration of (6.2) yields

Orthogonal contraction, together with the same tail bound, gives

We compare moments below a second level a. The Lipschitz comparison will cost H(a/T)^{p-1}, while the quadratic estimate for the remaining tail will cost (T/a)^{2-p}. Balancing these gives a=T/H. Suppose a\ge2, and define the common capped moment

The common marginal law makes b independent of e and \lambda. Moreover, the layer-cake formula and (6.2) imply

The function h_a(t)=\min\{|t|,a\}^p is pa^{p-1}-Lipschitz. Hence (6.3) implies, for every e,

The part above this cap is controlled in weighted average. Since p<2, for every real t we have

Using (6.4), we obtain

Combining the two estimates proves

Choose

where A_{p,\eta} is sufficiently large. Since \log H=o(H^{2-p}), for all sufficiently large n we have a\ge2 and

By (6.6) and \lambda\le2\sigma, increasing A_{p,\eta} if necessary ensures

Both b and K are independent of the test probability \lambda. Finally,

These are the parameters required by Lemma 3.1 in this range.

7 The range 2<p<\infty

Fix p>2, with \eta as in (4.5). For a strictly positive test probability \lambda, obtain \sigma\ge\lambda/2 and P from Lemma 4.2. Write

All function norms below are taken with respect to \rho, unless another measure is indicated. The projection acts only in the edge variable.

7.1 A ramp of truncations

The overlapping truncations below create a triangular multiplicity profile of height \ell. We will show that its p-energy is of order \ell^{p+1}, whereas the pth power of the projection error is at most C_pH^{p-2}\ell. This gain determines the choice of \ell.

For a>0, let v_{\le a} denote the vector obtained by replacing v_e by v_e\mathbf 1_{\{|v_e|\le a\}} at each edge; put v_{>a}=v-v_{\le a}. For an integer \ell\ge1, to be chosen below, set

Thus u_e is v_e multiplied by the number of intervals (2^k,2^{k+\ell}], 0\le k<\ell, containing |v_e|. The successive nonzero multiplicities on the dyadic magnitude intervals are

The magnitude-density identity (5.2) therefore gives the same p-energy at every edge:

In particular, b\ge p\log2>1, and b is independent of both the input points and \lambda. Figure 1 illustrates this energy calculation for four overlapping intervals.

The same identity gives

The triangle inequality in L_2(\nu), applied to (7.1), consequently yields

Using the contraction of P in \ell_2(\sigma) and its row-sum bound, we obtain

In particular, the coordinatewise quadratic estimate follows from

For the supremum bound in (7.3), each summand defining u_e has magnitude at most 2^{k+\ell}, and their sum is less than 2^{2\ell}.

7.2 The projection error

We claim that

For 0\le k<2\ell, define the pointwise vector function

Although v_{\le2^k} need not belong to L_2(\rho), the identity Pv=v holds pointwise and gives A_k=-(P-I)v_{>2^k}. Thus A_k does belong to L_2(\rho), and

Here the second inequality uses the \ell_2(\sigma) contraction of I-P and the preceding tail integral. Moreover,

Summing the two bounds in (7.5) separately shows that this signed sum has L_2(\rho) norm at most C_p and supremum norm at most CH2^{2\ell}.

For a level \tau\ge16H, split the sum at 2^k\le\tau/(16H). The sum of the supremum norms of these smaller terms is at most \tau/2. By geometric decay, the remaining terms have total L_2(\rho) norm at most C_p(\tau/H)^{1-p/2}. Chebyshev’s inequality, together with the global L_2 bound for smaller levels, gives

This tail vanishes for \tau>CH2^{2\ell}. Integrating it against p\tau^{p-1}\,d\tau proves (7.4): the smaller levels contribute C_pH^{p-2}, and the larger levels contribute at most C_pH^{p-2}(\ell+1).

Since \|u\|_{L_p(\rho)}^p=b, the pointwise power-difference inequality and Hölder’s inequality imply

By (7.2) and (7.4),

Choose

where L\ge1 depends only on p,\eta and will be enlarged once more below. First choose it large enough that (7.6) is at most \eta b/8.

7.3 Poisson sampling

We need the leading coefficient in the next estimate to be arbitrarily close to one, since the desired distortion D may be arbitrarily close to one.

A proof using independent symmetric sums is given in Appendix B.

The function Z vanishes outside

because u vanishes there. Hence we may take the signed Poisson sum W of Z on this finite-measure region. Every summand is in V, so W\in V almost surely.

Write m_e=\int|Z_e|^p\,d\nu and a_e=\int|Z_e|^2\,d\nu. Lemma 7.1 gives, for every \epsilon>0,

The two quadratic estimates in (7.3) imply

Set \epsilon=\eta/32. The projection estimate gives \sum_e\sigma_e m_e\le(1+\eta/8)b, so the averaged \epsilon m_e term is at most \eta b/16. Further,

Enlarge L, still depending only on p,\eta, until the contribution of (7.10), including its constant C_{p,\epsilon}, is at most \eta b/16. We have proved

7.4 A bounded random gradient

Choose a constant C_p' so that

dominates both \sup_{e,r,t}|Z_e(r,t)| and \sup_e a_e^{1/2}. The exponential-moment formula for signed Poisson sums gives

where C_0 is absolute: use \cosh s-1\le C_0s^2 for |s|\le1 and a_e\le J^2. Consequently, for z\ge0,

Set

Discarding the entire vector on a bad event preserves membership in V, so F\in V and \|F\|_\infty\le K. By the union bound and (7.12),

For every edge, Cauchy–Schwarz therefore gives

By (7.8),

Thus the last bound in (7.13) tends to zero uniformly over the input points and \lambda. Since b\ge1, it is at most \eta b/4 for all sufficiently large n, with the threshold depending only on p,\eta. Combining this with (7.11) and \lambda\le2\sigma yields

The parameters b\ge1 and K\ge1 are independent of \lambda and of the input points, as required by Lemma 3.1. Finally,

These are the parameters required by Lemma 3.1 in this range.

8 Dimension bounds and exact embeddings

Table 1 summarizes the common parameters supplied by the two constructions. The target moment and magnitude bound are fixed before the test probability \lambda varies; the projection and the joint law of the random gradient may depend on that probability.

8.1 Completion of the upper bound

In Sections 6 and 7, the constructed parameters satisfy b,K\ge1, the weighted moment condition (3.1), and

for all sufficiently large n, with a threshold depending only on p,\eta. Lemma 3.1 and (4.5) give an embedding of distortion at most D. Since b\ge1, its dimension satisfies

This proves the upper bound in (1.2) for sufficiently large n. For the remaining finitely many values of n, enlarge C_{p,D} and use Lemma 2.1.

8.2 The packing bound

The coordinate unit vectors in \ell_p^n form an equilateral set. After translating and scaling any distortion-D image in \ell_p^d, its points are 1-separated and lie in the ball of radius D about the first point. Their open balls of radius 1/2 are disjoint and lie in the ball of radius D+1/2 about that point. Comparing d-dimensional Lebesgue volumes gives

This proves the lower bound in (1.2).

8.3 A quadratic obstruction to exact embeddings

For real a,b, define

If ab=0, this is zero. If ab\ne0, it has strictly the sign of p-2. To verify this, apply convexity for p>2, or concavity for p<2, to the two numbers (a+b)^2 and (a-b)^2 raised to the power p/2. Their average is a^2+b^2. Next use the strict inequality

Thus, for u,v\in\ell_p^d and p\ne2,

Indeed, the difference of the two sides is \sum_{a=1}^d\Delta_p(u_a,v_a), whose nonzero summands all have the same sign.

Fix k\ge2. Index the coordinates of \ell_p^{k^2} by \{1,\ldots,k\}^2. Let r_i be the indicator of row i, and c_j the indicator of column j. Consider the 4k+1 distinct points

Suppose that \mathcal X_k embeds with distortion one into \ell_p^d. Translate and rescale to obtain an isometry f with f(0)=0. Strict convexity of \ell_p^d implies

In fact, \|f(x)-f(-x)\|_p=2\|x\|_p and both \|f(x)\|_p and \|f(-x)\|_p equal \|x\|_p, so equality in the triangle inequality forces the two vectors f(x) and -f(-x) to coincide.

By (8.2), the expression in (8.1) is determined by distances among the given points and is preserved by f. Distinct rows have disjoint supports, so the supports of f(r_1),\ldots,f(r_k) are pairwise disjoint. The same holds for f(c_1),\ldots,f(c_k). In contrast, each row and column intersect in exactly one coordinate. Their defect is

Consequently \operatorname{supp}(f(r_i)) meets \operatorname{supp}(f(c_j)) for every (i,j). A single coordinate can belong to at most one row support and at most one column support, so it can account for at most one of these k^2 intersections. It follows that d\ge k^2.

For n\ge9, take k=\lfloor(n-1)/4\rfloor and add distinct points if necessary to obtain an n-point set. Any exact embedding of that set restricts to one of \mathcal X_k, proving the lower bound in (1.3). The upper bound is Lemma 2.1. Finally, 0<\gamma(p)<1, so the logarithmic limits in Theorem 1.1 follow from the stated bounds.

A Electrical-flow localization

The following proof follows the heat-kernel and entropy argument of Gurel-Gurevich, Nachmias, and Sachdeva [7, Sections 2–4], in the symmetric projection notation used here.

B The Poisson moment inequality