Optimal Randomized Clustering of Matrices

Gunes, Mustafa Alper; Naor, Assaf

doi:10.4230/LIPIcs.SoCG.2026.56

Optimal Randomized Clustering of Matrices

Mustafa Alper Gunes

Department of Mathematics, Princeton University, NJ, USA Assaf Naor

Department of Mathematics, Princeton University, NJ, USA

Abstract

If $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ is a unitarily invariant normed space, i.e., $\|\mathsf{U}\mathsf{A}\mathsf{V}\|_{\mathbf{X}}=\|\mathsf{A}\|_{\mathbf{X}}$ for every matrix $\mathsf{A}\in\mathsf{M}_{n}(\mathbb{R})$ and every two orthogonal matrices $\mathsf{U},\mathsf{V}\in\mathsf{M}_{n}(\mathbb{R})$ , then we evaluate up to universal constant factors the smallest $\sigma>0$ for which there is a probability distribution over partitions of $\mathbf{X}$ into clusters of diameter at most $1$ yet for every two matrices $\mathsf{A},\mathsf{B}\in\mathsf{M}_{n}(\mathbb{R})$ the probability that they fall into distinct clusters is at most $\sigma$ times the $\mathbf{X}$ -distance between $\mathsf{A}$ and $\mathsf{B}$ . Specifically, we prove that this infimal $\sigma$ , which is called the separation modulus of $\mathbf{X}$ and is denoted $\mathsf{SEP}(\mathbf{X})$ , satisfies:

\mathsf{SEP}(\mathbf{X})=\Theta\big(\sqrt{n}\cdot\|\mathsf{I}_{n}\|_{\mathbf{X% }}\cdot\operatorname{diam}(B_{\mathbf{X}})\big),

(1)

where $\mathsf{I}_{n}$ is the $n$ -by- $n$ identity matrix and $\operatorname{diam}(B_{\mathbf{X}})$ is the diameter with respect to the standard Euclidean metric on $\mathsf{M}_{n}(\mathbb{R})$ of the unit ball $B_{\mathbf{X}}$ of $\mathbf{X}$ . Our proof of (1) proceeds through an asymptotic evaluation of the spectral gap of the Laplacian with Dirichlet boundary conditions on $B_{\mathbf{X}}$ , which we achieve by exact computations for a Jacobi orthogonal random matrix ensemble. Assuming oracle access to norm evaluations in $\mathbf{X}$ , by combining (1) with a new deterministic algorithm for a $O(1)$ -approximation of the diameter of convex bodies in $\mathbb{R}^{n}$ that are given by a weak membership oracle and are symmetric with respect to coordinate permutations and reflections about the standard axes (this task is famously known to be impossible in the absence of such symmetries), we get an oracle polynomial time algorithm whose output is the separation modulus of $\mathbf{X}$ up to universal constant factors. Another example of a consequence of (1) is that for each $m\in\{1,\ldots,n\}$ the separation modulus of the $m$ ’th Ky Fan norm on $\mathsf{M}_{n}(\mathbb{R})$ is bounded from above and from below by universal constant multiples of $m\sqrt{n}$ if $m\geqslant\sqrt{n}$ , and of $n$ if $m\leqslant\sqrt{n}$ . We also deduce from (1) an upper bound on the Lipschitz extension modulus of $\mathbf{X}$ that improves over the previously best-known bound even in the special case when $\mathbf{X}$ is $\mathsf{M}_{n}(\mathbb{R})$ equipped with the $\ell_{2}^{n}\to\ell_{2}^{n}$ operator norm.

Keywords and phrases:

Clustering, Unitarily Invariant Matrix Norms, Oracle Polynomial Time Approximation Algorithms for Radii of Convex Bodies, Extension of Lipschitz Functions, Random Matrices, Spectrum of the Laplacian with Dirichlet Boundary Conditions, Reverse Isoperimetry

Funding:

Assaf Naor: supported by NSF grant DMS-2453936, BSF grant 2018223, and a Simons Investigator award.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry ; Mathematics of computing

\rightarrow

Mathematical analysis ; Theory of computation

\rightarrow

Design and analysis of algorithms

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

For $\sigma>0$ , a metric space $(\mathcal{M},d_{\mathcal{M}})$ is said to admit a $\sigma$ -separating random partition if for every $\Delta>0$ there is a distribution over random partitions of $\mathcal{M}$ into clusters of diameter at most $\Delta$ with the property that for every two points $x,y\in\mathcal{M}$ the probability that $x$ and $y$ belong to distinct clusters is at most $\sigma/\Delta$ times the distance between $x$ and $y$ . The smallest $\sigma$ for which this is possible is called the separation modulus of $\mathcal{M}$ and it is denoted $\mathsf{SEP}(\mathcal{M})$ .

Separating random partitions are a well studied clustering primitive which was introduced and investigated in [10] (precursors that considered it implicitly, with a variety of applications, appear in [49, 7, 1, 40]); see e.g. [54, 55] for more on the history. By [10], every $n$ -point metric space $(\mathcal{M},d_{\mathcal{M}})$ satisfies $\mathsf{SEP}(\mathcal{M})=O(\log n)$ , and there are metric spaces for which this bound is sharp. In [45], a randomized polynomial time algorithm was designed that takes as input a finite metric space $(\mathcal{M},d_{\mathcal{M}})$ and outputs a factor $2$ approximation to $\mathsf{SEP}(\mathcal{M})$ . See [11, 20, 41, 31, 46, 24, 47, 45, 8, 54, 55, 43, 56, 44, 57] for an indication of the literature on this topic. The investigation of separating random partitions of finite-dimensional normed spaces, which is what we study herein, originates in [58], motivated by applications to network routing and distributed computing. The work [20] sharpened and generalized the bounds of [58], and influenced later research, e.g. [47, 4, 55]; similar partitioning schemes appeared implicitly in the earlier work [37] on SDP-based algorithms for graph colorings. Applications of separating random partitions to pure mathematics have also been found, notably to metric embeddings [11, 24, 56] and extension of vector-valued Lipschitz functions [47, 55].

In Theorem 1 below we obtain an asymptotic formula (up to universal constant factors) for the separation modulus of $\mathsf{M}_{n}(\mathbb{R})$ equipped with an arbitrary unitarily invariant matrix norm;¹¹1Formally, when dealing with infinite metric spaces (in particular, in the case of unitarily invariant matrix norms that we study herein), one must impose some measurability requirement for the definition of the separation modulus to make sense. At the very least, one has to demand that for every $x,y\in\mathcal{M}$ the aforementioned event “ $x$ and $y$ belong to distinct clusters” is measurable with respect to the underlying probability measure on the space of partitions of $\mathcal{M}$ . For the purpose of the present article, it suffices to assume this “minimal” measurability. However, it is beneficial for applications to impose stronger measurability assumptions; such a foundational treatment of random partitions of infinite spaces has been carried out in [47, 55]. One of the applications of Theorem 1 is to deduce an improved extension result for Lipschitz functions (Theorem 2 below), for which the aforementioned stronger measurability assumptions are needed. However, this will be achieved by substituting the ensuing reasoning into the framework of [55], which is shown in [55] to indeed yield the desired measurability. Thus, we do not need to recall stronger measurability requirements as they do not directly pertain to the ensuing discussion. Alternatively, our results are meaningful and new even if one only treats random partitions of finite subsets of $\mathsf{M}_{n}(\mathbb{R})$ equipped with a unitarily invariant matrix norm rather than random partitions of all of $\mathsf{M}_{n}(\mathbb{R})$ , a setting to which measurability considerations are irrelevant. we will spell out all of its (standard) notation and terminology right after stating it:

Theorem 1.

Let $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ be a unitarily invariant normed space. Then²²2In addition to the usual $O(\cdot),o(\cdot),\Omega(\cdot),\Theta(\cdot)$ notation, we will use throughout this text the following conventions for asymptotic notation: Given $a,b>0$ , by writing $a\lesssim b$ or $b\gtrsim a$ we mean that $a\leqslant\kappa b$ for some universal constant $\kappa>0$ , and $a\asymp b$ stands for $(a\lesssim b)\wedge(b\lesssim a)$ ; when we will need to allow for dependence on parameters, we will indicate it by subscripts.

\mathsf{SEP}(\mathbf{X})\asymp\sqrt{n}\|\mathsf{I}_{n}\|_{\mathbf{X}}% \operatorname{diam}(B_{\mathbf{X}}),

(2)

where $\operatorname{diam}(B_{\mathbf{X}})=\operatorname{diam}_{\mathsf{S}_{2}^{n}}(B% _{\mathbf{X}})$ is the diameter with respect to the standard Euclidean metric on $\mathsf{M}_{n}(\mathbb{R})$ of the unit ball $B_{\mathbf{X}}$ of $\mathbf{X}$ , and $\mathsf{I}_{n}\in\mathsf{M}_{n}(\mathbb{R})$ is the $n$ -by- $n$ identity matrix.

A norm $\|\cdot\|$ on the space $\mathsf{M}_{n}(\mathbb{R})$ of $n$ -by- $n$ matrices with real entries is said to be unitarily invariant if $\|\mathsf{U}\mathsf{A}\mathsf{V}\|=\|\mathsf{A}\|$ for every $\mathsf{A}\in\mathsf{M}_{n}(\mathbb{R})$ and every two matrices $\mathsf{U},\mathsf{V}$ that belong to the orthogonal group $\mathsf{O}_{n}$ . Norms with this property [71, 64] form a rich class of ways to measure the size of matrices in an intrinsic manner that does not depend on the choice of orthogonal bases of $\mathbb{R}^{n}$ with respect to which the matrix representation of the corresponding linear operator is formed. As such, unitarily invariant norms are of great importance and utility to a wide range of disciplines, ranging from multiple areas of pure mathematics and theoretical physics, to algorithm design, signal processing, quantum information theory, numerical linear algebra, shape analysis and imaging, statistics, machine learning and data analysis; we point to this selection [73, 50, 75, 13, 67, 62, 32, 28, 22, 59, 70, 69, 72, 63, 68] of sources for part of the massive and varied literature on this (examining the references therein and those that arise from internet search leads to a cornucopia of additional relevant works).

Non-examples of unitarily invariant norms on matrices include those that consider a matrix $\mathsf{A}=(a_{ij})\in\mathsf{M}_{n}(\mathbb{R})$ to merely be a collection of $n^{2}$ numbers, e.g., the $\ell_{p}^{n^{2}}$ norms

\|\mathsf{A}\|_{\ell_{p}^{n^{2}}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}% \Big(\sum_{i=1}^{n}\sum_{j=1}^{n}|a_{ij}|^{p}\Big)^{\frac{1}{p}}

(3)

for $p\in[1,\infty]\smallsetminus\{2\}$ ; such measurements of the size of a matrix are of course highly valuable even though they ignore the operator meaning of the arrangement of those numbers as an $n$ -by- $n$ array, and they are not what we study herein (for the aforementioned $\ell_{p}^{n^{2}}$ norm, the separation modulus has been evaluated up to universal constant factors in [20] when $1\leqslant p\leqslant 2$ and in [55] when $p>2$ ). Examples of unitarily invariant norms include the Schatten von-Neumann trace class $\mathsf{S}_{p}^{n}$ for every $1\leqslant p\leqslant\infty$ , which are given by setting

\forall\mathsf{A}\in\mathsf{M}_{n}(\mathbb{R}),\qquad\|A\|_{\mathsf{S}_{p}^{n}% }\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Big(\operatorname{\mathrm{Trace}}% \big((\mathsf{A}\mathsf{A}^{\!\!*})^{\frac{p}{2}}\big)\Big)^{\frac{1}{p}}=\Big% (\sum_{i=1}^{n}s_{i}(\mathsf{A})^{p}\Big)^{\frac{1}{p}},

where $s_{1}(\mathsf{A})\geqslant\ldots\geqslant s_{n}(\mathsf{A})\geqslant 0$ are the singular values of $\mathsf{A}$ , i.e., they are the (decreasing rearrangement of the) eigenvalues of the positive semidefinite matrix $|\mathsf{A}|=(\mathsf{A}\mathsf{A}^{\!*})^{1/2}$ . If $p=\infty$ , then $\mathsf{S}_{\infty}^{n}$ coincides with the space of $n$ -by- $n$ matrices equipped with their operator (a.k.a. spectral) norm, when they are viewed as linear operators from $\ell_{2}^{n}$ to itself, i.e.,

\|\mathsf{A}\|_{\mathsf{S}_{\infty}^{n}}=\max_{x\in B_{\ell_{2}^{n}}}\|\mathsf% {A}x\|_{\ell_{2}^{n}}=s_{1}(\mathsf{A}),

