Timeline for vector balancing problem
Current License: CC BY-SA 3.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 30, 2013 at 23:09 | history | edited | Nik Weaver | CC BY-SA 3.0 |
deleted 157 characters in body
|
| Jun 30, 2013 at 23:07 | vote | accept | Nik Weaver | ||
| Jun 19, 2013 at 5:54 | history | edited | Nik Weaver | CC BY-SA 3.0 |
added 273 characters in body
|
| Jun 18, 2013 at 10:09 | answer | added | Jon Bannon | timeline score: 16 | |
| May 24, 2012 at 19:22 | history | bounty ended | Nik Weaver | ||
| May 23, 2012 at 8:06 | answer | added | Andreas Thom | timeline score: 2 | |
| May 22, 2012 at 19:24 | comment | added | Nik Weaver | @Guillaume: this looks really interesting. Thank you. | |
| May 22, 2012 at 9:01 | comment | added | Guillaume Aubrun | Do you know the recent results by Srivastava and coauthors about sparsification of graphs ? There are able to select points by a clever inductive procedure, and prove results that were out of reach by random constructions. Maybe some variant of their ideas can be useful here ? See e.g. the survey arxiv.org/abs/1101.4324 | |
| May 19, 2012 at 3:37 | comment | added | Nik Weaver | @Seva: thank you! But it doesn't seem so helpful. In high dimensions there are so many other directions where something can go wrong. | |
| May 18, 2012 at 19:41 | comment | added | Seva | @Nik: a very nice application of Fiala-Beck! | |
| May 18, 2012 at 12:47 | comment | added | domotorp | Indeed. So the problem becomes interesting in high dimensions which I have no hope to imagine... | |
| May 18, 2012 at 10:07 | comment | added | Nik Weaver | Sorry about that! | |
| May 18, 2012 at 9:53 | comment | added | Nik Weaver | @domotorp: I should have said "continuous Beck-Fiala theorem". "This result [classical Beck-Fiala] has an interpretation as a theorem about incidence matrices and its generalization to real matrices (with essentially the same proof) is called the continuous Beck-Fiala theorem." --- Akemann and Anderson, The continuous Beck-Fiala theorem is optimal, Discrete Math ${\bf 146}$ (1995), 1-9. | |
| May 18, 2012 at 6:57 | comment | added | domotorp | @Nik for Beck-Fiala: If I got your argument, the points of the hypergraph are the k vectors vi and the n unitvectors ei form the sets. But now the degree of each point is n, so using Beck-Fiala you can only get a bound of O(n). Where did I go wrong? | |
| May 17, 2012 at 21:39 | comment | added | Nik Weaver | @Seva: $n=2$ should be easy. I expect a random subset $S$ would succeed with nonzero probability. But this argument stops working in higher dimensions (I suppose exactly where it stops working depends on your choice of $\delta$ and $\epsilon$). | |
| May 17, 2012 at 21:34 | comment | added | Nik Weaver | @Seva: For each $v_i$ form the vector $(|\langle v_i,e_1\rangle|^2,…,|\langle v_i,e_n\rangle|^2)$. This gives me $k$ vectors in ${\bf R}^n$, and the sum of the entries of each one is at most $.01$. By Beck-Fiala you can multiply each vector by $\pm 1$ in such a way that the sum is at most $.02$ in absolute value, in each entry. | |
| May 17, 2012 at 21:28 | comment | added | Nik Weaver | @Gerhard: I'm not assuming the $v_i$ are distinct, but it doesn't affect the problem if you impose that requirement. | |
| May 17, 2012 at 19:47 | comment | added | Seva | Also, is the case of $n$ fixed ($n=2$?) easy? | |
| May 17, 2012 at 19:46 | comment | added | Seva | @Nik: exactly how do you apply Beck-Fiala (or Beck-Spencer)? | |
| May 17, 2012 at 19:33 | comment | added | Gerhard Paseman | Permit a dumb but clarifying question. It is clear to me that S is a finite set, but it is not clear to me if the vectors v_i for i in S form a set of the same cardinality as S. Is it allowed that v_i = v_j for i distinct from j? (It seems easier for me to imagine the collection of v_i as a multiset for some unexplainable reason.) Gerhard "It Does Make A Difference" Paseman, 2012.05.17 | |
| May 17, 2012 at 19:02 | history | bounty started | Nik Weaver | ||
| May 17, 2012 at 19:01 | comment | added | Nik Weaver | @Seva: Excellent question, it is not even obvious that you can make the inequality hold on a fixed orthonormal basis. However, this is possible by the Beck-Fiala theorem. (In fact you can stay within the interval $(.5−2\delta,.5+2\delta)$.) | |
| May 14, 2012 at 20:03 | comment | added | Seva | Is it easy to show that there exists $S$ such that the double inequality we want to secure holds whenever $u$ is a vector of the standard basis? Would this imply the result in the general case? | |
| May 14, 2012 at 20:02 | comment | added | Seva | Another simple way to construct a set $\{v_j\}$ with the property in question: take an orthonormal basis $\{e_1,\ldots,e_n\}\subset{\mathbb R}^n$, scale down every vector $e_i$ dividing it by an integer $K_i\ge 100$, and then define $\{v_j\}$ to be the set where each of the resulting vectors $K_i^{-1}e_i$ is represented $K_i^2$ times. | |
| May 13, 2012 at 5:28 | comment | added | Gerhard Paseman | Since you are asking for ideas, here is one: you have a specialized partition of unity on the n sphere, where each partition member looks like every other up to scale and rotation. So you should be able to pick a small subset that covers the sphere in a non0 and non1 way everywhere. To acheive the bounds you need to know the geometry of the sphere and some estimates on what fraction of the set you will need to do the cover. If you can't fill in the valleys without making peaks too large, this says something about your set. Gerhard "Details Left To Bedeviled Reader" Paseman, 2012.05.12 | |
| May 12, 2012 at 20:17 | comment | added | Nik Weaver | @Gerhard and Benjamin. You can also fill out any family of vectors satisfying $\sum |\langle u,v_i\rangle|^2 \leq 1$ for all unit vectors $u$, to one which has exact equality for all $u$. It's easier to see this by reframing the problem in terms of the rank one positive operators $u \mapsto \langle u,v_i\rangle v_i$, and trying to get them to sum up to the identity operator. | |
| May 12, 2012 at 19:27 | comment | added | Nik Weaver | @Gerhard and Benjamin. Orthogonally project the standard basis of ${\bf R}^d$ onto an $n$-dimensional subspace, and you'll get a set of vectors in the subspace such that $\sum |\langle u,v_i\rangle|^2 = 1$ on every unit vector $u$. How small the $v_i$ are depends on how the subspace is situated, but they can easily be made as small as you like. | |
| May 12, 2012 at 19:20 | history | edited | Nik Weaver | CC BY-SA 3.0 |
added 1 characters in body
|
| May 12, 2012 at 19:01 | comment | added | Greg Kuperberg | Your formula does a good job of explaining that the constants aren't important, because you have $10^{-4}$ on one side and $1-10^{-3}$ on the other side, and of course you can reverse by passing to the complement. :-) | |
| May 12, 2012 at 18:32 | comment | added | Benjamin Young | I too would like to see an example of such a set of vectors $v_i$. | |
| May 12, 2012 at 17:11 | comment | added | Gerhard Paseman | Intuitively yes: just take "every other vector" in the set. However, I am having a hard time visualizing such a set that has the claimed property in the first place. If you do have one, then you should be able to flip k coins at random, pick the vectors indicated by heads, and almost surely have your desired set. If every sequence of coin flips leads to dissatisfaction, I would say that there was something wrong with your given set. Gerhard "Ask Me About System Design" Paseman, 2012.05.12 | |
| May 12, 2012 at 16:20 | history | asked | Nik Weaver | CC BY-SA 3.0 |