Nearly Optimal Lower Bounds for ℓp Embeddings (p<2)

Nearly Optimal Lower Bounds for ℓp Embeddings (p<2)

Introduction: Why ℓp “Subspace Embeddings” Keep Showing Up

If you’ve ever tried to run machine learning or optimization on massive data, you’ve probably bumped into the same annoying bottleneck: the data is too big to manipulate directly. A classic trick is to compress while still preserving what you care about—often distances or norms. In particular, the research problem behind this paper is about ℓp-subspace embeddings: mapping a d-dimensional subspace into a smaller space so that all vectors in the subspace keep roughly the same ℓp norm.

This new work from Yi Li (based on new research from https://arxiv.org/abs/2608.14201) tightens what we can prove about how small the compressed dimension can be. The paper focuses on the regime 1 ≤ p < 2 (excluding the special case where p is an even integer, which behaves differently). The big message: the authors show a nearly optimal lower bound on the embedding dimension required to achieve distortion (1±ε) simultaneously for every vector in the subspace.

To make it concrete, the paper defines N_p(d, ε) as the smallest integer N such that for every matrix A ∈ R^{n×d}, there exists a sketching/embedding matrix Φ ∈ R^{N×n} with:
[
(1-\epsilon)\|Ax\|p \le \|\Phi Ax\|p \le (1+\epsilon)\|Ax\|_p \quad \forall x\in \mathbb{R}^d.
]
So N is the number of “rows” you need in the compressed representation. The authors’ lower bound shows that you can’t hope to beat the known upper bounds by more than (at worst) polylog factors—at least for 1 ≤ p < 2.

Why This Matters (Right Now, Not “Someday”)

This is one of those results that’s easy to miss if you only care about flashy algorithms—but it matters because it draws a hard line around what’s possible. In practice, ℓp norms appear everywhere you’d want robustness (e.g., heavy-tailed noise) or different geometric behavior than ℓ2. Even if your current model pipeline uses ℓ2, many “robust regression” or “outlier-friendly” workflows either directly rely on ℓ1-ish geometry or quietly approximate it.

A very real today-style scenario: suppose you’re doing large-scale feature selection or optimization where the objective depends on ‖Ax‖_p. When p is closer to 1 (think p=1 or p=1.5), you’re in a regime where outliers dominate and the geometry becomes less forgiving. People love sketching because it makes training and optimization faster—but if the theory says “you must keep at least about this many rows,” then your engineering has a principled budget. No guessing. No magical thinking.

This paper also connects to a growing trend in ML theory: lower bounds are becoming as important as upper bounds. For a while, research focused on “can we sketch this efficiently?” Now we’re getting the matching “you can’t do better than this” answers—especially for the hardest ranges like 1 ≤ p < 2. That’s what this work adds: a lower bound that matches the best-known upper bound behavior (up to logs), closing a gap that was still open for general embeddings.

Hard Instances, for-All Guarantees, and the Real Game Being Played

What “for-all” Subspace Embedding Really Means

A lot of embedding-like statements sound similar, but they differ in what’s quantified. Here, the requirement is uniform over all vectors x ∈ R^d (inside the subspace). That “for-all” part is what makes the problem tough: it’s not enough to preserve norms for one or a few queries—you need the sketch to behave correctly globally.

Concretely, the embedding condition is:
- Inputs: any A of size n×d
- Outputs: one sketch matrix Φ of size N×n
- Guarantee: the inequality holds for every x

The paper’s lower bound says that to make this happen, N can’t be too small.

Why the Regime p < 2 is Special

The behavior changes dramatically depending on whether p hits certain “nice” values. The paper assumes:
- p is a constant in [1,∞) \ 2Z (so p is not an even integer)
- and then the strongest “almost settled” statement is for 1 ≤ p < 2

There’s also a known obstruction: when p ∈ 2Z, there exist isometric embeddings, which means you can’t have a lower bound that depends on ε in the same way. That’s why the paper excludes those p values.

The Paper’s Main Result: A Lower Bound That Nearly Matches Known Upper Bounds

The quantity being bounded: N_p(d, ε)

The core object is N_p(d, ε): the number of rows needed in an embedding/sketch so that ℓp norms are preserved to within (1±ε) for all vectors in the d-dimensional subspace.

The paper proves (for constant p ≥ 1, p ∉ 2Z) a lower bound that, in the key range 1 ≤ p < 2, matches what upper bounds suggest up to logarithmic factors.

The “shape” of the bound: what it depends on

Earlier work established that:
- dependence on d of the form d^{max{1, p/2}} is tight
- and dependence on ε of the form ε^{-2} is also known to be tight up to logs under appropriate d scaling (e.g., d ≳ log(1/ε))

This new result strengthens the missing part: it shows that the combined dependence on both d and ε is also essentially tight for general (not row-sampling-only) embeddings.

How this lines up with what we already had

There’s a bit of history here. For context, previous upper bounds had the general form (paper states it as):
- N_p(d, ε) bounded by something like O_p( (d/ε^2)^{max{1, p/2}} ) times perhaps polylog factors.

The new lower bound shows you can’t beat that combined dependence (again: up to logs) when 1 ≤ p < 2.

Here’s the comparison in spirit (not with the paper’s exact constants, but capturing the regimes and “what matched”):

This is why the result feels like “closing the loop” for 1 ≤ p < 2.

The Proof Blueprint: From Sketching to Data Structures to Dimensions

This is the most interesting part if you like how theory proofs are engineered. The paper uses a strategy that was pioneered in related work by Li et al. [6], and then pushes it further.

Step 1: Move from embeddings to sketches-as-data-structures

Instead of directly proving a dimension lower bound for embeddings, the authors define a related “for-all ℓp subspace sketch problem.”

They consider an n×d input matrix A, but the algorithm is framed like a data structure:
- The data structure must store O(log(nd))-bit-precision descriptions of entries (the paper explicitly mentions entries specified by O(log(nd)) bits).
- It must answer queries x by producing an approximation to ‖Ax‖_p^p (or equivalently ‖Ax‖_p up to power transforms).
- Most importantly: it must work for all x ∈ R^d.

This step is clever: answering many norm queries with high accuracy requires enough information stored somewhere. If you don’t store enough, two different “worlds” (two different hard instances) will look the same to the sketch, and the sketch can’t know which world it’s in.

Step 2: Prove an information lower bound (bits)

The paper establishes that any such data structure needs a number of bits that scales like:
- essentially Ω( d^2 / (ε^2 polylog(1/ε)) ) bits in a key hard regime (the paper describes it more generally with extra exponents depending on p via α_p = max{1, p/2})

In other words, you can’t compress too much without losing the ability to answer all norm queries accurately.

Step 3: Convert bit lower bounds into dimension lower bounds

Finally, the authors use a standard conversion: if you had a very small embedding dimension N, you could store or represent the sketch compactly, which would imply a better (smaller) data structure than the bit lower bound allows.

So the paper translates:
- “data structure needs ≥ X bits”
into
- “embedding must use N rows where N is at least the corresponding dimension bound”

This is exactly the kind of pipeline you want: it connects storage/communication constraints to linear algebraic embedding constraints.

The Core Construction: A Spectral Hard Instance That Forces Sign Recovery

Why spectral (eigenvalue) structure shows up

To prove lower bounds for uniform norm preservation, you need a hard input ensemble. This paper uses a spectral construction: it builds a matrix from a carefully designed symmetric matrix whose eigenvalues are known and controllable.

The hard matrix is related to expressions like:
[
M_{i,j} = |\langle i, j\rangle|^{p-2}
]
on a Boolean-like index set U = {−1, 1}^k.

Then the normalized Hadamard matrix H diagonalizes it, which makes the spectrum manageable. The paper also uses a “spectrum-truncated” version \tilde{M} to focus on the eigen-components that matter.

Sign encodings: recovering “hidden information”

Here’s the intuition. The authors construct instances so that answering the sketch’s norm queries lets you approximately recover hidden sign information. They do this in two phases:

1. Classical sign-vector style (earlier work): random signs s_i ∈ {−1,1} get embedded into the geometry.
2. This paper’s upgrade (for general p<2): replace each scalar sign with a sign matrix S_i ∈ {−1,1}^{s×s} (so the hidden information per index i becomes much richer).

Then they define query vectors that interact with the hard instance so that ‖Ax‖_p^p (as approximated by the sketch) reveals derivatives of certain analytic functions. From those derivatives, the sketch can distinguish different sign-matrix collections.

If you can distinguish exponentially many possibilities, then the sketch must “contain” enough information—which forces a large embedding dimension.

What’s Actually “Almost Settled” for 1 ≤ p < 2?

The tightness story: the missing link is the combined dependence

Earlier results had already pinned down:
- the tight dependence on d in terms like d^{max{1, p/2}}
- and ε^{-2} (up to logs) when d ≳ log(1/ε)

But what people really wanted (and hadn’t fully confirmed) was whether the dependence on d and ε couples exactly the way upper bounds suggested. This paper answers: yes, essentially.

The authors explicitly say that for p ∈ [1,2) the lower bound is tight up to logarithmic factors, so the ℓp-subspace embedding problem is “almost settled” in that range for general embeddings (not just row-sampling sketches).

Why excluding p ∈ 2Z is not a technicality

The paper notes that for p ∈ 2Z, isometric embeddings exist. That means you can have embeddings with no distortion loss that depend differently on ε, so any lower bound of the form “must pay ε^{-something}” would be false. So the condition p ∉ 2Z is necessary for the whole lower-bound mechanism to make sense.

Key Takeaways

Key Takeaways

• Main contribution: For constants 1 ≤ p < 2 with p ∉ 2Z, Yi Li proves a nearly optimal lower bound on the embedding dimension N_p(d, ε) needed for ℓp-subspace embeddings with distortion (1±ε).
• Tightness in the hardest gap: The result matches known upper bounds up to logarithmic factors, meaning the best-known dependence on both d and ε is essentially correct for general embeddings in this regime.
• Proof strategy (big picture): The paper reduces embedding lower bounds to for-all ℓp subspace sketch / data-structure lower bounds, proves an information (bits) lower bound using carefully crafted hard instances, then converts bits → dimension.
• Why the p < 2 regime matters: Geometry is less forgiving than ℓ2, and the sign-matrix spectral construction is engineered to force the sketch to carry enough information to recover hidden sign structure.
• Practical implication: If you’re building sketching or compression systems that preserve ℓp norms for p near 1 (robustness settings), this theory gives a real lower bound on compression level—useful for setting realistic targets for sketch size.

If you want, I can also rephrase the final lower bound into an easy “engineering rule of thumb” for how N scales with d and ε specifically for representative values like p=1 and p=1.5.