where $B_{\mathbf{X}}=\{x\in\mathbf{X}:\ \|x\|_{\mathbf{X}}\leqslant 1\}$ denotes the unit ball of a normed space $(\mathbf{X},\|\cdot\|_{\mathbf{X}})$ . Often $\mathsf{S}_{1}^{n}$ is called the nuclear norm on $\mathsf{M}_{n}(\mathbb{R})$ , and $\mathsf{S}_{2}^{n}$ is the standard Euclidean (a.k.a. Hilbert–Schmidt or Frobenius) norm on $\mathsf{M}_{n}(\mathbb{R})$ , i.e., it coincides with the case $p=2$ of (3). Additional examples are furnished [25] by the Ky Fan norms $\|\cdot\|_{\mathsf{K}_{1}},\ldots,\|\cdot\|_{\mathsf{K}_{n}}$ that are defined by:

\forall m\in[n]\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{1,\ldots,n\},\ % \forall\mathsf{A}\in\mathsf{M}_{n}(\mathbb{R}),\qquad\|A\|_{\mathsf{K}_{m}^{n}% }\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i=1}^{m}s_{i}(\mathsf{A}).

(4)

More generally, let $\mathbf{E}=(\mathbb{R}^{n},\|\cdot\|_{\mathbf{E}})$ be a symmetric normed space, i.e., the following requirement holds for every vector $x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ , every choice of permutation $\pi\in S_{n}$ , and every choice of signs $\varepsilon_{1},\ldots,\varepsilon_{n}\in\{-1,1\}$ :

\|(\varepsilon_{1}x_{\pi(1)},\ldots,\varepsilon_{n}x_{\pi(n)})\|_{\mathbf{E}}=% \|x\|_{\mathbf{E}}.

(5)

The unitary ideal $\mathsf{S}_{\mathbf{E}}^{n}$ of $\mathbf{E}$ is defined to be $\mathsf{M}_{n}(\mathbb{R})$ equipped with the norm that is given by:

\forall\mathsf{A}\in\mathsf{M}_{n}(\mathbb{R}),\qquad\|\mathsf{A}\|_{\mathsf{S% }_{\mathbf{E}}^{n}}=\big\|\big(s_{1}(\mathsf{A}),\ldots,s_{n}(\mathsf{A})\big)% \big\|_{\mathbf{E}}.

(6)

A norm $\|\cdot\|$ on $\mathsf{M}_{n}(\mathbb{R})$ is unitarily invariant iff there is a symmetric norm $\|\cdot\|_{\mathbf{E}}$ on $\mathbb{R}^{n}$ such that $\|\cdot\|=\|\cdot\|_{\mathsf{S}_{\mathbf{E}}^{n}}$ ; see e.g. [53] or [12, Chapter IV] for a justification of this classical fact.

The novel content of Theorem 1 is the upper bound on $\mathsf{SEP}(\mathbf{X})$ in (2), i.e., Theorem 1 provides an improved randomized clustering of $\mathbf{X}$ . The matching impossibility result is due to [55, Corollary 79], where it was proved that $\sqrt{n}\|\mathsf{I}_{n}\|_{\mathbf{X}}\operatorname{diam}(B_{\mathbf{X}})% \lesssim\mathsf{SEP}(\mathbf{X})\lesssim\sqrt{n\log n}\|\mathsf{I}_{n}\|_{% \mathbf{X}}\operatorname{diam}(B_{\mathbf{X}})$ in the setting of Theorem 1. Therefore, what Theorem 1 achieves is removing the last redundant unbounded lower-order factor, thus obtaining an asymptotic evaluation of $\mathsf{SEP}(\mathbf{X})$ that is optimal up universal constant factors.

For the operator norm, the aforementioned bounds from [55] are $n\lesssim\mathsf{SEP}(\mathsf{S}_{\infty}^{n})\lesssim n\sqrt{\log n}$ , and these were the previously best-known estimates on $\mathsf{SEP}(\mathsf{S}_{\infty}^{n})$ . By Theorem 1, we now know that $\mathsf{SEP}(\mathsf{S}_{\infty}^{n})\asymp n$ .

As another example, it is straightforward to check from (4) that for each $m\in[n]$ the $\mathsf{S}_{2}^{n}$ -diameter of the unit ball of the $m$ ’th Ky Fan norm $\mathsf{K}_{m}^{n}$ equals $2\sqrt{n+m(m-1)}/m\asymp\max\{1,\sqrt{n}/m\}$ , so Theorem 1 demonstrates that $\mathsf{SEP}(\mathsf{K}_{m}^{n})$ is bounded from above and from below by positive universal constant multiples of $m\sqrt{n}$ if $m\geqslant\sqrt{n}$ , and of $n$ if $m\leqslant\sqrt{n}$ , thus providing an interpolation between the operator norm $\mathsf{K}_{1}^{n}=\mathsf{S}_{\infty}^{n}$ and the nuclear norm $\mathsf{K}_{n}^{n}=\mathsf{S}_{1}^{n}$ that somewhat curiously stabilizes (up to universal constant factors) at $m\asymp\sqrt{n}$ .

Theorem 1 implies progress on the important and extensively studied classical topic of extending vector-valued Lipschitz functions; see e.g. [19, 55] and the references therein. The Lipschitz extension modulus of a metric space $(\mathcal{M},d_{\mathcal{M}})$ , denoted $\mathsf{e}(\mathcal{M},d_{\mathcal{M}})$ or simply $\mathsf{e}(\mathcal{M})$ when the underlying metric $d_{\mathcal{M}}$ is clear from the context, is the infimum over those $L\in[1,\infty]$ such that for every subset $\mathscr{C}\subseteq\mathcal{M}$ , every Banach space $(\mathbf{Y},\|\cdot\|_{\mathbf{Y}})$ , and every $1$ -Lipschitz function $f:\mathscr{C}\to\mathbf{Y}$ , there exists an $L$ -Lipschitz function $F:\mathcal{M}\to\mathbf{Y}$ whose restriction to $\mathscr{C}$ coincides with $f$ . By [47] we have $\mathsf{e}(\mathcal{M})\lesssim\mathsf{SEP}(\mathcal{M})$ , and the forthcoming work [15] demonstrates that $\mathsf{e}(\mathcal{M})\gtrsim\sqrt{\mathsf{SEP}(\mathcal{M})}$ , so $\mathsf{e}(\mathcal{M})<\infty$ if and only if $\mathsf{SEP}(\mathcal{M})<\infty$ . A substitution of the former upper bound on $\mathsf{e}(\mathcal{M})$ provides the following extension theorem:

Theorem 2.

If $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ is a unitarily invariant normed space, then:

\mathsf{e}(\mathbf{X})\lesssim\sqrt{n}\|\mathsf{I}_{n}\|_{\mathbf{X}}% \operatorname{diam}(B_{\mathbf{X}}).

The special case $\mathbf{X}=\mathsf{S}_{\infty}^{n}$ of Theorem 2 asserts that for every subset $\mathscr{C}$ of $\mathsf{M}_{n}(\mathbb{R})$ and every Banach space $(\mathbf{Y},\|\cdot\|_{\mathbf{Y}})$ , if $f:\mathscr{C}\to\mathbf{Y}$ is $1$ -Lipschitz with respect to the operator norm (and the given norm $\|\cdot\|_{\mathbf{Y}}$ on the target $\mathbf{Y}$ ), then it can be extended to a $\mathbf{Y}$ -valued function that is defined on all of $\mathsf{M}_{n}(\mathbb{R})$ and is $L$ -Lipschitz with respect to the operator norm, where $L\lesssim n$ . The previously best-known [55] upper bound on $L$ here was $L\lesssim n\sqrt{\log n}$ , and the corresponding best impossibility result that is currently available [55] is that there exist suitably chosen $\mathscr{C},\mathbf{Y},f$ as above for which necessarily $L\gtrsim\sqrt{n}$ . Thus, we now know that:

{\textstyle\sqrt[4]{\dim(\mathsf{S}_{\infty}^{n})}}=\sqrt{n}\lesssim\mathsf{e}% (\mathsf{S}_{\infty}^{n})\lesssim n={\textstyle\sqrt{\dim(\mathsf{S}_{\infty}^% {n})}}.

(7)

Problem 3.

It remains an interesting open question to determine the growth rate of $\mathsf{e}(\mathsf{S}_{\infty}^{n})$ as $n\to\infty$ . For that matter, there is no unitarily invariant normed space $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ for which the value of $\mathsf{e}(\mathbf{X})$ is known up to $O(1)$ factors, or even up to lower-order factors. Since $\operatorname{diam}(B_{\mathbf{X}})\geqslant 2\|\mathsf{I}_{n}\|_{\mathsf{S}_{% 2}^{n}}/\|\mathsf{I}_{n}\|_{\mathbf{X}}=2\sqrt{n}\|\mathsf{I}_{n}\|_{\mathbf{X}}$ , Theorem 2 does not provide an upper bound on $\mathsf{e}_{n}(\mathbf{X})$ that is $o(n)$ . At the same time, the general lower bound on $\mathsf{e}(\mathbf{X})$ in [55, Theorem 96] is at most $\sqrt{n}$ , since the Banach–Mazur distance between $\mathbf{X}$ and an $n^{2}$ -dimesnional Hilbert space is at most $\sqrt{n}$ , as seen by applying John’s theorem [33] to the symmetric space $\mathbf{E}=(\mathbb{R}^{n},\|\cdot\|_{\mathbf{E}})$ for which $\mathbf{X}=\mathsf{S}_{\mathbf{E}}^{n}$ . Thus, the bounds in (7) are the best one could hope for using the current state of the art even when $\mathsf{S}_{\infty}^{n}$ is replaced by any unitarily invariant norm on $\mathsf{M}_{n}(\mathbb{R})$ . It seems that a substantial new idea will be needed in order to improve either the upper or lower estimate in (7).

As another application of Theorem 1, if we are given oracle access to (approximate) norm computations in a unitarily invariant normed space $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ , then we obtain a (deterministic) algorithm that evaluates its separation modulus $\mathsf{SEP}(\mathbf{X})$ up to universal constant factors in oracle polynomial time.³³3A weak membership oracle suffices here (one can obtain from such a membership oracle a norm evaluation oracle by binary search of possible upper bounds on the norm of the queried vector). See [30] for the relevant (standard) background in algorithmic convex geometry. In particular, “oracle polynomial time” means that the algorithm consists of a binary Turing machine that is augmented by the given oracle, and its running time is polynomial in the usual sense, with the understanding that the time required by each call to the oracle is only what is needed to write the question onto, and read the answer from, a tape of the Turing machine. Thus, here we demand that the algorithm outputs a number that is guaranteed to be bounded from above and from below by positive universal constant multiples of $\mathsf{SEP}(\mathbf{X})$ , yet it performs only $n^{O(1)}$ norm evaluations.

Theorem 1 reduces the above task to devising an algorithm that outputs a $O(1)$ -factor approximation to $\operatorname{diam}(B_{\mathbf{X}})$ in oracle polynomial time. Write $\mathbf{X}=\mathsf{S}_{\mathbf{E}}^{n}$ for a symmetric normed space $\mathbf{E}=(\mathbb{R}^{n},\|\cdot\|_{\mathbf{E}})$ . The $\mathsf{S}_{2}^{n}$ -diameter of $B_{\mathbf{X}}$ is equal to the diameter $\operatorname{diam}_{\ell_{2}^{n}}(B_{\mathbf{E}})$ of $B_{\mathbf{E}}\subseteq\mathbb{R}^{n}$ in $\ell_{2}^{n}$ . And, $\mathbf{X}$ has the desired oracle if and only if $\mathbf{E}$ does.⁴⁴4We will use here only the trivial direction of this equivalence, which is simply restricting the oracle for $\mathbf{X}$ to diagonal matrices. The reverse direction incurs the $n^{O(1)}$ - time overhead of computing the singular values of the query matrix. So, the goal is obtaining an oracle polynomial time $O(1)$ -factor approximation algorithm to $\operatorname{diam}_{\ell_{2}^{n}}(B_{\mathbf{E}})$ .

A reduction to efficient Euclidean diameter estimation should give one pause, as the latter task cannot be achieved for general convex bodies, i.e., there is no oracle polynomial time algorithm that outputs a $O(1)$ -factor approximation to the $\ell_{2}^{n}$ -diameter of an arbitrary convex body $K$ in $\mathbb{R}^{n}$ that is given by a weak membership oracle; for deterministic algorithms, this impossibility result was proved in [9], and randomized algorithms were ruled out in [17, 18]. Such hardness of approximation is also proved in [18] for the problem of computing the diameter $\operatorname{diam}_{\ell_{p}^{n}}(\cdot)$ in $\ell_{p}^{n}$ for every $1\leqslant p<\infty$ (see Remark 10 below for a description of the known inapproximability factors). Nevertheless, in the presence of additional symmetries, we will prove the following theorem, which yields the aforementioned algorithm for approximating $\mathsf{SEP}(\mathbf{X})$ using Theorem 1:

Theorem 4.

For every $n\in\mathbb{N}$ , $D\geqslant 1$ and $0<\delta\leqslant\frac{1}{2}$ , there is $d=d(D,\delta)\in\mathbb{N}$ satisfying

d\lesssim D+\frac{\log\left(\frac{1}{\delta}\right)}{\delta},

(8)

