Nonlinear pp-stable projection conjecture for 1<p<21<p<2

About 7 years old · traced to

Let 1<p<21<p<2, let P⊂RDP\subset\mathbb{R}^D be a set of NN points, and let F:RD→RkF:\mathbb{R}^D\to\mathbb{R}^k have independent entries FijF_{ij} distributed as standard pp-stable random variables. Let ρ\rho, ϵ\epsilon, and kk be as in the theorem above, and define

μ(λ):=E ξ(λF11).\mu(\lambda):=\mathbb{E}\,\xi(\lambda F_{11}).

Nonlinear pp-stable projection conjecture. With probability at least 1−N−(c−2)1-N^{-(c-2)}, for all x,y∈Px,y\in P, if ∥x−y∥p=O(ϵ2)\lVert x-y\rVert_p=O(\epsilon^2) then

(1−ϵ)μ(∥x−y∥p)≤ρ(F(x),F(y))≤(1+ϵ)μ(∥x−y∥p),(1-\epsilon)\mu(\lVert x-y\rVert_p)\leq \rho(F(x),F(y))\leq (1+\epsilon)\mu(\lVert x-y\rVert_p),

and if ∥x−y∥p=Ω(ϵ2)\lVert x-y\rVert_p=\Omega(\epsilon^2) then

μ(∥x−y∥p1+ϵ)≤ρ(F(x),F(y))≤μ((1+ϵ)∥x−y∥p).\mu\left(\frac{\lVert x-y\rVert_p}{1+\epsilon}\right)\leq \rho(F(x),F(y))\leq \mu\left((1+\epsilon)\lVert x-y\rVert_p\right).

This extends the theorem's nonlinear embedding statement from Cauchy, or 11-stable, projections to pp-stable projections for 1<p<21<p<2, using the same metric and target-dimension regime.

References

Primary source

Michael P. Casey, “Linear Dimension Reduction Approximately Preserving a Function of the 1-Norm”, arXiv:1906.03536 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.