Skip to main content
MathOverflow

Return to Answer

Corrected typo.; edited body
Source Link
Bill Johnson
Bill Johnson
  • 31.5k
  • 5
  • 89
  • 138

Negative result:

See p. 377 in Chapter 15 of Matousek's book, which can be found here. In short, if you want the image of the $k$ points to be between the surface of a convex body $C$$K$ and the surface of $DK$ for some $D>1$, you need the operator to have rank at least $k^{f(D)}$ for some function $f$.

Positive result on a related problem:

In

Johnson, William B.; Lindenstrauss, Joram; Schechtman, Gideon On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. Geometrical aspects of functional analysis (1985/86), 177–184, Lecture Notes in Math., 1267, Springer, Berlin, 1987,

it is proved that for some constant $C$, if you have $k$ points on the surface of a symmetric convex body, then you can put the points isometrically into a suitable $\ell_\infty^m$ in such a way that a random projection of order rank $k^{1/D}$ will place the points between the surface of a symmetric convex body $C$$K$ and the surface of $CDK$; see the paper for a precise statement. I don't think symmetry places much of a role here. We were interested in the embedding of points into a Banach space and so did not think about general convex bodies. The embedding theorem we proved was later made obsolete by Matousek when he proved that and metric space with size $k$ embeds into $\ell_\infty^{n}$ with distortion $D$ with $n$ about $Dk^{1/(2D)} \log k$ (see p. 404 at the above given link).

Negative result:

See p. 377 in Chapter 15 of Matousek's book, which can be found here. In short, if you want the image of the $k$ points to be between the surface of a convex body $C$ and the surface of $DK$ for some $D>1$, you need the operator to have rank at least $k^{f(D)}$ for some function $f$.

Positive result on a related problem:

In

Johnson, William B.; Lindenstrauss, Joram; Schechtman, Gideon On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. Geometrical aspects of functional analysis (1985/86), 177–184, Lecture Notes in Math., 1267, Springer, Berlin, 1987,

it is proved that for some constant $C$, if you have $k$ points on the surface of a symmetric convex body, then you can put the points isometrically into a suitable $\ell_\infty^m$ in such a way that a random projection of order rank $k^{1/D}$ will place the points between the surface of a symmetric convex body $C$ and the surface of $CDK$; see the paper for a precise statement. I don't think symmetry places much of a role here. We were interested in the embedding of points into a Banach space and so did not think about general convex bodies. The embedding theorem we proved was later made obsolete by Matousek when he proved that and metric space with size $k$ embeds into $\ell_\infty^{n}$ with distortion $D$ with $n$ about $Dk^{1/(2D)} \log k$ (see p. 404 at the above given link).

Negative result:

See p. 377 in Chapter 15 of Matousek's book, which can be found here. In short, if you want the image of the $k$ points to be between the surface of a convex body $K$ and the surface of $DK$ for some $D>1$, you need the operator to have rank at least $k^{f(D)}$ for some function $f$.

Positive result on a related problem:

In

Johnson, William B.; Lindenstrauss, Joram; Schechtman, Gideon On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. Geometrical aspects of functional analysis (1985/86), 177–184, Lecture Notes in Math., 1267, Springer, Berlin, 1987,

it is proved that for some constant $C$, if you have $k$ points on the surface of a symmetric convex body, then you can put the points isometrically into a suitable $\ell_\infty^m$ in such a way that a random projection of order rank $k^{1/D}$ will place the points between the surface of a symmetric convex body $K$ and the surface of $CDK$; see the paper for a precise statement. I don't think symmetry places much of a role here. We were interested in the embedding of points into a Banach space and so did not think about general convex bodies. The embedding theorem we proved was later made obsolete by Matousek when he proved that and metric space with size $k$ embeds into $\ell_\infty^{n}$ with distortion $D$ with $n$ about $Dk^{1/(2D)} \log k$ (see p. 404 at the above given link).

Source Link
Bill Johnson
Bill Johnson
  • 31.5k
  • 5
  • 89
  • 138

Negative result:

See p. 377 in Chapter 15 of Matousek's book, which can be found here. In short, if you want the image of the $k$ points to be between the surface of a convex body $C$ and the surface of $DK$ for some $D>1$, you need the operator to have rank at least $k^{f(D)}$ for some function $f$.

Positive result on a related problem:

In

Johnson, William B.; Lindenstrauss, Joram; Schechtman, Gideon On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. Geometrical aspects of functional analysis (1985/86), 177–184, Lecture Notes in Math., 1267, Springer, Berlin, 1987,

it is proved that for some constant $C$, if you have $k$ points on the surface of a symmetric convex body, then you can put the points isometrically into a suitable $\ell_\infty^m$ in such a way that a random projection of order rank $k^{1/D}$ will place the points between the surface of a symmetric convex body $C$ and the surface of $CDK$; see the paper for a precise statement. I don't think symmetry places much of a role here. We were interested in the embedding of points into a Banach space and so did not think about general convex bodies. The embedding theorem we proved was later made obsolete by Matousek when he proved that and metric space with size $k$ embeds into $\ell_\infty^{n}$ with distortion $D$ with $n$ about $Dk^{1/(2D)} \log k$ (see p. 404 at the above given link).