such that for every $1\leqslant p\leqslant\infty$ there exists a deterministic algorithm $\mathrm{Alg}_{p}$ that takes as input $n,D,\varepsilon$ and a symmetric normed space $\mathbf{E}=(\mathbb{R}^{n},\|\cdot\|_{\mathbf{E}})$ whose unit ball is given by a weak membership oracle and satisfies

\frac{1}{e^{n^{D}}}\leqslant\|e_{1}\|_{\mathbf{E}}=\ldots=\|e_{n}\|_{\mathbf{E% }}\leqslant e^{n^{D}}.

(9)

The algorithm $\mathrm{Alg}_{p}$ outputs in oracle time $n^{d}$ a number $\mathrm{Alg}_{p}(n,D,\delta,\mathbf{E})$ that satisfies

(1-\delta)\operatorname{diam}_{\ell_{p}^{n}}(B_{\mathbf{E}})\leqslant\mathrm{% Alg}_{p}(n,D,\delta,\mathbf{E})\leqslant(1+\delta)\operatorname{diam}_{\ell_{p% }^{n}}(B_{\mathbf{E}}).

(10)

1.1 Reverse Faber–Krahn

The new ingredient of our proof of Theorem 2 is an asymptotic evaluation of the spectral gap of the Laplacian with Dirichlet boundary conditions on the unit ball $B_{\mathbf{X}}\subseteq\mathsf{M}_{n}(\mathbb{R})$ of any unitarily invariant norm $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ . We will next describe this; all of the relevant (classical and rudimentary) background on the spectral properties of the Dirichlet Laplacian can be found in [60, 21].

Fix $n\in\{2,3,\ldots\}$ . For a bounded domain $\Omega\subseteq\mathbb{R}^{n}$ , let $\lambda(\Omega)$ be the smallest $\lambda>0$ such that there exists a function $f:\Omega\to\mathbb{R}$ that is smooth on the interior of $\Omega$ , vanishes on the boundary $\partial\Omega$ of $\Omega$ , and satisfies $\Delta f=-\lambda f$ on the interior of $\Omega$ , where $\Delta=\sum_{i=1}^{n}\partial^{2}/(\partial x_{i}^{2})$ is the standard Laplacian on $\mathbb{R}^{n}$ . Set $\lambda(\mathbf{Y})=\lambda(B_{\mathbf{Y}})$ for each normed space $\mathbf{Y}=(\mathbb{R}^{n},\|\cdot\|_{\mathbf{Y}})$ . Here, we obtain the following result:

Theorem 5.

Every unitarily invariant normed space $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ satisfies:

\lambda(\mathbf{X})\asymp n^{3}\|\mathsf{I}_{n}\|_{\mathbf{X}}^{2}.

(11)

In the setting of Theorem 5, the following asymptotic equivalence is a different way to express (11):

\lambda(B_{\mathbf{X}})\mathrm{vol}_{\dim(\mathbf{X})}^{\frac{2}{\dim(\mathbf{% X})}}(B_{\mathbf{X}})\asymp\dim(\mathbf{X}),

(12)

where for $m\in\mathbb{N}$ and $0\leqslant\alpha\leqslant m$ the $\alpha$ -dimensional Hausdorff measure on $\mathbb{R}^{m}$ is denoted $\mathrm{vol}_{\alpha}(\cdot)$ ; the only values of $\alpha$ that occur herein are $\alpha\in\{m,m-1\}$ (Lebesgue measure and surface area measure, respectively). To see that (12) and (11) coincide, note that $\dim(\mathbf{X})=n^{2}$ and by [65, equation (2.2)] we have:

\mathrm{vol}_{n^{2}}(B_{\mathbf{X}})^{\frac{1}{n^{2}}}\asymp\frac{1}{\sqrt{n}% \|\mathsf{I}_{n}\|_{\mathbf{X}}}.

(13)

The Faber–Krahn inequality [23, 42] (originally conjectured in [61]) states that the left hand side of (12) is minimized when $B_{\mathbf{X}}$ is replaced by the unit ball of the standard Euclidean metric (in our case $\mathsf{S}_{2}^{n}$ , though the analogous statement holds if $\mathsf{M}_{n}(\mathbb{R})$ is replaced by $\mathbb{R}^{m}$ of any dimension). By a direct computation (see e.g. [55, page 32]), this classical extremal statement implies that the left hand side of (12) is bounded from below by a positive universal constant multiple of $\dim(\mathbf{X})$ .

The new content of (12) is thus the reverse inequality, i.e., the estimate $\lambda(\mathbf{X})\lesssim n^{3}\|\mathsf{I}_{n}\|_{\mathbf{X}}^{2}$ in Theorem 5. This confirms for (unit balls of) unitarily invariant matrix norms the following much more general (and still open) reverse Faber–Krahn phenomenon that was conjectured in [55]:

Conjecture 6 (reverse Faber–Krahn).

For every origin-symmertric convex body $K\subseteq\mathbb{R}^{m}$ (thus, $x\in K$ if and only if $-x\in K$ ) there exists a volume-preserving linear transformation $S\in\mathsf{SL}_{m}(\mathbb{R})$ with $\lambda(SK)\mathrm{vol}_{m}(K)^{2/m}\asymp m$ .

Theorem 5 demonstrates that Conjecture 6 holds for any unitarily invariant norm on $\mathsf{M}_{n}(\mathbb{R})\cong\mathbb{R}^{n^{2}}$ with the matrix $S$ being the ( $n^{2}$ -by- $n^{2}$ ) identity on $\mathsf{M}_{n}(\mathbb{R})$ ; this too was conjectured in [55] (see Conjecture 50 there, as well as [55, Problem 44] and [55, Remark 172]).

1.2 Weak isomorphic reverse isoperimetry

It was proved in [55] that Theorem 5 implies Theorem 1. The link between these two results is Theorem 7 below. For its formulation, recall that the isoperimetric quotient of a convex body $K\subseteq\mathbb{R}^{m}$ is defined to be $\mathrm{iq}(K)=\mathrm{vol}_{m-1}(\partial K)/\mathrm{vol}_{m}(K)^{1-1/m}$ .

Theorem 7.

For every $n\in\mathbb{N}$ , if $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ is a unitarily invariant normed space, then there exists an origin-symmetric convex body $L\subseteq B_{\mathbf{X}}$ such that:

\mathrm{vol}_{n^{2}}(L)^{\frac{1}{n^{2}}}\gtrsim\mathrm{vol}_{n^{2}}(B_{% \mathbf{X}})^{\frac{1}{n^{2}}}\qquad\mathrm{yet}\qquad\mathrm{iq}(L)\lesssim n.

(14)

It was proved in [55, Section 1.6.2] that for each unitarily invariant normed space $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ , the validity of Theorem 5 for $\mathbf{X}$ is equivalent to the validity of Theorem 7 for $\mathbf{X}$ ; see specifically the explanation why [55, Conjecture 49] and [55, Conjecture 50] are equivalent that appears in [55, page 43], for which equation (1.62) of [55] is crucial input, as well as the convexity and uniqueness of the so-called Cheeger body (see page 31 of [55]), per [2]. Therefore, by proving Theorem 5 we will also establish Theorem 7, but we will next briefly explain the meaning of Theorem 7 and its utility for proving Theorem 1.

For $m\in\mathbb{N}$ , the isoperimetric theorem implies that the isoperimetric quotient of a convex body $K\subseteq\mathbb{R}^{m}$ is at least the isoperimetric quotient of the $\ell_{2}^{m}$ -ball. Direct computation shows that the latter is bounded from above and from below by positive universal constant multiples of $\sqrt{m}$ . Thus, Theorem 7 says that one can inscribe in $B_{\mathbf{X}}$ an origin-symemtric convex body $L$ that is large in the sense that the first inequality in (14) holds, yet its isoperimetric quotient is as small as possible up to universal constant factors, i.e., $\mathrm{iq}(L)$ has the same order of magnitude as the isoperimetric quotient of the Hilbert–Schmidt unit ball in $\mathsf{M}_{n}(\mathbb{R})$ . This confirms for (unit balls of) unitarily invariant matrix norms the following much more general (and still open) phenomenon that was conjectured in [55]:

Conjecture 8 (weak isomorphic reverse isoperimetry).

⁵⁵5The adjective “weak” was used in [55] to describe this conjecture because in [55] a stronger phenomenon was also conjectured; we do not need to recall that stronger conjecture because the present work does not address it, and furthermore its weaker variant that we establish herein suffices for proving Theorem 1.For every origin-symmetric convex body $K\subseteq\mathbb{R}^{m}$ there exist $\mathsf{S}\in\mathsf{SL}_{m}(\mathbb{R})$ and an origin-symmetric convex body $L\subseteq\mathsf{S}K$ that satisfies:

\mathrm{vol}_{m}(L)^{\frac{1}{m}}\gtrsim\mathrm{vol}_{m}(B_{\mathbf{X}})^{% \frac{1}{m}}\qquad\mathrm{yet}\qquad\mathrm{iq}(L)\lesssim\sqrt{m}.

Analogously to the discussion in Section 1.1, Theorem 7 demonstrates that Conjecture 8 holds for any unitarily invariant norm on $\mathsf{M}_{n}(\mathbb{R})$ with the matrix $\mathsf{S}$ being the identity on $\mathsf{M}_{n}(\mathbb{R})$ ; this too was conjectured in [55] (see specifically Conjecture 49 there).

By [55], the upper bound on $\mathsf{SEP}(\mathbf{X})$ of Theorem 1 (which, as we explained earlier, is the part of Theorem 1 that remained to be proved because the matching lower bound is due to [55]) follows from Theorem 7; specifically, combine [55, Corollary 79] with equation (2.2) of [65], which is reproduced as equation (6.131) in [55]. The resulting construction in [55] of the random partition of $\mathbf{X}$ can be illustrated informally as follows. Let $L\subseteq B_{\mathbf{X}}$ be the auxiliary convex body that Theorem 1 provides. Iteratively remove random translates⁶⁶6One must define a suitable distribution of those random shifts here; for the purpose of the present sketch, one could aim instead to obtain a separated partition of an arbitrarily large bounded domain in $\mathsf{M}_{n}(\mathbb{R})$ , in which case the shifts can be chosen Lebesgue-uniformly at random. of $L$ from $\mathsf{M}_{n}(\mathbb{R})$ ; this yields almost surely a random partition of $\mathsf{M}_{n}(\mathbb{R})$ into sets (translates of $L$ minus the union of those translates from the preceding steps of this random iterative removal) that are of $\mathbf{X}$ -diameter at most $1$ , as $L\subseteq B_{\mathbf{X}}$ , and [55] demonstrates that the desired estimate on the separation probability holds thanks to the upper bound on the isoperimetric quotient of $L$ in (14).

$\blacktriangleright$ Remark 9.

While the above procedure yields a random partition of $\mathbf{X}$ whose separation modulus is optimal up to universal constant factors, it is not entirely constructive. From the algorithmic perspective it suffices to bound $\mathsf{SEP}(\mathbf{X})$ from above, per Theorem 4 and the discussion that precedes its statement, as by [45] there is a randomized polynomial time algorithm that takes as input any finite subset $\mathscr{C}$ of $\mathbf{X}$ and outputs a $2\mathsf{SEP}(\mathbf{X})$ -separating partition of $\mathscr{C}$ . One could hope to extract more algorithmic information by assuming that $B_{\mathbf{X}}$ has a weak membership oracle and aiming to obtain a convex body $L$ as in Theorem 1 which also has a weak membership oracle that is allowed to make $n^{O(1)}$ calls to the oracle of $B_{\mathbf{X}}$ and $n^{O(1)}$ additional Turing machine operations. We do not currently have this because the body $L$ of Theorem 1 is defined implicitly as the solution of a variational problem. We expect that the aforementioned task could be achieved by computing in oracle polynomial time a sufficiently good approximation to the first nontrivial eigenfunction $\varphi:B_{\mathbf{X}}\to\mathbb{R}$ of the Dirichlet Laplacian on $B_{\mathbf{X}}$ , i.e., $\varphi$ is smooth on the interior of $B_{\mathbf{X}}$ , it vanishes on $\partial B_{\mathbf{X}}$ , and $-\Delta\varphi=\lambda(\mathbf{X})\varphi$ point-wise. By [14] we know that $\varphi$ is a log-concave function, whence its sub-level sets are convex. We could then repeat the above procedure with $L$ replaced a suitable sub-level set of $\varphi$ . We conjecture that this will yield an optimal separating partition of (a large bounded domain of) $\mathbf{X}$ , and it remains open to implement the above strategy efficiently.

The above proposal is an (especially interesting) instance of a general program to estimate efficiently (in oracle polynomial time) solutions of geometrically meaningful partial differential equations; another important example is the first nontrivial eigenfunction of the Laplacian on a convex body with Neumann boundary conditions, which controls the Kannan–Lovász–Simonovits conjecture [36]; see [52, 48].

2 Proof of Theorem 5

Proof.

