INEQUALITIES AND POSITIVE-DEFINITE FUNCTIONS ARISING FROM A PROBLEM IN MULTIDIMENSIONAL-SCALING

We solve the following variational problem: Find the maximum of E E\\X -Y\\ subject to E\\X\\2 less-than-or-equal-to 1, where X and Y are i.i .d. random n-vectors, and \\ . \\ is the usual Euclidean norm on R(n). This problem arose from an investigation into multidimensional scalin g, 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 greater-than-or-equal-to 3, (2) circularly s ymmetric with a scaled version of the radial density rho/(1 - rho2)1/2 , 0 less-than-or-equal-to rho less-than-or-equal-to 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 reductio n to a radial problem is achieved. The solution is then found using th e 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. ra ndom n-vectors X and Y, E \\ X - Y \\ less-than-or-equal-to E \\ X + Y \\. Further, the kernel K(p,beta)(x,y) = \\ x + y \\ p(beta) - \\ x - y \\ p(beta),x,y is-an-element-of R(n) and \\ x \\ p = (SIGMA\x(i)\p) 1/p, is positive-definite, that is, it is the covariance of a random f ield, K(p,beta)(x,y) = E[Z(x)Z(y)] for some real-valued random process Z(x), for 1 less-than-or-equal-to p less-than-or-equal-to 2 and 0 < b eta less-than-or-equal-to p less-than-or-qual-to 2 (but not for beta > 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 proble m, 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 n onnegative definiteness on signed measures of zero integral.