Optimal Randomized Clustering of Matrices

If X = (Mn(ℝ), ∥ · ∥X) is a unitarily invariant normed space, i.e., ∥UAV∥X = ∥A∥X for every matrix A ∈ Mn(ℝ) and every two orthogonal matrices U, V ∈ Mn(ℝ), then we evaluate up to universal constant factors the smallest σ > 0 for which there is a probability distribution over partitions of X into clusters of diameter at most 1 yet for every two matrices A, B ∈ Mn(ℝ) the probability that they fall into distinct clusters is at most σ times the X-distance between A and B. Specifically, we prove that this infimal σ, which is called the separation modulus of X and is denoted SEP(X), satisfies: SEP(X) = Θ(√n · ∥In∥X · diam(BX)), where In is the n-by-n identity matrix and diam(BX) is the diameter with respect to the standard Euclidean metric on Mn(ℝ) of the unit ball BX of X. Our proof of (1) proceeds through an asymptotic evaluation of the spectral gap of the Laplacian with Dirichlet boundary conditions on BX, which we achieve by exact computations for a Jacobi orthogonal random matrix ensemble. Assuming oracle access to norm evaluations in X, by combining (1) with a new deterministic algorithm for a O(1)-approximation of the diameter of convex bodies in ℝⁿ 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 X up to universal constant factors. Another example of a consequence of (1) is that for each m ∈ {1, . . ., n} the separation modulus of the m’th Ky Fan norm on Mn(ℝ) is bounded from above and from below by universal constant multiples of m√n if m ≥ √n, and of n if m ≤ √n. We also deduce from (1) an upper bound on the Lipschitz extension modulus of X that improves over the previously best-known bound even in the special case when X is Mn(ℝ) equipped with the ℓⁿ₂ → ℓⁿ₂ operator norm.