Fix $n\in\mathbb{N}$ . It was proved in [55, Remark 172] that if Theorem 7 holds for $\mathsf{S}_{\infty}^{n}$ , then Theorem 7 holds for every unitarily invariant normed space $\mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}})$ . By the equivalence of Theorem 5 and Theorem 7 that was proved in [55] and we discussed in Section 1.2, it therefore suffices to prove Theorem 5 when $\mathbf{X}=\mathsf{S}_{\infty}^{n}$ , where we recall that $\mathsf{S}_{\infty}^{n}$ is $\mathsf{M}_{n}(\mathbb{R})$ equipped with the $\ell_{2}^{n}\to\ell_{2}^{n}$ operator norm. So, our goal in the rest of this section will be to demonstrate that $\lambda(\mathsf{S}_{\infty}^{n})\asymp n^{3}$ . Only the upper bound

\lambda(\mathsf{S}_{\infty}^{n})\lesssim n^{3}

(15)

remains to be proved, thanks to the Faber–Krahn inequality, as we explained in Section 1.1.

For every $p,n\in\mathbb{N}$ define a function $f_{n}^{p}:B_{\mathsf{S}_{\infty}^{n}}\to[0,\infty)$ by setting:

\forall\mathsf{A}\in B_{\mathsf{S}_{\infty}^{n}},\qquad f_{n}^{p}(\mathsf{A})% \stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{det}\big(\mathsf{I}_{n}-% \mathsf{A}\mathsf{A}^{\!*}\big)^{p}=\prod_{k=1}^{n}\big(1-s_{k}(\mathsf{A})^{2% }\big)^{p}.

(16)

Then, $f_{n}^{p}$ is smooth (in fact, it is a polynomial in the entries of $\mathsf{A}$ ), and the second equality in (16) makes it evident that $f_{n}^{p}$ vanishes on $\partial B_{\mathsf{S}_{\infty}^{n}}=\{\mathsf{A}\in\mathsf{M}_{n}(\mathbb{R})% :\ s_{1}(\mathsf{A})=1\}$ . The standard (see e.g. [21]) Rayleigh quotient characterization of the smallest nonzero Dirichlet eigenvalue of $(-\Delta)$ therefore gives:

\lambda(\mathsf{S}_{\infty}^{n})\leqslant\frac{\int_{B_{\mathsf{S}_{\infty}^{n% }}}\|\nabla f_{n}^{p}(\mathsf{A})\|_{\mathsf{S}_{2}^{n}}^{2}\,\mathrm{d}% \mathsf{A}}{\int_{B_{\mathsf{S}_{\infty}^{n}}}f_{n}^{p}(\mathsf{A})^{2}\,% \mathrm{d}\mathsf{A}}.

(17)

Theorem 5 will thus be proven if we will evaluate exactly the right hand side of (17) as follows:

\frac{\int_{B_{\mathsf{S}_{\infty}^{n}}}\|\nabla f_{n}^{p}(\mathsf{A})\|_{% \mathsf{S}_{2}^{n}}^{2}\,\mathrm{d}\mathsf{A}}{\int_{B_{\mathsf{S}_{\infty}^{n% }}}f_{n}^{p}(\mathsf{A})^{2}\,\mathrm{d}\mathsf{A}}=\frac{pn^{2}(4p+n)^{2}}{2(% 2p-1)(4p+1)}.

(18)

Indeed, the right hand side of (18) is bounded from above and from below by positive universal constant multiples of $n^{2}\max\{n^{2}/p,p\}$ . Therefore, up to universal constant factors setting $p=n$ minimizes the right hand side of (18). For this choice of $p$ , the Rayleigh quotient estimate (17) becomes $\lambda(\mathsf{S}_{\infty}^{n})\lesssim n^{3}$ , which is our current goal (15). Observe that the above reasoning shows that any choice of $p$ other than $p\asymp n$ does not yield the desired estimate (15) . The rest of this section will be devoted to establishing (18).

Given $n\in\mathbb{N}$ , we will denote by $V_{n}:\mathbb{R}^{n}\to[0,\infty)$ the following (Vendermunde determinant) function:

\forall x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n},\qquad V_{n}(x)\stackrel{{% \scriptstyle\mathrm{def}}}{{=}}\prod_{i=1}^{n-1}\prod_{j=i+1}^{n}|x_{i}-x_{j}|.

(19)

Define a probability density $\mathfrak{J}_{n}^{p}:[0,1]^{n}\to[0,\infty)$ by setting:

\forall x=(x_{1},\ldots,x_{n})\in[0,1]^{n},\qquad\mathfrak{J}_{n}^{p}(x)% \stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{V_{n}(x)}{Z_{n}(p)}\prod_{r=1}% ^{n}\frac{x_{r}^{2p}}{\sqrt{1-x_{r}}},

(20)

where $Z_{n}(p)>0$ denotes the normalization factor such that $\int_{[0,1]^{n}}\mathfrak{J}_{n}^{p}(x)\,\mathrm{d}x=1$ , i.e.,

Z_{n}(p)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\int_{[0,1]^{n}}V_{n}(x)% \prod_{r=1}^{n}\frac{x_{r}^{2p}}{\sqrt{1-x_{r}}}\,\mathrm{d}x=\frac{n!}{\pi^{% \frac{n}{2}}}\prod_{s=1}^{n}\frac{\Gamma\big(2m+\frac{1}{2}(s+1)\big)\Gamma% \big(\frac{1}{2}s\big)^{2}}{\Gamma\big(2m+\frac{1}{2}(n+s+1)\big)}.

(21)

The second equality in (21) is a special case of the classical Selberg integral formula [66]. The parameter $Z_{n}(p)$ is commonly denoted in the literature (see e.g. [27]) as $S_{n}(\alpha,\beta,\upgamma)$ for the setting of parameters $(\alpha,\beta,\upgamma)=(2p+1,1/2,1/2)$ ; using the ad hoc shorter notation $Z_{n}(p)$ is beneficial here since we will not need to consider probability densities other than $\mathfrak{J}_{n}^{p}$ . Also, we chose to use the letter $\mathfrak{J}$ for the probability density on $[0,1]^{n}$ in (20) to indicate that it belongs to the $3$ -parameter family of densities of Jacobi random $n$ -by- $n$ matrix ensembles; specifically, using the parametrization of [3, equation (4.1.5)], the relevant setting of parameters in the present case are $(\beta,r,s)=(1,4p+1,0)$ .

There exists $c_{n}>0$ such that for every Borel-measurable function $f:[0,\infty)^{n}\to[0,\infty)$ that is invariant under permutations of the coordinates, i.e., $f(s_{\pi(1)},\ldots,s_{\pi(n)})=f(s)$ for every permutation $\pi\in S_{n}$ and every point $s=(s_{1},\ldots,s_{n})\in[0,\infty)^{n}$ , the following identity holds:

\int_{\mathsf{M}_{n}(\mathbb{R})}f\big(s_{1}(\mathsf{A}),\ldots,s_{n}(\mathsf{% A})\big)\,\mathrm{d}A=c_{n}\int_{[0,\infty)^{n}}f(s)\prod_{i=1}^{n-1}\prod_{j=% s+1}^{n}\big|s_{i}^{2}-s_{j}^{2}\big|\,\mathrm{d}s.

(22)

(22) is a special case of the Weyl integration formula [74]; see e.g. [3, Proposition 4.1.3]. The exact value of the parameter $c_{n}$ will not have any role in the ensuing reasoning (it will cancel out in our computations), but it is worthwhile to note in passing that $c_{n}^{1/n^{2}}\asymp 1/\sqrt{n}$ ; see e.g. [26] for much more on such matters. Thanks to (22), the denominator in the left hand side of (18) can be evaluated as follows:

\int_{B_{\mathsf{S}_{\infty}^{n}}}f_{n}^{p}(\mathsf{A})^{2}\,\mathrm{d}\mathsf% {A}\stackrel{{\scriptstyle\eqref{testfxndef}\wedge\eqref{eq:weyl}}}{{=}}c_{n}% \int_{[0,1]^{n}}\prod_{r=1}^{n}\big(1-s_{r}^{2}\big)^{2p}\prod_{i=1}^{n-1}% \prod_{j=s+1}^{n}\big|s_{i}^{2}-s_{j}^{2}\big|\,\mathrm{d}x\stackrel{{% \scriptstyle\eqref{normalization formula}}}{{=}}\frac{c_{n}}{2^{n}}Z_{n}(p),

(23)

where for the last step of (23) we applied the change of variable $s=(\sqrt{1-x_{1}},\ldots,\sqrt{1-x_{n}})$ , whose Jacobian is $(-1)^{n}/(2^{n}\prod_{r=1}^{n}\sqrt{1-x_{r}})$ .

We need to understand the Hilbert–Schmidt norm of the gradient of $(\mathsf{A}\in B_{\mathsf{S}_{\infty}^{n}})\mapsto f_{n}^{p}(\mathsf{A})$ . For this, as a special case of [51, Theorem 7.1] we see that if we define $g_{n}^{p}:\mathbb{R}^{n}\to\mathbb{R}$ by

\forall x\in\mathbb{R}^{n},\qquad g_{n}^{p}(x)\stackrel{{\scriptstyle\mathrm{% def}}}{{=}}\prod_{i=1}^{n}\big(1-x_{i}^{2}\big)^{p},

(24)

then for any matrix $\mathsf{A}$ in the interior of $B_{\mathsf{S}_{\infty}^{n}}$ there are $\mathsf{U}=\mathsf{U}_{\mathsf{A},n,p},\mathsf{V}=\mathsf{V}_{\mathsf{A},n,p}% \in\mathsf{O}_{n}$ such that

	$\displaystyle\nabla f_{n}^{p}(\mathsf{A})$
	$\displaystyle=\mathsf{U}\begin{pmatrix}\frac{\partial g_{n}^{p}}{\partial x_{1% }}\big(s_{1}(\mathsf{A}),\ldots,s_{n}(\mathsf{A})\big)&0&\dots&0\\ 0&\frac{\partial g_{n}^{p}}{\partial x_{2}}\big(s_{1}(\mathsf{A}),\ldots,s_{n}% (\mathsf{A})\big)&\ddots&\vdots\\ \vdots&\ddots&\ddots&0\\ 0&\dots&0&\frac{\partial g_{n}^{p}}{\partial x_{n}}\big(s_{1}(\mathsf{A}),% \ldots,s_{n}(\mathsf{A})\big)\end{pmatrix}\mathsf{V}.$

By substituting the definition (24) of $g_{n}^{p}$ , we thus have:

\nabla f_{n}^{p}(\mathsf{A})=2p\prod_{i=1}^{n}\big(1-s_{i}(\mathsf{A})^{2}\big% )^{p}\mathsf{U}\begin{pmatrix}\frac{s_{1}(\mathsf{A})}{1-s_{1}(\mathsf{A})^{2}% }&0&\dots&0\\ 0&\frac{s_{2}(\mathsf{A})}{1-s_{2}(\mathsf{A})^{2}}&\ddots&\vdots\\ \vdots&\ddots&\ddots&0\\ 0&\dots&0&\frac{s_{n}(\mathsf{A})}{1-s_{n}(\mathsf{A})^{2}}\end{pmatrix}% \mathsf{V}.

Since $\mathsf{U}$ and $\mathsf{V}$ are orthogonal matrices, we therefore have:

\|\nabla f_{n}^{p}(\mathsf{A})\|_{\mathsf{S}_{2}^{n}}^{2}=4p^{2}\prod_{r=1}^{n% }\big(1-s_{r}(\mathsf{A})^{2}\big)^{2p}\sum_{k=1}^{n}\frac{s_{k}(\mathsf{A})^{% 2}}{\left(1-s_{k}(\mathsf{A})^{2}\right)^{2}}.

(25)

Consequently, the numerator in the left hand side of (18) can be evaluated as follows:

\displaystyle\begin{split}\int_{B_{\mathsf{S}_{\infty}^{n}}}&\|\nabla f_{n}^{p% }(\mathsf{A})\|_{\mathsf{S}_{2}^{n}}^{2}\,\mathrm{d}\mathsf{A}\\ &\ \stackrel{{\scriptstyle\eqref{eq:weyl}\wedge\eqref{eq:norm of gradient}}}{{% =}}4p^{2}c_{n}\int_{[0,1]^{n}}\left(\sum_{k=1}^{n}\frac{s_{k}^{2}}{\left(1-s_{% k}^{2}\right)^{2}}\right)\prod_{r=1}^{n}\big(1-s_{r}^{2}\big)^{2p}\prod_{i=1}^% {n-1}\prod_{j=s+1}^{n}\big|s_{i}^{2}-s_{j}^{2}\big|\,\mathrm{d}x\\ &\ \ \ \ \stackrel{{\scriptstyle\eqref{eq:J density def}}}{{=}}\frac{c_{n}Z_{n% }(p)}{2^{n}}4p^{2}\int_{[0,1]^{n}}\sum_{k=1}^{n}\frac{1-x_{k}}{x_{k}^{2}}% \mathfrak{J}_{n}^{p}(x)\,\mathrm{d}x\\ &\ \ \ \ \ \,=\frac{c_{n}Z_{n}(p)}{2^{n}}4p^{2}n\bigg(\int_{[0,1]^{n}}\frac{% \mathfrak{J}_{n}^{p}(x)}{x_{n}^{2}}\,\mathrm{d}x-\int_{[0,1]^{n}}\frac{% \mathfrak{J}_{n}^{p}(x)}{x_{n}}\,\mathrm{d}x\bigg),\end{split}

