MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 edited body

The answer is no. First, to understand the question, WLOG $f$ is symmetric and positive definite; a general $f$ has a polar decomposition $f = os$ and the orthogonal factor $o$ has no effect on any of the norms in question. Then, WLOG $f$ is a rank 1 projection. The second and subsequent eigenvalues of $f$ do not increase $||f||$, but they could increase $||f(x)||$ for some specific $x$. So in summary, we can assume that $f = vv^T$ for some vector $v$. The question is whether $v$ must always make a large small angle with some binary vector.

Let $$v = (1,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{3}},\ldots,\frac{1}{\sqrt{m}}).$$ If $w$ is a binary vector of weight $k$, then $|v \cdot w|$ is maximized when the non-zero entries of $w$ are at the beginning. However, $$||w|| = \sqrt{k} \qquad ||v|| = \Theta(\sqrt{\log m}) \qquad |v \cdot w| = O(\sqrt{k}).$$ This means that the angle between $w$ and $v$ is smalllarge, and therefore $||f(w)|| = ||v (v \cdot w)||$ is small compared to $||f||\;||w|| = ||v||^2 ||w||$.

The same proof works if $\{0,1\}$ is replaced by $\{-1,0,1\}$, or indeed by any finite subset of $\mathbb{R}$. On the other hand, there is a variation of the question with a positive answer.

Similar to Pietro Majer's remark, you can interpret the question as a comparison between two norms on $\mathbb{R}^m$. One is the $\ell^2$ norm, and the other is the norm whose unit ball is a polytope whose vertices are at the points in $S = \{0,1\}^m$ and its negative. By the theory of spherical packings on a sphere, for any $c < 1$, there exists a set $S$ of exponential size in $m$ such that the two norms are equal up to a factor of $c$. This is then a positive answer for that sample set of vector, even for constants close to 1. But such a set (coming from the centers of a sphere covering of the sphere) has to be fairly complicated, and I don't know if there are explicit asymptotic examples.

3 added 2 characters in body

The answer is no. First, to understand the question, WLOG $f$ is symmetric and positive definite; a general $f$ has a polar decomposition $f = os$ and the orthogonal factor $o$ has no effect on any of the norms in question. Then, WLOG $f$ is a rank 1 projection. The second and subsequent eigenvalues of $f$ do not increase $||f||$, but they could increase $||f(x)||$ for some specific $x$. So in summary, we can assume that $f = vv^T$ for some vector $v$. The question is whether $v$ must always make a large angle with some binary vector.

Let $$v = (1,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{3}},\ldots,\frac{1}{\sqrt{m}}).$$ If $w$ is a binary vector of weight $k$, then $|v \cdot w|$ is maximized when the non-zero entries of $w$ are at the beginning. However, $$||w|| = \sqrt{k} \qquad ||v|| = \Theta(\sqrt{\log m}) \qquad |v \cdot w| = O(\sqrt{k}).$$ This means that the angle between $w$ and $v$ is small, and therefore $||f(w)|| = ||v (v \cdot w)||$ is small compared to $||f||\;||w|| = ||v||^2 ||w||$.

The same proof works if $\{0,1\}$ is replaced by $\{-1,0,1\}$, or indeed by any finite subset of $\mathbb{R}$. On the other hand, there is a variation of the question with a positive answer.

Similar to Pietro Majer's remark, you can interpret the question as a comparison between two norms on $\mathbb{R}^m$. One is the $\ell^2$ norm, and the other is the norm whose unit ball is a polytope whose vertices are at the points in $S = {0,1}^m$ \{0,1\}^m$ and its negative. By the theory of spherical packings on a sphere, for any$c < 1$, there exists a set$S$of exponential size in$m$such that the two norms are equal up to a factor of$c$. This is then a positive answer for that sample set of vector, even for constants close to 1. But such a set (coming from the centers of a sphere covering of the sphere) has to be fairly complicated, and I don't know if there are explicit asymptotic examples. 2 added 21 characters in body; added 4 characters in body The answer is no. First, to understand the question, WLOG$f$is symmetric and positive definite; a general$f$has a polar decomposition$f = os$and the orthogonal factor$o$has no effect on any of the norms in question. Then, WLOG$f$is a rank 1 projection. The second and subsequent eigenvalues of$f$do not increase$||f||$, but they could increase$||f(x)||$for some specific$x$. So in summary, we can assume that$f = vv^T$for some vector$v$. The question is whether$v$must always make a large angle with some binary vector. Let $$v = (1,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{3}},\ldots,\frac{1}{\sqrt{m}}).$$ If$w$is a binary vector of weight$k$, then$|v \cdot w|$is maximized when the non-zero entries of$w$are at the beginning. However, $$||w|| = \sqrt{k} \qquad ||v|| = \Theta(\sqrt{\log m}) \qquad |v \cdot w| = O(\sqrt{k}).$$ This means that the angle between$w$and$v$is small, and therefore$f(w) ||f(w)|| = v ||v (v \cdot w)$w)||$ is short small compared to $||f(v)||\;||w||$.||f||\;||w|| = ||v||^2 ||w||$. The same proof works if ${0,1}$\{0,1\}$ is replaced by ${-1,0,1}$, \{-1,0,1\}$, or indeed by any finite subset of$\mathbb{R}$. On the other hand, there is a variation of the question with a positive answer. Similar to Pietro Majer's remark, you can interpret the question as a comparison between two norms on$\mathbb{R}^m$. One is the$\ell^2$norm, and the other is the norm whose unit ball is a polytope whose vertices are at the points in$S = {0,1}^m$and its negative. By the theory of spherical packings on a sphere, for any$c < 1$, there exists a set$S$of exponential size in$m$such that the two norms are equal up to a factor of$c\$. This is then a positive answer for that sample set of vector, even for constants close to 1. But such a set (coming from the centers of a sphere covering of the sphere) has to be fairly complicated, and I don't know if there are explicit asymptotic examples.

1