Inequalities and Positive-Definite Functions Arising From a Problem in Multidimensional Scaling

We solve the following variational problem: Find the maximum of E ∥ X−Y ∥ subject to E ∥ X ∥2 ≤ 1, where X and Y are i.i.d. random n-vectors, and ∥⋅∥ is the usual Euclidean norm on Rn. This problem arose from an investigation into multidimensional scaling, a data analytic method for visualizing proximity data. We show that the optimal X is unique and is (1) uniform on the surface of the unit sphere, for dimensions n ≥ 3, (2) circularly symmetric with a scaled version of the radial density ρ/(1−ρ2)1/2, 0 ≤ ρ ≤1, for n=2, and (3) uniform on an interval centered at the origin, for n=1 (Plackett's theorem). By proving spherical symmetry of the solution, a reduction to a radial problem is achieved. The solution is then found using the Wiener-Hopf technique for (real) n < 3. The results are reminiscent of classical potential theory, but they cannot be reduced to it. Along the way, we obtain results of independent interest: for any i.i.d. random n-vectors X and Y,E ∥ X−Y ∥ ≤ E ∥ X+Y ∥. Further, the kernel Kp, β(x,y) = ∥ x+y ∥βp− ∥x−y∥βp, x, y∈Rn and ∥ x ∥ p=(∑|xi|p)1/p, is positive-definite, that is, it is the covariance of a random field, Kp,β(x,y) = E [ Z(x)Z(y) ] for some real-valued random process Z(x), for 1 ≤ p ≤ 2 and 0 < β ≤ p ≤ 2 (but not for β >p or p>2 in general). Although this is an easy consequence of known results, it appears to be new in a strict sense. In the radial problem, the average distance D(r1,r2) between two spheres of radii r1 and r2 is used as a kernel. We derive properties of D(r1,r2), including nonnegative definiteness on signed measures of zero integral.