(26)

where the second step of (26) makes the same change of variable $s=(\sqrt{1-x_{1}},\ldots,\sqrt{1-x_{n}})$ as above. By combining (23) and (26) we obtain the following expression for the Rayleigh quotient in (18):

\displaystyle\begin{split}\frac{\int_{B_{\mathsf{S}_{\infty}^{n}}}\|\nabla f_{% n}^{p}(\mathsf{A})\|_{\mathsf{S}_{2}^{n}}^{2}\,\mathrm{d}\mathsf{A}}{\int_{B_{% \mathsf{S}_{\infty}^{n}}}|f_{n}^{p}(\mathsf{A})|^{2}\,\mathrm{d}\mathsf{A}}&=4% p^{2}\int_{[0,1]^{n}}\Big(\sum_{s=1}^{n}\frac{1-x_{s}}{x_{s}^{2}}\Big)% \mathfrak{J}_{n}^{p}(x)\,\mathrm{d}x\\ &=4p^{2}n\bigg(\int_{[0,1]^{n}}\frac{\mathfrak{J}_{n}^{p}(x)}{x_{n}^{2}}\,% \mathrm{d}x-\int_{[0,1]^{n}}\frac{\mathfrak{J}_{n}^{p}(x)}{x_{n}}\,\mathrm{d}x% \bigg).\end{split}

(27)

To evaluate the right hand side of (27), consider the following symmetric polynomial $P\in\mathbb{Q}[x_{1},\ldots x_{n}]$ :

P(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{s=1}^{n}\prod_{t\in[n]% \smallsetminus\{s\}}x_{t}^{2}+\frac{2}{3}\sum_{s=1}^{n-1}\sum_{t=s+1}^{n}x_{s}% x_{t}\prod_{k\in[n]\smallsetminus\{s,t\}}x_{k}^{2},

(28)

where in (28), and throughout, we use the common notation $[n]\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{1,\ldots,n\}$ . Thus,

\displaystyle\begin{split}\frac{1}{Z_{n}(p)}\int_{[0,1]^{n}}&P(x)V_{n}(x)\prod% _{s=1}^{n}\frac{x_{s}^{2p-2}}{\sqrt{1-x_{s}}}\,\mathrm{d}x\\ &\stackrel{{\scriptstyle\eqref{eq:J density def}}}{{=}}n\int_{[0,1]^{n}}\frac{% \mathfrak{J}_{n}^{p}(x)}{x_{n}^{2}}\,\mathrm{d}x+\frac{n(n-1)}{3}\int_{[0,1]^{% n}}\frac{\mathfrak{J}_{n}^{p}(x)}{x_{n-1}x_{n}}\,\mathrm{d}x.\end{split}

(29)

The final integral that appears in (29) can be evaluated as follows:

\int_{[0,1]^{n}}\frac{\mathfrak{J}_{n}^{p}(x)}{x_{n-1}x_{n}}\,\mathrm{d}x\\ \stackrel{{\scriptstyle\eqref{eq:J density def}}}{{=}}\frac{1}{Z_{n}(p)}\int_{% [0,1]^{n}}V_{n}(x)\bigg(\prod_{t=1}^{n-2}x_{t}\bigg)\prod_{s=1}^{n}\frac{x_{s}% ^{2p-1}}{\sqrt{1-x_{s}}}\,\mathrm{d}x=\frac{(4p+n)(4p+n+1)}{4p(4p+1)},

(30)

where the second equality that appears in (30) is an instantiation of the Aomoto integral formula [6] (see also e.g. [5, Theorem 8.1.2]). To evaluate the integral that appears in the left hand side of (29), observe that the polynomial $P$ that is defined in (28) coincides with the Jack polynomial that is denoted in [27] by $P^{(1/\upgamma)}_{\lambda}$ , where $\upgamma=1/2$ and $\lambda$ is the vector in $\mathbb{Z}^{n}$ whose first $n-1$ coordinates equal $2$ and the whose last coordinate equals $0$ ; this is seen by substituting the aforementioned parameters $\upgamma,\lambda$ into equations (3.2) and (3.10) of [27]. The Kadell integral formula [35], which appears in [27] as equation (3.13) thus gives:

\frac{1}{Z_{n}(p)}\int_{[0,1]^{n}}P(x)V_{n}(x)\prod_{s=1}^{n}\frac{x_{s}^{2p-2% }}{\sqrt{1-x_{s}}}\,\mathrm{d}x=\frac{n(n+2)(4p+n)(4p+n-2)}{24p(2p-1)}.

(31)

The first integral that appears in the right hand side of (27) is therefore evaluated as follows:

\displaystyle\begin{split}\int_{[0,1]^{n}}&\frac{\mathfrak{J}_{n}^{p}(x)}{x_{n% }^{2}}\,\mathrm{d}x\\ &\stackrel{{\scriptstyle\eqref{eq:integrate P}\wedge\eqref{eq:n-2}\wedge\eqref% {eq:use kadell}}}{{=}}\frac{(n+2)(4p+n)(4p+n-2)}{24p(2p-1)}-\frac{(n-1)(4p+n)(% 4p+n+1)}{12p(4p+1)}.\end{split}

(32)

Now, the second integral that appears in the right hand side of (27) can be evaluated as follows:

\int_{[0,1]^{n}}\frac{\mathfrak{J}_{n}^{p}(x)}{x_{n}}\,\mathrm{d}x\stackrel{{% \scriptstyle\eqref{eq:J density def}}}{{=}}\frac{1}{Z_{n}(p)}\int_{[0,1]^{n}}V% _{n}(x)\bigg(\prod_{t=1}^{n-1}x_{t}\bigg)\prod_{s=1}^{n}\frac{x_{s}^{2p-1}}{% \sqrt{1-x_{s}}}\,\mathrm{d}x=\frac{4p+n}{4p},

(33)

where the second step of (33) is another instantiation of the Aomoto integral formula. The desired identity (18) follows by substituting (32) and (33) into (27), and then simplifying the resulting expression. $\hfill\blacktriangleleft$

3 Proof of Theorem 4

Proof.

Observe that every $x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ satisfies the following estimate:

\displaystyle\begin{split}\|x\|_{\mathbf{E}}\stackrel{{\scriptstyle\eqref{eq:1% symmetric}}}{{=}}\max_{s\in[n]}&\frac{\|x\|_{\mathbf{E}}+\|(-x_{1},\ldots,-x_% {s-1},x_{s},-x_{s+1},\ldots,-x_{n})\|_{\mathbf{E}}}{2}\\ &\geqslant\max_{s\in[n]}|x_{s}|\cdot\|e_{s}\|_{\mathbf{E}}\stackrel{{% \scriptstyle\eqref{eq:norms are reasonable}}}{{\geqslant}}\frac{\|x\|_{\ell_{2% }^{n}}}{\sqrt{n}e^{n^{D}}},\end{split}

(34)

where the penultimate step of (34) is an application of the covexity of $\|\cdot\|_{\mathbf{E}}$ . Furthermore:

\|x\|_{\mathbf{E}}\leqslant\sum_{s=1}^{n}|x_{s}|\cdot\|e_{s}\|_{\mathbf{E}}% \stackrel{{\scriptstyle\eqref{eq:norms are reasonable}}}{{\leqslant}}e^{n^{D}}% \sum_{s=1}^{n}|x_{s}|\leqslant\sqrt{n}e^{n^{D}}\|x\|_{\ell_{2}^{n}},

(35)

where the first step of (35) is an application of the triangle inequality for $\|\cdot\|_{\mathbf{E}}$ and last step of (35) is an application of Cauchy–Schwarz. Therefore:

\frac{1}{\sqrt{n}e^{n^{D}}}B_{\!\ell_{2}^{n}}\stackrel{{\scriptstyle\eqref{eq:% use Cauchy schwarz}}}{{\subseteq}}B_{\mathbf{E}}\stackrel{{\scriptstyle\eqref{% eq:use convexity}}}{{\subseteq}}\sqrt{n}e^{n^{D}}\!\!B_{\!\ell_{2}^{n}}.

(36)

Using the terminology of [30], the inclusions (36) mean that $B_{\mathbf{E}}$ is well–bounded and centered. Since in Theorem 4 we are assuming that $B_{\mathbf{E}}$ is given by a weak membership oracle, the Judin–Nemirovskiĭ theorem [34] (see [30, Section 4.3]), which is a striking application of the Shallow-Cut Ellipsoid Method [34] (see [30, Section 3.3]), implies it is possible to optimize linear functionals efficiently on $B_{\mathbf{E}}$ . In particular, since the dual norm $\|\cdot\|_{\mathbf{E}^{*}}$ is given by $\|x\|_{\mathbf{E}^{*}}=\max_{y\in B_{\mathbf{E}}}\langle x,y\rangle$ for every $x\in\mathbb{R}^{n}$ , where $\langle\cdot,\cdot\rangle:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}$ denotes the standard scalar product on $\mathbb{R}^{n}$ , it follows that there is an algorithm $\mathrm{Eval}_{\mathbf{E}^{*}}$ which takes as input $x\in\mathbb{R}^{n}$ and outputs in oracle time that is polynomial in both $\log(1/\delta)$ and $n^{D}$ a number $\mathrm{Eval}_{\mathbf{E}^{*}}\!(x)\in[0,\infty)$ that is guaranteed to satisfy the following estimates:

\Big(1-\frac{\delta}{2}\Big)\|x\|_{\mathbf{E}^{*}}\leqslant\mathrm{Eval}_{% \mathbf{E}^{*}}\!(x)\leqslant\Big(1+\frac{\delta}{2}\Big)\|x\|_{\mathbf{E}^{*}}.

(37)

Define $q=p/(p-1)$ if $p>1$ , and $q=\infty$ if $p=1$ . By [29, Lemma 2], if we denote

K_{q}^{n}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\big\{a=(a_{1},\ldots,a_{n}% )\in\mathbb{R}^{n}:\ \|a\|_{\ell_{q}^{n}}\leqslant 1\ \mathrm{and}\ a_{1}% \geqslant a_{2}\geqslant\cdots\geqslant a_{n}\geqslant 0\big\},

(38)

then for every $0<\delta<1$ there exists a subset $\mathcal{G}(n,q,\delta)$ of $K_{q}^{n}$ such that:

\forall x\in K_{q}^{n},\quad d_{\ell_{q}^{n}}\big(x,\mathcal{G}(n,q,\delta)% \big)=\min_{a\in\mathcal{G}(n,q,\delta)}\|x-a\|_{\ell_{q}^{n}}\leqslant\frac{% \delta}{2},

(39)

i.e., $\mathcal{G}(n,q,\delta)$ is $(\delta/2)$ -dense in $K_{q}^{n}$ with respect to the $\ell_{q}^{n}$ norm, yet its size satisfies:

|\mathcal{G}(n,q,\delta)|\leqslant n^{\frac{2\log\left(\frac{30}{\delta}\right% )}{\log\left(1+\frac{\delta}{6}\right)}}.

(40)

So, by (40) for fixed $\delta$ the size of $\mathcal{G}(n,q,\delta)$ grows like a fixed power of $n$ , in marked contrast to the fact (which is a straightforward consequence of volume comparison) that every $(\delta/2)$ -dense subset of a unit ball of an $n$ -dimensional normed space must have size at least $(2/\delta)^{n}$ .

The algorithm $\mathrm{Alg}_{p}$ of Theorem 4 evaluates $\mathrm{Eval}_{\mathbf{E}^{*}}\!(a)$ for each $a\in\mathcal{G}(n,q,\delta)$ and outputs the number:

\mathrm{Alg}_{p}(n,D,\delta,\mathbf{E})\stackrel{{\scriptstyle\mathrm{def}}}{{% =}}2\max_{a\in\mathcal{G}(n,q,\delta)}\mathrm{Eval}_{\mathbf{E}^{*}}\!(a).

(41)

The oracle running time of this simple procedure is a polynomial in both $\log(1/\delta)$ and $n^{D}$ times the size of $\mathcal{G}(n,q,\delta)$ , so by (40) it is at most $n^{d}$ where the degree $d$ satisfies the desired bound (8). Furthermore:

\operatorname{diam}_{\ell_{p}^{n}}(B_{\mathbf{E}})=2\sup_{x\in B_{\mathbf{E}}}% \|x\|_{\ell_{p}^{n}}=2\sup_{x\in B_{\mathbf{E}}}\sup_{y\in B_{\ell_{q}^{n}}}% \langle x,y\rangle=2\sup_{y\in B_{\ell_{q}^{n}}}\sup_{x\in B_{\mathbf{E}}}% \langle x,y\rangle=2\sup_{y\in B_{\ell_{q}^{n}}}\|x\|_{\mathbf{E}^{*}}.

(42)

