arXiv preprint ·
Low-Degree Polynomial Approximation of the Cross-Polytope
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We determine the degree-distortion tradeoff for polynomial approximation of the $d$-dimensional cross-polytope $B_1^d$. For every $1\le t\le d$, every globally nonnegative degree-$2t$ form that is positive away from the origin has multiplicative sandwich distortion at least $(2e)^{-1/2}\sqrt{d/t}$, while an explicit sum-of-squares (SoS) form achieves distortion at most $(2e)^{1/2}\sqrt{d/t}$. Hence both the nonnegative-form and SoS optima are $Θ(\sqrt{d/t})$, and degree $Θ(d)$ is necessary and sufficient for constant distortion. The lower bound is representation-free. Averaging over signed permutations and evaluating on flat points of the $\ell_1$ sphere reduces every candidate to a support-size profile $V(k)=k^{-2t}Q(k)$ with $°Q\le t$ and $Q(0)=0$. After the substitution $u=1/k$, Lagrange interpolation shows that this degree budget cannot keep the profile nearly constant across $d$ support scales. A matching SoS construction averages even powers of sign-vector facet normals and reduces the upper bound to a Rademacher moment. We also isolate a weighted reciprocal-grid lemma, derive consequences for $\ell_p$ balls, and contrast the polar cube. For a general symmetric polytope, weighted facet powers yield a one-sided certificate whose boundary-floor objective is concave and whose worst-direction oracle reduces to convex dual-norm problems; at degree two, its optimizers recover classical optimal design and the John ellipsoid. This is an oracle-model certificate optimization, not an end-to-end complexity result or a characterization of the full SoS optimum.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics
High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models
Fast Stencil Computations on a Single Arbitrarily Moving Interval
A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments
Accelerated Local Algorithms for Personalized and Regularized PageRank
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.