8
$\begingroup$

Given a set $S$ of non-zero vectors in $\mathbb{R}^n,$ and a subspace $L,$ consider $f(S,L)=\max_{s \in S}\frac{\|Ps\|_2}{\|s\|_2}$ where $Ps$ is the orthogonal projection of $s$ onto $L.$

Specifically, consider the set $X$ consisting of the $2^n-1$ (nonzero) vectors with all coordinates $0$ or $1$.

A recent question concerns criteria which might show, for a given subspace $L$, that $f(X,L)$ is small. Here I am concerned with choosing the subspace:

For each $n$ and $d<n$, what is the minimum over all $d$-dimensional subspaces of $f(X,L)?$

If that seems too broad, then the case $d=1$ would be of interest.


Summary There are several good answers here. It is a toss-up which one to choose. I'm going to repost the $d>1$ case as a new question.

Here is a somewhat selective review, all for the case $d=1.$

  1. Gerhard mentioned that $(1,-1,0,0,\cdots)$ attains $\sqrt{1/2}.$

  2. Seva suggested that $(1,1/\sqrt{2},1/\sqrt{3},\cdots)$ is asymptotically optimal attaining $O(\sqrt{1/\log n}).$ This is indeed better but the smallest $n$ for which it beats $\sqrt{1/2}$ is (by my calculations) $n=1203.$ The nice optimality proof references $(1,\sqrt{2}-1,\sqrt{3}-\sqrt{2},\cdots)$ This is actually a better choice, it first beats $\sqrt{1/2}$ for $n=56.$ The two choices are comparable (up to scalar multiple) because $\sqrt{k+1}-\sqrt{k} \approx 1/2\sqrt{k}$. The approximation is pretty good, except for $k=0.$ As this is the largest entry, it takes longer to beat $\sqrt{1/2}$.

  3. Denis essentially does mention $(1,\sqrt{2}-1,\sqrt{3}-\sqrt{2},\cdots)$ and, at least in one edit, suggests reflecting in the center: So for $n=6$ use $(a_1,a_2,a_3,-a_3,-a_2,-a_1)$ where $a_k=\sqrt{k}-\sqrt{k-1}.$ This is superior at $n=4$ and even at $n=3$ with the right rule for the center: It seems obvious that there should be symmetry and entries summing to $0$, but actually $(1,\sqrt{2}-1,-1)$ is the best choice for $n=3$.

  4. Emil nicely lays this out in a comment. Here is my somewhat informal explanation (with some minor details skipped) , in case another perspective is useful. I suggest at the end that this should remind one of linear programming.:

There is no harm in assuming that the subspace is generated by a vector $v=(v_1,v_2,\cdots,v_n)$ with $v_1 > v_2 > \cdots > v_n$ (actually, only $\ge$ is clear, but I will ignore that in the interests of brevity.). By a mild abuse of notation, for $j>0$ let $x_{j}$ be the vector whose first $j$ entries are $1$ and the rest $0$ while $v_{-j}$ has first $n-j$ entries $0$ and the last $j$ equal to $1$.