Since $\mathcal{G}(n,q,\delta)$ is a subset of $B_{\ell_{q}^{n}}$ , this implies in particular that the following a priori upper bound on the output of $\mathrm{Alg}_{p}$ holds, which gives the second inequality in the desired conclusion (10) of Theorem 4:

	$\displaystyle\mathrm{Alg}_{p}(n,D,\delta,\mathbf{E})$	$\displaystyle\stackrel{{\scriptstyle\eqref{eq:alg for E star}\wedge\eqref{eq:% def our alg}}}{{\leqslant}}2\max_{a\in\mathcal{G}(n,q,\delta)}\Big(1+\frac{% \delta}{2}\Big)\\|a\\|_{\mathbf{E}^{*}}$
		$\displaystyle\leqslant 2\Big(1+\frac{\delta}{2}\Big)\sup_{y\in B_{\ell_{q}^{n}% }}\\|x\\|_{\mathbf{E}^{*}}\stackrel{{\scriptstyle\eqref{eq:duality}}}{{\leqslant% }}\Big(1+\frac{\delta}{2}\Big)\operatorname{diam}_{\ell_{p}^{n}}(B_{\mathbf{E}% }).$

Define $\mathscr{D}(n,q,\delta)\subseteq B_{\ell_{q}^{n}}$ by:

\displaystyle\begin{split}\mathscr{D}&(n,q,\delta)\\ &\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Big\{\big(\varepsilon_{1}a_{\pi(1)% },\varepsilon_{2}a_{\pi(2)},\ldots,\varepsilon_{n}a_{\pi(n)}\big):\ (\pi,(% \varepsilon_{1},\ldots,\varepsilon_{n}),a)\in S_{n}\times\{-1,1\}^{n}\times% \mathcal{G}(n,q,\delta)\Big\}.\end{split}

(43)

Then, $\mathscr{D}(n,q,\delta)$ is $(\delta/2)$ -dense in $B_{\ell_{q}^{n}}$ . Indeed, for each $x=(x_{1},\ldots,x_{n})\in B_{\ell_{q}^{n}}$ fix a permutation $\pi=\pi^{x}\in S_{n}$ such that $|x_{\pi(1)}|\geqslant|x_{\pi(2)}|\geqslant\ldots\geqslant|x_{\pi(n)}|$ . Denoting $\varepsilon_{i}=\varepsilon_{i}^{x}=\mathrm{sign}(x_{i})\in\{-1,1\}$ for each $i\in[n]$ , the vector $y=(\varepsilon_{\pi(1)}x_{\pi(1)},\ldots,\varepsilon_{\pi(n)}x_{\pi(n)})=(|x_{% \pi(1)}|,\ldots,|x_{\pi(n)}|)$ belongs $K_{q}^{n}$ , by (39). Now, use (39) to get a point $a\in\mathcal{G}(n,q,\delta)$ with $\|y-a\|_{\ell_{q}^{n}}\leqslant\delta/2$ , so that the point $b=(\varepsilon_{1}a_{\pi^{-1}(1)},\ldots,\varepsilon_{n}a_{\pi^{-1}(n)})$ belongs to $\mathscr{D}(n,q,\delta)$ by (43), and satisfies $\|x-b\|_{\ell_{q}^{n}}=\|y-a\|_{\ell_{q}^{n}}\leqslant\delta/2$ .

Observe that the convex hull $\mathrm{conv}(\mathscr{D}(n,q,\delta))$ of $\mathscr{D}(n,q,\delta)$ satisfies the following inclusion:

\mathrm{conv}\left(\mathscr{D}(n,q,\delta)\right)\supseteq\Big(1-\frac{\delta}% {2}\Big)B_{\ell_{q}^{n}}.

(44)

In fact, more generally, for any normed space $\mathbf{X}=(\mathbb{R}^{n},\|\cdot\|_{\mathbf{X}})$ , if $\mathscr{C}\subseteq B_{\mathbf{X}}$ is $(\delta/2)$ -dense in $B_{\mathbf{X}}$ with respect to the metric induced by $\|\cdot\|_{\mathbf{X}}$ , then $\mathrm{conv}(\mathscr{C})\supseteq(1-\delta/2)B_{\mathbf{X}}$ . Indeed, suppose contrapositively that there exists $x\in(1-\delta/2)B_{\mathbf{X}}\smallsetminus\mathrm{conv}(\mathscr{C})$ . Then, by the separation theorem we can fix $y^{*}\in\mathbb{R}^{n}$ with $\|y^{*}\|_{\mathbf{X}^{*}}=1$ such that $\langle y^{*},x\rangle>\langle y^{*},c\rangle$ for every $c\in\mathscr{C}$ . By the Hahn–Banach theorem, we can fix $y\in B_{\mathbf{X}}$ such that $\langle y^{*},y\rangle=1$ . Finally, because $\mathscr{C}$ is $(\delta/2)$ -dense in $B_{\mathbf{X}}$ , we can fix $c_{y}\in\mathscr{C}$ such that $\|y-c_{y}\|_{\mathbf{X}}\leqslant\delta/2$ . We now arrive at the desired contradiction as follows:

1-\frac{\delta}{2}\geqslant\|x\|_{\mathbf{X}}\geqslant\langle y^{*},x\rangle>% \langle y^{*},c_{y}\rangle=\langle y^{*}y\rangle-\langle y^{*},c_{y}-y\rangle% \geqslant 1-\|c_{y}-y\|_{\mathbf{X}}\geqslant 1-\frac{\delta}{2},

(45)

where the second and the penultimate steps of (45) use the fact that $y^{*}$ has norm $1$ as a linear functional in $\mathbf{X}^{*}$ , the first step of (45) uses the assumption $x\in(1-\delta/2)B_{\mathbf{X}}$ , the third step of (45) uses the assumed property of the separating functional $y^{*}$ for $c=c_{y}\in\mathscr{C}$ , and the final step of (45) uses the choice of $c_{y}$ .

We can now justify the first inequality of the desired conclusion (10) of Theorem 4 as follows:

$\displaystyle\mathrm{Alg}_{p}(n,D,\delta,\mathbf{E})$	$\displaystyle\stackrel{{\scriptstyle\eqref{eq:alg for E star}\wedge\eqref{eq:% def our alg}}}{{\geqslant}}2\max_{a\in\mathcal{G}(n,q,\delta)}\Big(1-\frac{% \delta}{2}\Big)\\|a\\|_{\mathbf{E}^{*}}$
	$\displaystyle\ \ \ \ \stackrel{{\scriptstyle\eqref{eq:def DD}}}{{=}}2\max_{a% \in\mathscr{D}(n,q,\delta)}\Big(1-\frac{\delta}{2}\Big)\\|a\\|_{\mathbf{E}^{*}}$	(46)
	$\displaystyle\ \ \ \ \ =2\Big(1-\frac{\delta}{2}\Big)\max_{x\in\mathrm{conv}% \big(\mathscr{D}(n,q,\delta)\big)}\\|x\\|_{\mathbf{E}^{*}}$	(47)
	$\displaystyle\ \ \ \ \stackrel{{\scriptstyle\eqref{eq:conve inclusion}}}{{% \geqslant}}2\Big(1-\frac{\delta}{2}\Big)\max_{x\in\left(1-\frac{\delta}{2}% \right)B_{\ell_{q}^{n}}}\\|x\\|_{\mathbf{E}^{*}}$
	$\displaystyle\ \ \ \ \ =2\Big(1-\frac{\delta}{2}\Big)^{2}\max_{x\in B_{\ell_{q% }^{n}}}\\|x\\|_{\mathbf{E}^{*}}$
	$\displaystyle\ \ \ \ \stackrel{{\scriptstyle\eqref{eq:duality}}}{{=}}\Big(1-% \frac{\delta}{2}\Big)^{2}\operatorname{diam}_{\ell_{p}^{n}}(B_{\mathbf{E}})$
	$\displaystyle\ \ \ \ \ >(1-\delta)\operatorname{diam}_{\ell_{p}^{n}}(B_{% \mathbf{E}}),$

where (46) is the step in which the assumption that $\|\cdot\|_{\mathbf{E}}$ is a symmetric norm is used, as this implies (by definition) that its dual $\|\cdot\|_{\mathbf{E}^{*}}$ is also a symmetric norm, and (47) holds since $\|\cdot\|_{\mathbf{E}^{*}}$ is a convex function. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 10.

In the Introduction we stated the contrast between Theorem 4 and the known nonexistence of any oracle polynomial time algorithm that computes a $O(1)$ -factor approximation to the $\ell_{p}^{n}$ -diameter of an arbitrary (so, not necessarily symmetric, as in Theorem 4) convex body in $\mathbb{R}^{n}$ that is given by a weak membership oracle, where $1\leqslant p<\infty$ is fixed. This contrast is even more severe because the known impossibility results rule out approximation factors that tend to $\infty$ with $n$ , as we will next recall.

For $n\in\mathbb{N}$ , $h\geqslant 3$ and $1\leqslant p<\infty$ , let $D_{p}^{h}(n)$ be the smallest $\alpha\geqslant 1$ for which there is a deterministic algorithm that takes as input a convex body $K\subseteq\mathbb{R}^{n}$ given by a weak membership oracle, and outputs in oracle time at most $n^{h}$ a number $\Delta_{p}(K)$ satisfying $\operatorname{diam}_{\ell_{p}^{n}}(K)\leqslant\Delta_{p}(K)\leqslant\alpha% \operatorname{diam}_{\ell_{p}^{n}}(K)$ . Similarly, let $R_{p}^{h}(n)$ denote the smallest $\alpha\geqslant 1$ for which there is a randomised algorithm that outputs in oracle time at most $n^{h}$ a number $\Delta_{p}(K)$ satisfying $\operatorname{diam}_{\ell_{p}^{n}}(K)\leqslant\Delta_{p}(K)\leqslant\alpha% \operatorname{diam}_{\ell_{p}^{n}}(K)$ with probability at least, say, $1/3$ .

Using the above notations, for $2\leqslant p<\infty$ we have $D_{p}^{h}(n)\asymp_{h}R_{p}^{h}(n)\asymp_{h}(n/\log n)^{1/p}$ ; when $p=2$ these bounds on $D_{2}^{h}(n)$ are due to [9], and these bounds for both $D_{p}^{h}(n)$ and $R_{p}^{h}(n)$ , and arbitrary $2<p<\infty$ , are due to [17, 18]. If $1\leqslant p<2$ , then $R_{p}^{h}(n)\asymp_{h}\sqrt{n/\log n}$ by [38, 39], improving by unbounded polylog factor over the corresponding bounds of [17, 18]. For deterministic algorithms, when $1\leqslant p<2$ we have $D_{p}^{h}(n)\lesssim_{h}\sqrt{n}/(\log n)^{1-1/p}$ by [17, 18], and the best-known lower bound is $D_{p}^{h}(n)\gtrsim_{h}\sqrt{n/\log n}$ , which follows from the trivial lower bound $D_{p}^{h}(n)\geqslant R_{p}^{h}(n)$ and the aforementioned asymptotic evaluation of $R_{p}^{h}(n)$ . Thus, for fixed $1\leqslant p<2$ there remains a gap of $(\log n)^{1/p-1/2}$ , which tends to $\infty$ with $n$ , between the best-known upper and lower bounds on the deterministic approximation ratio $D_{p}^{h}(n)$ . While it seems reasonable to expect that this gap (noted in [17, 18, 16]) could be closed using available methods, to the best of our knowledge this has not yet been carried out, even though it would be worthwhile to do so.

References

