The separation modulus of unitarily invariant matrix norms
Mustafa Alper Gunes, Assaf Naor · 2025
Read The separation modulus of unitarily invariant matrix norms by Mustafa Alper Gunes, Assaf Naor (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-03853.txt.
Introduction
Mustafa Alper Gunes and Assaf Naor pin down the separation modulus for spaces of matrices under unitarily invariant norms. The separation modulus measures how well separated points can be packed. That quantity ties to isoperimetric questions. Their route runs through spectral geometry on the unit ball of the norm.
Exact work with a Jacobi orthogonal random matrix ensemble gives the spectral gap of the Laplacian on that ball. It grows like the cube of the dimension times the norm of the identity, squared. That estimate confirms a weak form of the isomorphic reverse isoperimetry conjecture for these spaces. The separation formula then follows as a corollary. With a new deterministic diameter algorithm, it yields an oracle polynomial-time procedure to compute the modulus approximately.
Catalog record
| CREATOR | Mustafa Alper Gunes, Assaf Naor |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-03853
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The separation modulus of unitarily invariant matrix norms Thanks: A. N. was supported by NSF grant DMS-2453936, BSF grant 2018223, and a Simons Investigator award. Mustafa Alper Gunes, Assaf Naor Abstract . If 𝐗 = ( 𝖬 n ( ℝ ) , ∥ ⋅ ∥ 𝐗 ) \mathbf{X}=(\mathsf{M}_{n}(\mathbb{R}),\|\cdot\|_{\mathbf{X}}) is a unitarily invariant normed space, namely, ‖ 𝖴𝖠𝖵 ‖ 𝐗 = ‖ 𝖠 ‖ 𝐗 \|\mathsf{U}\mathsf{A}\mathsf{V}\|_{\mathbf{X}}=\|\mathsf{A}\|_{\mathbf{X}} for every matrix 𝖠 ∈ 𝖬 n ( ℝ ) \mathsf{A}\in\mathsf{M}_{n}(\mathbb{R}) and every two orthogonal matrices 𝖴 , 𝖵 ∈ 𝖮 n \mathsf{U},\mathsf{V}\in\mathsf{O}_{\!n} , then we prove that the spectral gap λ ( 𝐗 ) \lambda(\mathbf{X}) of the Laplacian with Dirichlet boundary conditions on the unit ball B 𝐗 B_{\mathbf{X}} of 𝐗 \mathbf{X} satisfies the asymptotic equivalence λ ( 𝐗 ) ≍ n 3 ‖ 𝖨 n ‖ 𝐗 2 , \lambda(\mathbf{X})\asymp n^{3}\|\mathsf{I}_{n}\|_{\mathbf{X}}^{2}, (1) where 𝖨 n \mathsf{I}_{\!n} is the n n -by- n n identity matrix. This leads to a confirmation of the weak isomorphic reverse isoperimetry conjecture for 𝐗 \mathbf{X} , namely, we demonstrate that there exists a convex body L = L 𝐗 ⊆ B 𝐗 L=L_{\mathbf{X}}\subseteq B_{\mathbf{X}} such that ( vol n 2 ( L ) ) 1 n 2 ≍ ( vol n 2 ( B 𝐗 ) ) 1 n 2 , \big(\mathrm{vol}_{n^{2}}(L)\big)^{\frac{1}{n^{2}}}\asymp\big(\mathrm{vol}_{n^{2}}(B_{\mathbf{X}})\big)^{\frac{1}{n^{2}}}, yet its isoperimetric quotient iq ( L ) = vol n 2 − 1 ( ∂ L ) / vol n 2 ( L ) ( n − 1 ) / n \mathrm{iq}(L)=\mathrm{vol}_{n^{2}-1}(\partial L)/\mathrm{vol}_{n^{2}}(L)^{(n-1)/n} is at most a universal constant multiple of n ≍ iq ( B ℓ 2 n 2 ) n\asymp\mathrm{iq}(B_{\!\!\ell_{\!\!2}^{n^{2}}}) . We prove ( 1 ) through exact computations for a Jacobi orthogonal random matrix ensemble. As a corollary (and motivation) of the above results, we deduce that the separation modulus of 𝐗 \mathbf{X} satisfies 𝖲𝖤𝖯 ( 𝐗 ) ≍ n ‖ 𝖨 n ‖ 𝐗 diam ( B 𝐗 ) , \mathsf{SEP}(\mathbf{X})\asymp\sqrt{n}\|\mathsf{I}_{\!n}\|_{\mathbf{X}}\diam(B_{\mathbf{X}}), (2) where diam ( B 𝐗 ) \diam(B_{\mathbf{X}}) is the diameter of B 𝐗 B_{\mathbf{X}} with respect to the standard Euclidean metric on 𝖬 n ( ℝ ) \mathsf{M}_{n}(\mathbb{R}) . Assuming oracle access to norm evaluations in 𝐗 \mathbf{X} , by combining ( 2 ) with a new deterministic algorithm for efficiently computing a O ( 1 ) O(1) -approximation of the diameter of convex bodies in ℝ n \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 is known to be impossible in the absence of such symmetries), we obtain an oracle polynomial time algorithm whose output is guaranteed to be the separation modulus of 𝐗 \mathbf{X} up to positive universal constant factors. Another example of a consequence of ( 2 ) is that for each m ∈ { 1 , … , n } m\in\{1,\ldots,n\} the separation modulus of the m m ’th Ky Fan norm on 𝖬 n ( ℝ ) \mathsf{M}_{n}(\mathbb{R}) is bounded from above and from below by positive universal constant multiples of m n m\sqrt{n} if m ⩾ n m\geqslant\sqrt{n} , and of n n if m ⩽ n m\leqslant\sqrt{n} . We also deduce from ( 2 ) 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 𝖬 n ( ℝ ) \mathsf{M}_{n}(\mathbb{R}) equipped with the ℓ 2 n → ℓ 2 n \ell_{\!\!2}^{n}\to\ell_{\!\!2}^{n} operator norm. 1. Introduction Given n\in\mathbb{N} , 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} . 1 1 1 One defines analogously unitarily invariant norms on the spaces \mathsf{M}_{n}(\mathbb{C}) and \mathsf{M}_{n}(\mathbb{H}) of n -by- n matrices whose entries belong to the complex numbers \mathbb{C} or, respectively, the quaternions \mathbb{H} (thus, the dimension over \mathbb{R} of \mathsf{M}_{n}(\mathbb{C}) equals 2n^{2} and the dimension over \mathbb{R} of \mathsf{M}_{n}(\mathbb{H}) equals 4n^{2} ), but all of the results that are derived herein follow formally for complex and quaternionic entries from their counterparts for real entries; these simple deductions are carried out in Section 4 below. Alternatively, it is possible to perform the proofs mutatis mutandis directly for complex and quaternionic matrices. For this reason, the considerations herein (excluding Section 4 ) will treat only the case of matrices whose entries are in \mathbb{R} . Norms with this property [ 57 , 54 ] 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 basses 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, and data analysis. 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(\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., if \mathsf{A}=(a_{ij})\in\mathsf{M}_{n}(\mathbb{R}) , then \|\mathsf{A}\|_{\mathsf{S}_{2}^{n}}=(\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}^{2})^{1/2} . Additional examples are furnished [ 23 ] by the Ky Fan norms \|\cdot\|_{\mathsf{K}_{1}},\ldots,\|\cdot\|_{\mathsf{K}_{n}} that are defined as follows: \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}). (3) More generally, let \mathbf{E}=(\mathbb{R}^{n},\|\cdot\|_{\mathbf{E}}) be a symmetric normed space, i.e., the following requirement holds: \forall x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n},\ \forall\pi\in S_{n},\ \forall(\varepsilon_{1},\ldots,\varepsilon_{n}\in\{-1,1\},\qquad\|(\varepsilon_{1}x_{\pi(1)},\ldots,\varepsilon_{n}x_{\pi(n)})\|_{\mathbf{E}}=\|x\|_{\mathbf{E}}. (4) The (real) 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 setting: \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}}. (5) A norm \|\cdot\| on \mathsf{M}_{n}(\mathbb{R}) is unitarily invariant if and only if there exists a symmetric norm \|\cdot\|_{\mathbf{E}} on \mathbb{R}^{n} such that \|\cdot\|=\|\cdot\|_{\mathsf{S}_{\mathbf{E}}^{n}} ; see e.g. [ 46 ] or [ 12 , Chapter IV] for a justification of this classical fact. The purpose of the present article is to obtain optimal randomized clustering of arbitrary unitarily invariant norms, which is a useful tool for a range of algorithmic tasks (see below), as well as for applications in mathematics (notably to metric embeddings [ 11 , 22 , 50 ] and Lipschitz extension [ 41 , 48 ] ). Let (\mathcal{M},d_{\mathcal{M}}) be a metric space. For a partition \mathscr{P} of \mathcal{M} and a point x\in\mathcal{M} , the cluster of \mathscr{P} to which x belongs is denoted \mathscr{P}(x) . One says that \mathscr{P} is \Delta -bounded for some \Delta>0 if \diam_{\mathcal{M}}(\mathscr{P}(x))\leqslant\Delta for every x\in\mathcal{M} , where \diam_{\mathcal{M}}(\mathscr{C})=\sup\{d_{\mathcal{M}}(y,z):\ y,z\in\mathcal{M}\} denotes the d_{\mathcal{M}} -diameter of \varnothing\neq\mathscr{C}\subseteq\mathcal{M} . Given \sigma\geqslant 0