Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given an operator $f\colon R^m\to R^n$, can one always find a non-zero vector $x\in \{ 0,1 \}^m$ such that $\|f(x)\|/\|x\|\ge0.01\|f\|$? (Here I denote by $\|\cdot\|$ both the Euclidean norms in $R^m$ and $R^n$ and the induced operator norm.) The answer may well be negative -- any examples?


In case the answer to the question above is ``no'' (or unknown), would it help to assume that the matrix of $f$ with respect to the standard orthonormal bases of $R^m$ and $R^n$ has all its elements equal to $0$ or $1$?


As I see it, this is basically a question in the geometry of numbers, and I would expect the answer should be known.

share|improve this question

2 Answers 2

up vote 10 down vote accepted

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 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 large, 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.

share|improve this answer
    
Nice answer! Is it true that your vector $v$ is an example of what is sometimes called a `badly approximable vector'? –  Robby McKilliam Oct 10 '10 at 10:03
    
Of course it is badly approximable in context, but Google tells me that the standard context is something else. The term usually refers to a number or vector that is badly approximable by rational numbers or vectors, in the sense that the common denominator of a good rational approximation is as large as possible. This is vaguely similar, but not really the same. –  Greg Kuperberg Oct 10 '10 at 10:12
    
@Greg : just a trivial remark : it seems that you exchanged "large angle" ($\cos$ near 0) and "small angle" ($|\cos|\geq c>0$) in your answer (equivalently, said "angle", thinking "absolute cosine of angle"). –  BS. Oct 12 '10 at 9:55
    
@BS Yeah, you're right. I think that I fixed it now. –  Greg Kuperberg Oct 12 '10 at 12:05
    
Great, this answers my first question - as suspected, the answer is negative. How about the second question? What if we assume that the operator under consideration has a zero-one matrix (in a pair of orthonormal bases)? –  Seva Oct 13 '10 at 21:28

Of course no. Remember that the operator norm of $A$ wrto the Eucliedan norms is the attained at an eigenvector of $S:=A^TA. $ Try a suitable simple binary $2\times 2$ matrix and compare the values of $\|Ax\|$ on the eigenvectors of $S$ and in the three nonzero binary vectors $(01), (10), (11).$

However, if instead you take in the domain $\mathbb{R}^n$ either the $l^1$ norm $\|\cdot \|_1$ or the $l^\infty$ norm $\|\cdot\|_\infty$ then, whatever norm you have in the target space $\mathbb{R}^m$, the operator norm of $A$ is attained in an extremal point of the unit ball of the domain, which is in both cases a binary vector.

share|improve this answer
1  
Yes, I agree. However, I wonder if putting constraints upon $m$ or $n$ could help. The original questions asks for a constant of $0.01$. There's no way this can be absolute, but how does the best constant vary with $n$ and $m$? –  Matthew Daws Oct 10 '10 at 8:54
1  
I may have gaven the title of my question an overly simplified form. In fact, I want the norm of $f$ to be attained on a binary vector up to a constant factor (written as $0.01$ in the body of my question). Thus, no one single particular example would resolve the question! –  Seva Oct 10 '10 at 9:18
    
As to the best constant -- seems I can get a very good one; namely, something like $1/\sqrt{\log s}$, with $s=\min\{m,n\}$. My question is whether this can be improved to a "constant constant"! –  Seva Oct 10 '10 at 9:46
    
yea, the title was somehow misleading. No matter, you then got a very clear and thorough answer by Greg Kuperberg. –  Pietro Majer Oct 10 '10 at 18:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.