[1] Noga Alon, Richard M. Karp, David Peleg, and Douglas B. West. A graph-theoretic game and its application to the $k$ -server problem (extended abstract). In On-Line Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, February 11-13, 1991, pages 1–10, 1991. doi:10.1090/DIMACS/007/01.
[2] François Alter and Vicent Caselles. Uniqueness of the Cheeger set of a convex body. Nonlinear Anal., 70(1):32–44, 2009. doi:10.1016/j.na.2007.11.032.
[3] Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices, volume 118 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2010.
[4] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 459–468, 2006. doi:10.1109/FOCS.2006.49.
[5] George E. Andrews, Richard Askey, and Ranjan Roy. Special functions, volume 71 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1999. doi:10.1017/CBO9781107325937.
[6] K. Aomoto. Jacobi polynomials associated with Selberg integrals. SIAM J. Math. Anal., 18(2):545–549, 1987. doi:10.1137/0518042.
[7] Baruch Awerbuch and David Peleg. Sparse partitions (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, pages 503–513, 1990. doi:10.1109/FSCS.1990.89571.
[8] Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, and Roy Schwartz. Min-max graph partitioning and small set expansion. SIAM J. Comput., 43(2):872–904, 2014. doi:10.1137/120873996.
[9] Imre Bárány and Zoltán Füredi. Computing the volume is difficult. Discrete Comput. Geom., 2(4):319–326, 1987. doi:10.1007/BF02187886.
[10] Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science, pages 184–193. IEEE, 1996. doi:10.1109/SFCS.1996.548477.
[11] Yair Bartal. On approximating arbitrary metrices by tree metrics. In STOC ’98 (Dallas, TX), pages 161–168. ACM, New York, 1999.
[12] Rajendra Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1997. doi:10.1007/978-1-4612-0653-8.
[13] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004.
[14] Herm Jan Brascamp and Elliott H. Lieb. On extensions of the Brunn-Minkowski and Prékopa-Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation. J. Functional Analysis, 22(4):366–389, 1976. doi:10.1016/0022-1236(76)90004-5.
[15] Mark Braverman and Assaf Naor. Quantitative Wasserstein rounding. Preprint, 2025.
[16] Andreas Brieden. Geometric optimization problems likely not contained in $\mathbb{APX}$ . Discrete Comput. Geom., 28(2):201–209, 2002. doi:10.1007/s00454-002-2756-x.
[17] Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, László Lovász, and Miklós Simonovits. Approximation of diameters: Randomization doesn’t help. In 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, Palo Alto, California, USA, November 8-11, 1998, pages 244–251. IEEE Computer Society, 1998. doi:10.1109/SFCS.1998.743451.
[18] Andreas Brieden, Peter Gritzmann, Ravindran Kannan, Victor Klee, László Lovász, and Miklós Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika, 48(1-2):63–105, 2001. doi:10.1112/S0025579300014364.
[19] Alexander Brudnyi and Yuri Brudnyi. Methods of geometric analysis in extension and trace problems. Volume 2, volume 103 of Monographs in Mathematics. Birkhäuser/Springer Basel AG, Basel, 2012.
[20] M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. Approximating a finite metric by a small number of tree metrics. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 379–388, 1998. doi:10.1109/SFCS.1998.743488.
[21] Isaac Chavel. Eigenvalues in Riemannian geometry, volume 115 of Pure and Applied Mathematics. Academic Press, Inc., Orlando, FL, 1984. Including a chapter by Burton Randol, With an appendix by Jozef Dodziuk.
[22] John P. Cunningham and Zoubin Ghahramani. Linear dimensionality reduction: Survey, insights, and generalizations. Journal of Machine Learning Research, 16(89):2859–2900, 2015. doi:10.5555/2789272.2912091.
[23] G. Faber. Beweis, daß unter allen homogenen Membranen von gleicher Fläche und gleicher Spannung die kreisförmige den tiefsten Grundton gibt. Münch. Ber. 1923, 169-172 (1923)., 1923.
[24] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. doi:10.1016/j.jcss.2004.04.011.
[25] Ky Fan. Maximum properties and inequalities for the eigenvalues of completely continuous operators. Proc. Nat. Acad. Sci. U.S.A., 37:760–766, 1951. doi:10.1073/pnas.37.11.760.
[26] P. J. Forrester. Log-gases and random matrices, volume 34 of London Mathematical Society Monographs Series. Princeton University Press, Princeton, NJ, 2010. doi:10.1515/9781400835416.
[27] Peter Forrester and Ole Warnaar. The importance of the Selberg integral. Bulletin of the American Mathematical Society, 45:489–534, October 2008. doi:10.1090/S0273-0979-08-01221-4.
[28] Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, MD, 4 edition, 2013.
[29] W. T. Gowers. Symmetric block bases in finite-dimensional normed spaces. Israel J. Math., 68(2):193–219, 1989. doi:10.1007/BF02772661.
[30] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993. doi:10.1007/978-3-642-78240-4.
[31] Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 534–543, 2003. doi:10.1109/SFCS.2003.1238226.
[32] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, 2 edition, 2012.
[33] Fritz John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, pages 187–204. Interscience Publishers, Inc., New York, N. Y., 1948.
[34] D. B. Judin and A. S. Nemirovskiĭ. Informational complexity and effective methods for the solution of convex extremal problems. Èkonom. i Mat. Metody, 12(2):357–369, 1976.
[35] Kevin W. J. Kadell. The Selberg-Jack symmetric functions. Adv. Math., 130(1):33–102, 1997. doi:10.1006/aima.1997.1642.
[36] R. Kannan, L. Lovász, and M. Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete Comput. Geom., 13(3-4):541–559, 1995. doi:10.1007/BF02574061.
[37] David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. J. ACM, 45(2):246–265, 1998. doi:10.1145/274787.274791.
[38] Subhash Khot and Assaf Naor. Linear equations modulo 2 and the ${L}_{1}$ diameter of convex bodies [extended abstract]. In 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, USA, October 20-23, 2007, Proceedings, pages 318–328. IEEE Computer Society, 2007. doi:10.1109/FOCS.2007.20.
[39] Subhash Khot and Assaf Naor. Linear equations modulo 2 and the $L_{1}$ diameter of convex bodies. SIAM J. Comput., 38(4):1448–1463, 2008. doi:10.1137/070691140.
[40] Philip N. Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 682–690, 1993. doi:10.1145/167088.167261.
[41] Goran Konjevod, R. Ravi, and F. Sibel Salman. On approximating planar metrics by tree metrics. Inform. Process. Lett., 80(4):213–219, 2001. doi:10.1016/S0020-0190(01)00161-2.
[42] E. Krahn. Über Minimaleigenschaften der Kugel in drei und mehr Dimensionen. Acta Univ. Dorpat A 9, 1-44 (1926)., 1926.
[43] Robert Krauthgamer and Nir Petruschka. Lipschitz decompositions of finite $\ell_{p}$ metrics. In Oswin Aichholzer and Haitao Wang, editors, 41st International Symposium on Computational Geometry, SoCG 2025, June 23-27, 2025, Kanazawa, Japan, volume 332 of LIPIcs, pages 66:1–66:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SOCG.2025.66.
[44] Robert Krauthgamer, Nir Petruschka, and Shay Sapir. The Power of Recursive Embeddings for $\ell_{\!\!p}$ Metrics. To appear in 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025). Preprint available at https://arxiv.org/pdf/2503.18508, 2025.
[45] Robert Krauthgamer and Tim Roughgarden. Metric clustering via consistent labeling. Theory Comput., 7:49–74, 2011. doi:10.4086/toc.2011.v007a005.
[46] J. R. Lee and A. Naor. Metric decomposition, smooth measures, and clustering. Unpublished manuscript, available at https://web.math.princeton.edu/˜naor/homepage%20files/cluster.pdf, 2003.
[47] James R. Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005. doi:10.1007/s00222-004-0400-5.
[48] Yin Tat Lee and Santosh S. Vempala. The Kannan-Lovász-Simonovits conjecture. In Current developments in mathematics 2017, pages 1–36. Int. Press, Somerville, MA, 2019.
[49] Frank Thomson Leighton and Satish Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988, pages 422–431, 1988. doi:10.1109/SFCS.1988.21958.
[50] Adrian S. Lewis. The convex analysis of unitarily invariant matrix functions. Journal of Convex Analysis, 2(1-2):173–183, 1995.
[51] Adrian S. Lewis and Hristo S. Sendov. Nonsmooth analysis of singular values. part i: Theory. Set-Valued Analysis, 13:213–241, 2005. URL: https://api.semanticscholar.org/CorpusID:36823342.
[52] Emanuel Milman. On the role of convexity in isoperimetry, spectral gap and concentration. Invent. Math., 177(1):1–43, 2009. doi:10.1007/s00222-009-0175-9.
[53] L. Mirsky. Symmetric gauge functions and unitarily invariant norms. Quart. J. Math. Oxford Ser. (2), 11:50–59, 1960. doi:10.1093/qmath/11.1.50.
[54] Assaf Naor. Probabilistic clustering of high dimensional norms. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 690–709. SIAM, Philadelphia, PA, 2017. doi:10.1137/1.9781611974782.44.
[55] Assaf Naor. Extension, separation and isomorphic reverse isoperimetry, volume 11 of Memoirs of the European Mathematical Society. European Mathematical Society (EMS), Berlin, 2024. doi:10.4171/mems/11.
[56] Assaf Naor and Kevin Ren. Euclidean embedding, randomized clustering, and Lipschitz extension for finite and doubling subsets of ${L}_{p}$ when $p>2$ . Preprint available at https://arxiv.org/pdf/2410.21931, 2025.
[57] Assaf Naor and Kevin Ren. Optimal randomized clustering for subsets of ${L}_{p}$ when $p>2$ . To appear in 37th ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), 2026.
[58] David Peleg and Eilon Reshef. Deterministic polylog approximation for minimum communication spanning trees (extended abstract). In Automata, languages and programming (Aalborg, 1998), volume 1443 of Lecture Notes in Comput. Sci., pages 670–681. Springer, Berlin, 1998. doi:10.1007/BFb0055092.
[59] Michal Pešta. Unitarily invariant errors-in-variables estimation. Statistical Papers, 57:1041–1057, 2016. doi:10.1007/s00362-016-0800-9.
[60] G. Pólya and G. Szegö. Isoperimetric Inequalities in Mathematical Physics. Annals of Mathematics Studies, No. 27. Princeton University Press, Princeton, N. J., 1951.
[61] John William Strutt Rayleigh, Baron. The Theory of Sound. Dover Publications, New York, 1945. 2d ed.
[62] Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010. doi:10.1137/070697835.
[63] Arvind K. Saibaba. Randomized subspace iteration: Analysis of canonical angles and unitarily invariant norms. SIAM Journal on Matrix Analysis and Applications, 40(1):23–48, 2019. doi:10.1137/18M1179432.
[64] Robert Schatten. A Theory of Cross-Spaces, volume No. 26 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, 1950.
[65] Carsten Schütt. On the volume of unit balls in Banach spaces. Compositio Math., 47(3):393–407, 1982. URL: http://www.numdam.org/item?id=CM_1982__47_3_393_0.
[66] Atle Selberg. Remarks on a multiple integral. Norsk Mat. Tidsskr., 26:71–79, 1944.
[67] Barry Simon. Trace Ideals and Their Applications, volume 120 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2 edition, 2005. doi:10.1090/surv/120.
[68] Martin Stoll. A literature survey of matrix methods for data science. GAMM-Mitteilungen, 43(3):e202000013, 2020. doi:10.1002/gamm.202000013.
[69] David Sutter, Mario Berta, and Marco Tomamichel. Multivariate trace inequalities. Communications in Mathematical Physics, 352(1):37–58, 2017. doi:10.1007/s00220-016-2778-5.
[70] Marco Tomamichel. Quantum Information Processing with Finite Resources: Mathematical Foundations, volume 5 of SpringerBriefs in Mathematical Physics. Springer, Cham, 2016. doi:10.1007/978-3-319-21891-5.
[71] J. von Neumann. Some matrix inequalities and metrization of matric space. Mitt. Forschungsinst. Math. Mech. Kujbyschew-Univ. Tomsk 1, 286-300 (1937), 1937.
[72] John Watrous. The Theory of Quantum Information. Cambridge University Press, Cambridge, 2018. doi:10.1017/9781316848142.
[73] G. A. Watson. The solution of orthogonal procrustes problems for a family of orthogonally invariant norms. Advances in Computational Mathematics, 2:393–405, 1994. doi:10.1007/BF02521606.
[74] Hermann Weyl. The Classical Groups. Their Invariants and Representations. Princeton University Press, Princeton, NJ, 1939.
[75] Kemin Zhou, John C. Doyle, and Keith Glover. Robust and Optimal Control. Prentice Hall, Upper Saddle River, NJ, 1996.

[bib.bib1] [1] Noga Alon, Richard M. Karp, David Peleg, and Douglas B. West. A graph-theoretic game and its application to the $k$ -server problem (extended abstract). In On-Line Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, February 11-13, 1991, pages 1–10, 1991. doi:10.1090/DIMACS/007/01.

[bib.bib2] [2] François Alter and Vicent Caselles. Uniqueness of the Cheeger set of a convex body. Nonlinear Anal., 70(1):32–44, 2009. doi:10.1016/j.na.2007.11.032.

[bib.bib3] [3] Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices, volume 118 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2010.

[bib.bib4] [4] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 459–468, 2006. doi:10.1109/FOCS.2006.49.

[bib.bib5] [5] George E. Andrews, Richard Askey, and Ranjan Roy. Special functions, volume 71 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1999. doi:10.1017/CBO9781107325937.

[bib.bib6] [6] K. Aomoto. Jacobi polynomials associated with Selberg integrals. SIAM J. Math. Anal., 18(2):545–549, 1987. doi:10.1137/0518042.

