Inequalities and Positive-Definite Functions Arising from a Problem in Multidimensional Scaling
Buja, Andreas ; Logan, B. F. ; Reeds, J. A. ; Shepp, L. A.
Ann. Statist., Tome 22 (1994) no. 1, p. 406-438 / Harvested from Project Euclid
We solve the following variational problem: Find the maximum of $E\|X - Y\|$ subject to $E\|X\|^2 \leq 1$, where $X$ and $Y$ are i.i.d. random $n$-vectors, and $\|\cdot\|$ is the usual Euclidean norm on $\mathbb{R}^n$. 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 \geq 3$, (2) circularly symmetric with a scaled version of the radial density $\rho/(1 - \rho^2)^{1/2}, 0 \leq \rho \leq 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\| \leq E\|X + Y\|$. Further, the kernel $K_{p,\beta}(x, y) = \|x + y\|^\beta_p - \|x - y\|^\beta_p, x, y \in \mathbb{R}^n$ and $\|x\|p = (\sum|x_i|^p)^{1/p}$, is positive-definite, that is, it is the covariance of a random field, $K_{p,\beta}(x, y) = E\lbrack Z(x)Z(y)\rbrack$ for some real-valued random process $Z(x)$, for $1 \leq p \leq 2$ and $0 < \beta \leq p \leq 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 problem, the average distance $D(r_1, r_2)$ between two spheres of radii $r_1$ and $r_2$ is used as a kernel. We derive properties of $D(r_1, r_2)$, including nonnegative definiteness on signed measures of zero integral.
Publié le : 1994-03-14
Classification:  Multidimensional scaling,  maximal expected distance,  potential theory,  inequalities,  positive-definite functions,  Wiener-Hopf technique,  26D10,  62H99,  42A82,  45E10
@article{1176325376,
     author = {Buja, Andreas and Logan, B. F. and Reeds, J. A. and Shepp, L. A.},
     title = {Inequalities and Positive-Definite Functions Arising from a Problem in Multidimensional Scaling},
     journal = {Ann. Statist.},
     volume = {22},
     number = {1},
     year = {1994},
     pages = { 406-438},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176325376}
}
Buja, Andreas; Logan, B. F.; Reeds, J. A.; Shepp, L. A. Inequalities and Positive-Definite Functions Arising from a Problem in Multidimensional Scaling. Ann. Statist., Tome 22 (1994) no. 1, pp.  406-438. http://gdmltest.u-ga.fr/item/1176325376/