Timeline for Projecting the unit cube onto a subspace
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 6, 2011 at 7:52 | comment | added | Seva | Do not know what the absolute winner is - but as to $1/\sqrt{\log n}$, I have just posted an answer to your question... | |
| Apr 6, 2011 at 6:58 | comment | added | Aaron Meyerowitz | I just posted a question mathoverflow.net/questions/60775. If you can prove that $1/\sqrt{\log n}$ is best possible, that would be nice. I'd like to see the absolute best one-dimensional subspace. | |
| Apr 6, 2011 at 5:58 | comment | added | Seva |
You are right that this particular vector gives a slightly better constant, but I am not concerned much about improving the constant here. (The order of magnitude $1/\sqrt{\log n}$ is best possible, by the way.) I just gave this as an example of a "good", or "oblique", subspace. More exotic subspaces are difficult to test directly, and so I am interested in some general criteria.
|
|
| Apr 6, 2011 at 5:08 | comment | added | Aaron Meyerowitz | OK I think that achieves its maximum ratio when it sends the all 1's vector $j$ to one of length roughly $\frac{\|j\|}{\sqrt{\log n}}.$ It would be better (but not optimal) to use $(1,1/\sqrt2,...,1/\sqrt {n/2},-1,-1/\sqrt2,...,-1/\sqrt {n/2}).$ None of the projections you care about are longer and many are shorter. Hence none of the ratios are larger. | |
| Apr 6, 2011 at 4:56 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
added 162 characters in body
|
| Apr 5, 2011 at 14:10 | comment | added | Seva |
I am afraid there is still some misunderstanding here. Let's say that a subspace $L<R^n$ is good if for any $z\in\{0,1\}^n$, the projection of $z$ onto $L$ has length at most $\|z\|/\log\log n$. Good subspaces do exist: say, the one-dimensional subspace spanned by the vector $(1,1/\sqrt2,...,1/\sqrt n)$ is good. What I seek is a sufficiently general and versatile criterion for a subspace to be good.
|
|
| Apr 5, 2011 at 9:03 | comment | added | Seva |
I see your point - but my question is not about the subspaces that you consider! I don't want all projections to be (relatively) small for any vector $z\in\{0,1\}^n$ and any subspace $L$ - I have some particular subspace $L$ in mind, and I wonder what properties of this my subspace can guarantee that it is "not aligned with the vectors from $\{0,1\}^n$".
|
|
| Apr 5, 2011 at 8:31 | comment | added | Aaron Meyerowitz | OK, thanks, I think I fixed it. For $d=1$ the subspace spanned by $[1,-1,0,0,0,\cdots]$ sends some things to the zero vector and others to $[1/2,-1/2,0,0,0,\cdots]$. For $d=2$ some things go to $[2/3,-1/3,-1/3,0,0,0,\cdots]$. For $d=3$ some things go to $[1/2,1/2,-1/2,-1/2,0,0,\cdots]$. | |
| Apr 5, 2011 at 7:57 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
added 14 characters in body
|
| Apr 5, 2011 at 7:04 | comment | added | Seva |
Concerning "what $L$ actually is": is is an invariant subspace of a (high) tensor power of the "Fibonacci matrix" $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. I am not asking, however, to look at my particular problem; rather, I am to trying to figure out what are possible approaches and useful tools.
|
|
| Apr 5, 2011 at 7:02 | comment | added | Seva |
Thanks for an attempt to answer in essence - but I am afraid, I don't understood much here. For $d=1$ you seem to claim that the longest projection of a vector from $\{0,1\}^n$ onto your subspace is $0$, do you? Anyway, I am speaking about some particular subspace, and I need the length of the projection normalized by dividing by the length of the vector itself.
|
|
| Apr 5, 2011 at 4:52 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
added 14 characters in body
|
| Apr 5, 2011 at 4:47 | history | answered | Aaron Meyerowitz | CC BY-SA 2.5 |