[bib.bib7] [7] Baruch Awerbuch and David Peleg. Sparse partitions (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, pages 503–513, 1990. doi:10.1109/FSCS.1990.89571.

[bib.bib8] [8] Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, and Roy Schwartz. Min-max graph partitioning and small set expansion. SIAM J. Comput., 43(2):872–904, 2014. doi:10.1137/120873996.

[bib.bib9] [9] Imre Bárány and Zoltán Füredi. Computing the volume is difficult. Discrete Comput. Geom., 2(4):319–326, 1987. doi:10.1007/BF02187886.

[bib.bib10] [10] Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science, pages 184–193. IEEE, 1996. doi:10.1109/SFCS.1996.548477.

[bib.bib11] [11] Yair Bartal. On approximating arbitrary metrices by tree metrics. In STOC ’98 (Dallas, TX), pages 161–168. ACM, New York, 1999.

[bib.bib12] [12] Rajendra Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1997. doi:10.1007/978-1-4612-0653-8.

[bib.bib13] [13] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004.

[bib.bib14] [14] Herm Jan Brascamp and Elliott H. Lieb. On extensions of the Brunn-Minkowski and Prékopa-Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation. J. Functional Analysis, 22(4):366–389, 1976. doi:10.1016/0022-1236(76)90004-5.

[bib.bib15] [15] Mark Braverman and Assaf Naor. Quantitative Wasserstein rounding. Preprint, 2025.

[bib.bib16] [16] Andreas Brieden. Geometric optimization problems likely not contained in $\mathbb{APX}$ . Discrete Comput. Geom., 28(2):201–209, 2002. doi:10.1007/s00454-002-2756-x.

[bib.bib17] [17] Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, László Lovász, and Miklós Simonovits. Approximation of diameters: Randomization doesn’t help. In 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, Palo Alto, California, USA, November 8-11, 1998, pages 244–251. IEEE Computer Society, 1998. doi:10.1109/SFCS.1998.743451.

[bib.bib18] [18] Andreas Brieden, Peter Gritzmann, Ravindran Kannan, Victor Klee, László Lovász, and Miklós Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika, 48(1-2):63–105, 2001. doi:10.1112/S0025579300014364.

[bib.bib19] [19] Alexander Brudnyi and Yuri Brudnyi. Methods of geometric analysis in extension and trace problems. Volume 2, volume 103 of Monographs in Mathematics. Birkhäuser/Springer Basel AG, Basel, 2012.

[bib.bib20] [20] M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. Approximating a finite metric by a small number of tree metrics. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 379–388, 1998. doi:10.1109/SFCS.1998.743488.

[bib.bib21] [21] Isaac Chavel. Eigenvalues in Riemannian geometry, volume 115 of Pure and Applied Mathematics. Academic Press, Inc., Orlando, FL, 1984. Including a chapter by Burton Randol, With an appendix by Jozef Dodziuk.

[bib.bib22] [22] John P. Cunningham and Zoubin Ghahramani. Linear dimensionality reduction: Survey, insights, and generalizations. Journal of Machine Learning Research, 16(89):2859–2900, 2015. doi:10.5555/2789272.2912091.

[bib.bib23] [23] G. Faber. Beweis, daß unter allen homogenen Membranen von gleicher Fläche und gleicher Spannung die kreisförmige den tiefsten Grundton gibt. Münch. Ber. 1923, 169-172 (1923)., 1923.

[bib.bib24] [24] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. doi:10.1016/j.jcss.2004.04.011.

[bib.bib25] [25] Ky Fan. Maximum properties and inequalities for the eigenvalues of completely continuous operators. Proc. Nat. Acad. Sci. U.S.A., 37:760–766, 1951. doi:10.1073/pnas.37.11.760.

[bib.bib26] [26] P. J. Forrester. Log-gases and random matrices, volume 34 of London Mathematical Society Monographs Series. Princeton University Press, Princeton, NJ, 2010. doi:10.1515/9781400835416.

[bib.bib27] [27] Peter Forrester and Ole Warnaar. The importance of the Selberg integral. Bulletin of the American Mathematical Society, 45:489–534, October 2008. doi:10.1090/S0273-0979-08-01221-4.

[bib.bib28] [28] Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, MD, 4 edition, 2013.

[bib.bib29] [29] W. T. Gowers. Symmetric block bases in finite-dimensional normed spaces. Israel J. Math., 68(2):193–219, 1989. doi:10.1007/BF02772661.

[bib.bib30] [30] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993. doi:10.1007/978-3-642-78240-4.

[bib.bib31] [31] Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 534–543, 2003. doi:10.1109/SFCS.2003.1238226.

[bib.bib32] [32] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, 2 edition, 2012.

[bib.bib33] [33] Fritz John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, pages 187–204. Interscience Publishers, Inc., New York, N. Y., 1948.

[bib.bib34] [34] D. B. Judin and A. S. Nemirovskiĭ. Informational complexity and effective methods for the solution of convex extremal problems. Èkonom. i Mat. Metody, 12(2):357–369, 1976.

[bib.bib35] [35] Kevin W. J. Kadell. The Selberg-Jack symmetric functions. Adv. Math., 130(1):33–102, 1997. doi:10.1006/aima.1997.1642.

[bib.bib36] [36] R. Kannan, L. Lovász, and M. Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete Comput. Geom., 13(3-4):541–559, 1995. doi:10.1007/BF02574061.

[bib.bib37] [37] David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. J. ACM, 45(2):246–265, 1998. doi:10.1145/274787.274791.

[bib.bib38] [38] Subhash Khot and Assaf Naor. Linear equations modulo 2 and the ${L}_{1}$ diameter of convex bodies [extended abstract]. In 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, USA, October 20-23, 2007, Proceedings, pages 318–328. IEEE Computer Society, 2007. doi:10.1109/FOCS.2007.20.

[bib.bib39] [39] Subhash Khot and Assaf Naor. Linear equations modulo 2 and the $L_{1}$ diameter of convex bodies. SIAM J. Comput., 38(4):1448–1463, 2008. doi:10.1137/070691140.

[bib.bib40] [40] Philip N. Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 682–690, 1993. doi:10.1145/167088.167261.

[bib.bib41] [41] Goran Konjevod, R. Ravi, and F. Sibel Salman. On approximating planar metrics by tree metrics. Inform. Process. Lett., 80(4):213–219, 2001. doi:10.1016/S0020-0190(01)00161-2.

[bib.bib42] [42] E. Krahn. Über Minimaleigenschaften der Kugel in drei und mehr Dimensionen. Acta Univ. Dorpat A 9, 1-44 (1926)., 1926.

[bib.bib43] [43] Robert Krauthgamer and Nir Petruschka. Lipschitz decompositions of finite $\ell_{p}$ metrics. In Oswin Aichholzer and Haitao Wang, editors, 41st International Symposium on Computational Geometry, SoCG 2025, June 23-27, 2025, Kanazawa, Japan, volume 332 of LIPIcs, pages 66:1–66:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SOCG.2025.66.

[bib.bib44] [44] Robert Krauthgamer, Nir Petruschka, and Shay Sapir. The Power of Recursive Embeddings for $\ell_{\!\!p}$ Metrics. To appear in 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025). Preprint available at https://arxiv.org/pdf/2503.18508, 2025.

[bib.bib45] [45] Robert Krauthgamer and Tim Roughgarden. Metric clustering via consistent labeling. Theory Comput., 7:49–74, 2011. doi:10.4086/toc.2011.v007a005.

[bib.bib46] [46] J. R. Lee and A. Naor. Metric decomposition, smooth measures, and clustering. Unpublished manuscript, available at https://web.math.princeton.edu/˜naor/homepage%20files/cluster.pdf, 2003.

[bib.bib47] [47] James R. Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005. doi:10.1007/s00222-004-0400-5.

[bib.bib48] [48] Yin Tat Lee and Santosh S. Vempala. The Kannan-Lovász-Simonovits conjecture. In Current developments in mathematics 2017, pages 1–36. Int. Press, Somerville, MA, 2019.

[bib.bib49] [49] Frank Thomson Leighton and Satish Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988, pages 422–431, 1988. doi:10.1109/SFCS.1988.21958.

[bib.bib50] [50] Adrian S. Lewis. The convex analysis of unitarily invariant matrix functions. Journal of Convex Analysis, 2(1-2):173–183, 1995.

[bib.bib51] [51] Adrian S. Lewis and Hristo S. Sendov. Nonsmooth analysis of singular values. part i: Theory. Set-Valued Analysis, 13:213–241, 2005. URL: https://api.semanticscholar.org/CorpusID:36823342.

[bib.bib52] [52] Emanuel Milman. On the role of convexity in isoperimetry, spectral gap and concentration. Invent. Math., 177(1):1–43, 2009. doi:10.1007/s00222-009-0175-9.

[bib.bib53] [53] L. Mirsky. Symmetric gauge functions and unitarily invariant norms. Quart. J. Math. Oxford Ser. (2), 11:50–59, 1960. doi:10.1093/qmath/11.1.50.

[bib.bib54] [54] Assaf Naor. Probabilistic clustering of high dimensional norms. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 690–709. SIAM, Philadelphia, PA, 2017. doi:10.1137/1.9781611974782.44.

[bib.bib55] [55] Assaf Naor. Extension, separation and isomorphic reverse isoperimetry, volume 11 of Memoirs of the European Mathematical Society. European Mathematical Society (EMS), Berlin, 2024. doi:10.4171/mems/11.

[bib.bib56] [56] Assaf Naor and Kevin Ren. Euclidean embedding, randomized clustering, and Lipschitz extension for finite and doubling subsets of ${L}_{p}$ when $p>2$ . Preprint available at https://arxiv.org/pdf/2410.21931, 2025.

[bib.bib57] [57] Assaf Naor and Kevin Ren. Optimal randomized clustering for subsets of ${L}_{p}$ when $p>2$ . To appear in 37th ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), 2026.

[bib.bib58] [58] David Peleg and Eilon Reshef. Deterministic polylog approximation for minimum communication spanning trees (extended abstract). In Automata, languages and programming (Aalborg, 1998), volume 1443 of Lecture Notes in Comput. Sci., pages 670–681. Springer, Berlin, 1998. doi:10.1007/BFb0055092.

[bib.bib59] [59] Michal Pešta. Unitarily invariant errors-in-variables estimation. Statistical Papers, 57:1041–1057, 2016. doi:10.1007/s00362-016-0800-9.

[bib.bib60] [60] G. Pólya and G. Szegö. Isoperimetric Inequalities in Mathematical Physics. Annals of Mathematics Studies, No. 27. Princeton University Press, Princeton, N. J., 1951.

[bib.bib61] [61] John William Strutt Rayleigh, Baron. The Theory of Sound. Dover Publications, New York, 1945. 2d ed.

[bib.bib62] [62] Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010. doi:10.1137/070697835.

[bib.bib63] [63] Arvind K. Saibaba. Randomized subspace iteration: Analysis of canonical angles and unitarily invariant norms. SIAM Journal on Matrix Analysis and Applications, 40(1):23–48, 2019. doi:10.1137/18M1179432.

[bib.bib64] [64] Robert Schatten. A Theory of Cross-Spaces, volume No. 26 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, 1950.

[bib.bib65] [65] Carsten Schütt. On the volume of unit balls in Banach spaces. Compositio Math., 47(3):393–407, 1982. URL: http://www.numdam.org/item?id=CM_1982__47_3_393_0.

[bib.bib66] [66] Atle Selberg. Remarks on a multiple integral. Norsk Mat. Tidsskr., 26:71–79, 1944.

[bib.bib67] [67] Barry Simon. Trace Ideals and Their Applications, volume 120 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2 edition, 2005. doi:10.1090/surv/120.

[bib.bib68] [68] Martin Stoll. A literature survey of matrix methods for data science. GAMM-Mitteilungen, 43(3):e202000013, 2020. doi:10.1002/gamm.202000013.

[bib.bib69] [69] David Sutter, Mario Berta, and Marco Tomamichel. Multivariate trace inequalities. Communications in Mathematical Physics, 352(1):37–58, 2017. doi:10.1007/s00220-016-2778-5.

[bib.bib70] [70] Marco Tomamichel. Quantum Information Processing with Finite Resources: Mathematical Foundations, volume 5 of SpringerBriefs in Mathematical Physics. Springer, Cham, 2016. doi:10.1007/978-3-319-21891-5.

[bib.bib71] [71] J. von Neumann. Some matrix inequalities and metrization of matric space. Mitt. Forschungsinst. Math. Mech. Kujbyschew-Univ. Tomsk 1, 286-300 (1937), 1937.

[bib.bib72] [72] John Watrous. The Theory of Quantum Information. Cambridge University Press, Cambridge, 2018. doi:10.1017/9781316848142.

[bib.bib73] [73] G. A. Watson. The solution of orthogonal procrustes problems for a family of orthogonally invariant norms. Advances in Computational Mathematics, 2:393–405, 1994. doi:10.1007/BF02521606.

[bib.bib74] [74] Hermann Weyl. The Classical Groups. Their Invariants and Representations. Princeton University Press, Princeton, NJ, 1939.

[bib.bib75] [75] Kemin Zhou, John C. Doyle, and Keith Glover. Robust and Optimal Control. Prentice Hall, Upper Saddle River, NJ, 1996.

Optimal Randomized Clustering of Matrices

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

Theorem 2.

Problem 3.

Theorem 4.

1.1 Reverse Faber–Krahn

Theorem 5.

Conjecture 6 (reverse Faber–Krahn).

1.2 Weak isomorphic reverse isoperimetry

Theorem 7.

Conjecture 8 (weak isomorphic reverse isoperimetry).

▶ Remark 9.

2 Proof of Theorem 5

Proof.

3 Proof of Theorem 4

Proof.

▶ Remark 10.

References

$\blacktriangleright$ Remark 9.

$\blacktriangleright$ Remark 10.