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

Let 1<p<21<p<2, let PRDP\subset\mathbb{R}^D be a set of NN points, and let F:RDRkF:\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 1N(c2)1-N^{-(c-2)}, for all x,yPx,y\in P, if xyp=O(ϵ2)\lVert x-y\rVert_p=O(\epsilon^2) then

(1ϵ)μ(xyp)ρ(F(x),F(y))(1+ϵ)μ(xyp),(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 xyp=Ω(ϵ2)\lVert x-y\rVert_p=\Omega(\epsilon^2) then

μ(xyp1+ϵ)ρ(F(x),F(y))μ((1+ϵ)xyp).\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.

Sources & referencesView supporting material

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.