Projecting the unit cube onto subspaces - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T03:42:35Z http://mathoverflow.net/feeds/question/60775 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60775/projecting-the-unit-cube-onto-subspaces Projecting the unit cube onto subspaces Aaron Meyerowitz 2011-04-06T06:51:47Z 2011-04-07T08:10:42Z <p>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.$</p> <p>Specifically, consider the set $X$ consisting of the $2^n-1$ (nonzero) vectors with all coordinates $0$ or $1$. </p> <p>A <a href="http://mathoverflow.net/questions/60604" rel="nofollow">recent question</a> concerns criteria which might show, for a given subspace $L$, that $f(X,L)$ is small. Here I am concerned with choosing the subspace: </p> <blockquote> <p>For each $n$ and <code>$d&lt;n$</code>, what is the minimum over all $d$-dimensional subspaces of $f(X,L)?$</p> </blockquote> <p>If that seems too broad, then the case $d=1$ would be of interest. </p> <hr> <p><strong>Summary</strong> There are several good answers here. It is a toss-up which one to choose. I'm going to repost the <code>$d&gt;1$</code> case as a <a href="http://mathoverflow.net/questions/60901" rel="nofollow">new question</a>.</p> <p>Here is a somewhat selective review, all for the case $d=1.$</p> <ol> <li><p>Gerhard mentioned that $(1,-1,0,0,\cdots)$ attains $\sqrt{1/2}.$</p></li> <li><p>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}$.</p></li> <li><p>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$.</p></li> <li><p>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.:</p></li> </ol> <p>There is no harm in assuming that the subspace is generated by a vector <code>$v=(v_1,v_2,\cdots,v_n)$</code> with <code>$v_1 &gt; v_2 &gt; \cdots &gt; v_n$</code> (actually, only $\ge$ is clear, but I will ignore that in the interests of brevity.). By a mild abuse of notation, for <code>$j&gt;0$ let $x_{j}$</code> be the vector whose first $j$ entries are $1$ and the rest $0$ while <code>$v_{-j}$</code> has first $n-j$ entries $0$ and the last $j$ equal to $1$. </p> <p>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$:</p> <ul> <li>Every vector in $B$ is $x_j$ for some $j$ with <code>$v_j &gt; 0$</code> or else $x_{-j}$ for some $j$ with <code>$v_{n-j} &lt; 0$</code> (think about why any other vector with $j$ entries equal to $1$ will be worse.) </li> <li>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$.</li> </ul> <p>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 <code>$v=(\alpha a_1,\alpha a_2, \cdots,\alpha a_q; -\beta a_{n-q},\cdots,-\beta a_2,-\beta a_1)$</code> for the <code>$a_k$</code> 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).</p> <p>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 <code>$d \ge 2.$</code></p> http://mathoverflow.net/questions/60775/projecting-the-unit-cube-onto-subspaces/60778#60778 Answer by Seva for Projecting the unit cube onto subspaces Seva 2011-04-06T07:32:55Z 2011-04-06T07:39:11Z <p>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 <code>$(1,1/\sqrt{2},...,1/\sqrt{n})$</code>, the projection onto $L$ of any non-zero vector <code>$\epsilon\in\{0,1\}^n$</code> has lenght at most <code>$\frac{2}{\sqrt{\log n}}\,\|\epsilon\|$</code>. 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 <code>$\epsilon\in\{0,1\}^n$</code> such that $$\langle z,\epsilon \rangle \ge \frac{2}{\sqrt{\log n+4}}\,\|z\|\|\epsilon\|.$$</p> <p>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.</p> <p>Suppose, for a contradiction, that $z_1+...+z_k&lt;\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 &lt; \tau \big(z_1+(\sqrt2-1)z_2 +...+ (\sqrt n-\sqrt{n-1})z_n \big).$$ Using Cauchy-Schwarz now gives $$1 &lt; \tau \Big( \sum_{k=1}^n \big(\sqrt k-\sqrt{k-1}\big)^2 \Big)^{1/2} \|z\| &lt; \tau \sqrt{\log n +4}/2,$$ a contradiction.</p> http://mathoverflow.net/questions/60775/projecting-the-unit-cube-onto-subspaces/60779#60779 Answer by Denis Serre for Projecting the unit cube onto subspaces Denis Serre 2011-04-06T07:38:24Z 2011-04-06T13:22:03Z <p><em>Edited</em>. 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$. </p> <p>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$. </p> <p>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}}$.</p>