Random-information decay threshold for polynomially decaying ellipsoids

Let 1p1\le p\le\infty and let the semiaxes be σj=jλ\sigma_j=j^{-\lambda} for jNj\in\mathbb{N}, with λ>1s=(121p)+\lambda>\frac{1}{s}=\left(\frac{1}{2}-\frac{1}{p}\right)_+. Write Ep,σm\mathcal{E}_{p,\sigma}^{m} for the corresponding finite-dimensional p\ell_p-ellipsoid, Gn,mG_{n,m} for a random nn-dimensional information subspace, and rad(Ep,σm,Gn,m)\operatorname{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}) and rad(Ep,σm,n)\operatorname{rad}(\mathcal{E}_{p,\sigma}^{m},n) for the radii of random and optimal information, respectively. Let pp^* be the conjugate exponent of pp. Random-information threshold conjecture.

decay(rad(Ep,σm,Gn,m))={decay(rad(Ep,σm,n)),λ>1p,0,λ1p.\operatorname{decay}\bigl(\operatorname{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})\bigr)= \begin{cases} \operatorname{decay}\bigl(\operatorname{rad}(\mathcal{E}_{p,\sigma}^{m},n)\bigr),&\lambda>\frac{1}{p^*},\\ 0,&\lambda\le\frac{1}{p^*}. \end{cases}

The conjecture predicts a threshold at λ=1/p\lambda=1/p^*: above it, random information has the same decay rate as optimal information, while at or below it random information has no decay. The surrounding discussion establishes several regions of this picture, but the asserted threshold behavior remains open.

Sources & referencesView supporting material

Primary source

Aicke Hinrichs, Joscha Prochno and Mathias Sonnleitner, “Random sections of _p-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators”, arXiv:2109.14504 (2021).

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.