Universal optimality of the double-centred matrix under unitarily invariant norms for dissimilarity data

Technical Summary: Universal Optimality of the Double-Centred Matrix

Problem Statement
The paper addresses the problem of selecting a canonical representative from an affine family of real symmetric matrices derived from a given symmetric dissimilarity matrix $D = (D_{ij})_{i,j=1}^n$. Let $D^{(2)} = (D_{ij}^2)$ denote the matrix of squared dissimilarities. The authors consider the family of matrices $A(g)$ defined by the relation:
$$D_{ij}^2 = a_{ii} + a_{jj} - 2a_{ij}, \quad i \neq j$$
where the diagonal entries of $A(g)$ are free parameters. Specifically, for a vector $g \in \mathbb{R}^n$, the family is parametrized as:
$$A(g) = \frac{1}{2} \left( \mathbf{1}g^\top + g\mathbf{1}^\top - D^{(2)} \right)$$
Here, $\mathbf{1}$ is the all-ones vector. The diagonal entries of $A(g)$ are determined by $g$, while the off-diagonal entries are fixed by the dissimilarity data.

The central question is whether there exists a specific choice of the diagonal vector $g$ that minimizes the "size" of $A(g)$ across a broad class of matrix norms, specifically unitarily invariant norms (which include the Frobenius norm, spectral norm, nuclear norm, Schatten $p$-norms, and Ky Fan $k$-norms). Crucially, the paper does not assume that the dissimilarity matrix $D$ arises from a Euclidean configuration (i.e., $D$ need not be a Euclidean distance matrix, and $A(g)$ need not be positive semidefinite).

Methodology
The authors employ a purely matrix-theoretic approach, avoiding assumptions of Euclidean realizability. The methodology relies on three main components:

1. Affine Structure Analysis: The authors analyze the structure of $A(g)$ under the action of the centering matrix $J = I - \frac{1}{n}\mathbf{1}\mathbf{1}^\top$. They establish a key structural identity (Lemma 2.2):
   $$J A(g) J = -\frac{1}{2} J D^{(2)} J$$
   This identity demonstrates that the "centred compression" of any matrix in the affine family is independent of the parameter $g$.

2. Frobenius Norm Minimization: The authors first solve the minimization problem for the Frobenius norm ($\|\cdot\|_F$). They prove that the objective function $f(g) = \|A(g)\|_F^2$ is a strictly convex quadratic with a positive-definite Hessian. By deriving the first-order optimality condition, they identify a unique minimizer $g_F$ such that $A(g_F)\mathbf{1} = \mathbf{0}$. This leads to the explicit closed-form solution:
   $$g_F = \frac{1}{n} D^{(2)}\mathbf{1} - \frac{1}{2n^2}(\mathbf{1}^\top D^{(2)}\mathbf{1})\mathbf{1}$$
   Consequently, the unique Frobenius minimizer is the double-centred matrix:
   $$A(g_F) = -\frac{1}{2} J D^{(2)} J$$

3. Extension to Unitarily Invariant Norms: To extend this result to all unitarily invariant norms, the authors utilize the contractivity of orthogonal pinching (Lemma 2.4). They show that for any unitarily invariant norm $\|\|\cdot\|\|$, the inequality $\|\| J A(g) J \|\| \le \|\| A(g) \|\|$ holds. Since $J A(g) J = A(g_F)$ for all $g$, it follows that $A(g_F)$ minimizes the norm for the entire family.

Key Results

• Universal Optimality (Theorem 2.5): The double-centred matrix $A(g_F) = -\frac{1}{2} J D^{(2)} J$ is a minimizer of $\|\| A(g) \|\|$ for every unitarily invariant norm. This includes the spectral norm, nuclear norm, Frobenius norm, and all Schatten $p$-norms and Ky Fan $k$-norms.
• Uniqueness Structure:
  • For strictly convex unitarily invariant norms (e.g., Frobenius norm, Schatten $p$-norms with $1 < p < \infty$), $g_F$ is the unique minimizer.
  • For non-strictly convex norms (e.g., spectral norm, nuclear norm), the minimizer is not necessarily unique. The authors characterize the non-uniqueness along the one-dimensional slice $g(t) = g_F + \frac{t}{n}\mathbf{1}$, showing that $\|A(g(t))\|_2 = \max\{\rho^*, |t|\}$, where $\rho^* = \|A(g_F)\|_2$. Thus, any $t$ with $|t| \le \rho^*$ yields a spectral-norm minimizer.
• Rank Condition (Proposition 2.8): The authors characterize the case where the Frobenius and spectral minima coincide (i.e., $\|A(g_F)\|_F = \|A(g_F)\|_2$). This occurs if and only if $\text{rank}(J D^{(2)} J) \le 1$. In the Euclidean case, this is equivalent to the $n$ points being collinear. In this degenerate case, all Schatten norms of $A(g_F)$ coincide.

Significance and Claims
The paper claims to provide a purely variational characterisation of the double-centred matrix, which is the central object in Classical Multidimensional Scaling (CMDS) and Principal Coordinate Analysis (PCoA).

• Independence from Euclidean Assumptions: Unlike classical CMDS theory, which often requires the input dissimilarities to be Euclidean (implying the resulting matrix is positive semidefinite), this result holds for arbitrary symmetric dissimilarity data. The double-centred matrix emerges as the optimal representative regardless of whether the data is Euclidean.
• Norm Independence: The result demonstrates that the choice of the double-centred matrix is not an artifact of minimizing the Frobenius norm specifically. Instead, it is a "universal" minimizer for the entire class of unitarily invariant norms.
• Relation to Matrix Nearness: The work is framed as an affine variant of the matrix nearness problem. It contrasts with existing literature (e.g., Higham's work on nearest positive semidefinite matrices) by showing that, for this specific affine family, the Frobenius and spectral minimization problems are solved by the same matrix (though uniqueness differs), and a closed-form solution exists for both.

The authors do not propose new applications but rather provide a theoretical justification for the widespread use of the double-centred matrix in fields like numerical ecology and microbiome analysis, where dissimilarity measures (e.g., Bray–Curtis) often fail to satisfy Euclidean metric properties.