Projecting the unit cube onto subspaces - MathOverflow

Projecting the unit cube onto subspaces

2011-04-06T06:51:47Z

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.$

Gerhard mentioned that $(1,-1,0,0,\cdots)$ attains $\sqrt{1/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}$.
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$.
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.$

Answer by Seva for Projecting the unit cube onto subspaces

2011-04-06T07:32:55Z

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.

Answer by Denis Serre for Projecting the unit cube onto subspaces

2011-04-06T07:38:24Z

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}}$.