This is an updated revision of a recent question where I asked:

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

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

Call this minimum $m_{n,d}.$ I amend the question to ask specifically about $d>1$ as the answers given for the previous question all concerned the case $d=1.$ Together they pretty well completed that case. The gist for $d=1$ (see that question for details) is that for $n=5$ it is optimal to take the span of the vector $v_5=(1,\sqrt(2)-1,\sqrt{3}-\sqrt{2}; 1-\sqrt{2},-1)$ and that the vectors where the maximum ratio is obtained are $(1,0,0,0,0), (1,1,0,0,0), (1,1,1,0,0), (0,0,0,0,1)$ and $(0,0,0,0,1).$ (A basis of $\mathbb{R}^5.$) For other values of $n$ a similar construction is used, breaking in the exact middle for even $n$. This gives the exact value of $m_{n,1}.$ It is not an attractive expression but $m_{n,1}=O(\frac{1}{\sqrt{\log n}}).$ I won't attempt to make that more precise but it should be possible.

A few comments:

  • Call a class of vectors in $\mathbb{R}^n$ good if the projection of $X$ onto any one of them is $O(\frac{1}{\sqrt{\log n}})$. Examples include these variations of $v_n$: Not switching from positive to negative exactly in the middle (or at all). Replacing some of the entries (the middle ones or the negative ones) by 0. Replacing $v_n$ with $v_t$ for some smaller $t$ padded by 0's on one or both sides. etc.

  • For a dimension $d$ subspace to be good (with the obvious definition) requires every vector in $L$ to be good. So one can think of various ways to do this starting with a basis of good vectors. Perhaps this can show that $m_{N,d}\approx m_{n,1}$ for $N=nd$ or $N=nd+r$ with $r<d.$

  • These vague constructions hint at ways to have $f(X,L)$ small with several vectors $x$ attaining the maximum. It should be possible to have a basis or perhaps even a set of $nd$ vectors in $X$ attain the maximum by starting with a good example and then perturbing the subspace so as to reduce this maximum ratio (while keeping it constant on these vectors) and raising it on some other vectors until the set attaining the maximum is enlarged. This is not linear programing but it reminds me of it and duality might be useful.(see the previous question for slightly more details.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.