Given $v$, Let $B \subset X$ be the set of vectors in $X$ which attain the maximum of $\frac{\|Px\|}{\|x\|}.$ I make two claims about $B$:

  • Every vector in $B$ is $x_j$ for some $j$ with $v_j > 0$ or else $x_{-j}$ for some $j$ with $v_{n-j} < 0$ (think about why any other vector with $j$ entries equal to $1$ will be worse.)
  • Unless $B$ is a basis of $\mathbb{R}^n$, There is a $v$ which gives a better ratio. (Because otherwise we should be able perturb the entries of $v$ in such a way as to lower $\frac{\|Px\|}{\|x\|}$ for the vectors already in $B$ (simultaneously keeping them equal and maximal) while raising that ratio slightly for some $x_j$ not yet in $B$.

Together these tell us that $B=\lbrace x_{1},x_{2},\cdots x_n\rbrace$ or else $B=\lbrace x_{1},x_{2},\cdots x_q;x_{q-n},\cdots,x_{-2},x_{-1}\rbrace$ where $v_q>0>v_{q+1}.$ Since the various ratios must all be the same, we deduce that $v=(\alpha a_1,\alpha a_2, \cdots,\alpha a_q; -\beta a_{n-q},\cdots,-\beta a_2,-\beta a_1)$ for the $a_k$ as above. Here $\alpha$ and $\beta$ are positive constants. A bit of reflection shows that they must be equal and hence can be taken to be $1$. Finally, $q$ should be $ n/2 $ (rounded if needed).

Comment: (disclaimer: I am an optimist but not an optimizer so the following may inexact.) Here we have the convex optimization problem of choosing $v$ so as to minimize the largest of $\frac{\|Px\|_2}{\|x\|_2}.$ Had it been $\frac{\|Px\|_1}{\|x\|_1}$ we would have been able to use linear programming. My argument above has the feel of linear programing, perhaps using duality. Perhaps a similar method could uncover optimal subspaces of dimension $d \ge 2.$

$\endgroup$
4
  • $\begingroup$ I presume that the norm is the standard Euclidian and the projection is orthogonal. $\endgroup$ Apr 6, 2011 at 6:58
  • $\begingroup$ Yes, that was my intention. $\endgroup$ Apr 6, 2011 at 7:01
  • $\begingroup$ If n=2, I imagine that the subspace (t, -t) gives the minimum value. For n > 2, and d=1, the subspace (t, -t, 0, ...,0) sets the limbo bar pretty low. For arbitrary d, looking at n = d+1 might help with determining the minimum, and will be something like the subspace orthogonal to (1,1,...,1) (d+1) ones, which you can generalize. This is not a proof so much as a goal. Gerhard "How Low Can You Go" Paseman, 2011.04.06 $\endgroup$ Apr 6, 2011 at 7:08
  • $\begingroup$ @Aaron: there is a typo in the title of the question. @Everybody else: if you like the present question, you may wish to check the question it originated from (mathoverflow.net/questions/60604) and consider voting to re-open it. $\endgroup$
    – Seva
    Apr 6, 2011 at 17:51

2 Answers 2

4
$\begingroup$

My answer concerns with the case $d=1$ only. Without loss of generality, we can focus on the subspaces, generated by a vector with all coordinates non-negative. It is easy to verify that for the subspace $L$, generated by the vector $(1,1/\sqrt{2},...,1/\sqrt{n})$, the projection onto $L$ of any non-zero vector $\epsilon\in\{0,1\}^n$ has lenght at most $\frac{2}{\sqrt{\log n}}\,\|\epsilon\|$. This is essentially the worst case as, on the other hand, for any non-zero vector $z\in R^n$ with non-negative coordinates there exists a non-zero vector $\epsilon\in\{0,1\}^n$ such that $$ \langle z,\epsilon \rangle \ge \frac{2}{\sqrt{\log n+4}}\,\|z\|\|\epsilon\|. $$

To see this, write $z=(z_1,...,z_n)$ and, without loss of generality, assume that $$ z_1 \ge \dotsb \ge z_n \ge 0\quad \text{and}\quad \|z\|=1. $$ Let $\tau := 2/\sqrt{\log n+4}$. We will show that there exists $k\in[n]$ with $z_1+...+z_k\ge\tau\sqrt k$; choosing then $\epsilon$ to be the vector with the first $k$ coordinates equal to $1$ and the rest equal to $0$ completes the proof.

Suppose, for a contradiction, that $z_1+...+z_k<\tau\sqrt{k}$ for $k=1,...,n$. Multiplying this inequality by $z_k-z_{k+1}$ for each $k\in[n-1]$, and by $z_n$ for $k=n$, adding up the resulting estimates, and rearranging the terms, we obtain $$ z_1^2+...+z_n^2 < \tau \big(z_1+(\sqrt2-1)z_2 +...+ (\sqrt n-\sqrt{n-1})z_n \big). $$ Using Cauchy-Schwarz now gives $$ 1 < \tau \Big( \sum_{k=1}^n \big(\sqrt k-\sqrt{k-1}\big)^2 \Big)^{1/2} \|z\| < \tau \sqrt{\log n +4}/2, $$ a contradiction.

$\endgroup$
2
  • $\begingroup$ Assymptotically that might be optimal but if we want to achieve the absolute minimum then it seems better to have a mix of positive and negative coordinates. $\endgroup$ Apr 6, 2011 at 11:43
  • $\begingroup$ @Aaron: absolutely. $\endgroup$
    – Seva
    Apr 6, 2011 at 12:34
3
$\begingroup$

Edited. Conjecture for $d=1$: Define the sequence $v_1,\ldots,v_n$ by $v_1=1$ and $$v_{k+1}=\left(\sqrt{1+\frac1k}-1\right)(v_1+\cdots v_k).$$ Then the $\min\max$ equals $a$ where $$a^2\sum_1^nv_j^2=1.$$ It corresponds to the projection on the line spanned by $u:=(a_1,\ldots,a_n)$ where $a_j:=av_j$.

In this construction, the equality $\|Pe_I\|=\|e_I\|$ ($I$ a subset of indices) is achieved for every subset $I=(1,\ldots,p)$ with $1\le p\le n$.

We have $v_k=\sqrt{k}-\sqrt{k-1}\sim\frac{1}{2\sqrt k}$. Asymptotically, we have $a\sim\frac{2}{\sqrt{\log n}}$.

$\endgroup$
8
  • $\begingroup$ At least for $n=3,$ Your example $(-a,0,a)$ is not quite as good as $(-5,2,5)$. $\endgroup$ Apr 6, 2011 at 11:48
  • 1
    $\begingroup$ @Aaron. See my edits. Now my $(a_1,a_2,a_3)$ is better than $(-5,2,5)$. $\endgroup$ Apr 6, 2011 at 13:22
  • $\begingroup$ @Dennis Aha, so using $\sqrt{2} \approx 7/5.$ in$(-1,\sqrt{2}-1,1).$ $\endgroup$ Apr 6, 2011 at 14:46
  • $\begingroup$ @Aaron. One N in Denis in French. Even if there are two A's in Aaron. $\endgroup$ Apr 6, 2011 at 15:14
  • $\begingroup$ What do you mean Aaron with this new vector $(-1,\sqrt2-1,1)$ ? $\endgroup$ Apr 6, 2011 at 15: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.