5
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice answer! Is it true that your vector $v$ is an example of what is sometimes called a `badly approximable vector'? $\endgroup$
    – Robby McKilliam
    Oct 10, 2010 at 10:03
  • $\begingroup$ 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. $\endgroup$
    – Greg Kuperberg
    Oct 10, 2010 at 10:12
  • $\begingroup$ 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)? $\endgroup$
    – Seva
    Oct 13, 2010 at 21:28
  • $\begingroup$ That's a much more complicated question, of course, and I don't have a solution. The matrix has a Perron-Frobenius eigenvector which determines its norm. You could try to make an example in which that eigenvector looks like the vector $v$ in the example. $\endgroup$
    – Greg Kuperberg
    Oct 14, 2010 at 6:20
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Matthew Daws
    Oct 10, 2010 at 8:54
  • 1
    $\begingroup$ 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! $\endgroup$
    – Seva
    Oct 10, 2010 at 9:18
  • $\begingroup$ 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"! $\endgroup$
    – Seva
    Oct 10, 2010 at 9:46
  • $\begingroup$ yea, the title was somehow misleading. No matter, you then got a very clear and thorough answer by Greg Kuperberg. $\endgroup$
    – Pietro Majer
    Oct 10, 2010 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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