51

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.

This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest possible proof strategies?

I have vectors $v_1, \ldots, v_k$ in ${\bf R}^n$. Each of them has euclidean length at most $.01$, and for every unit vector $u \in {\bf R}^n$ they satisfy $$\sum_{i=1}^k |\langle u,v_i\rangle|^2 = 1.$$ Is it possible to find a set of indices $S \subset \{1, \ldots, k\}$ such that $$.0001 < \sum_{i \in S} |\langle u,v_i\rangle|^2 < .9999$$ for every unit vector $u$? This will imply the same bounds when summing over the complement of $S$.

The $.01$ and $.0001$ aren't important; I just need the result for some positive $\delta$ and $\epsilon$. But they have to be independent of $k$ and $n$. (This may seem unlikely, until you try to construct a counterexample.)

The motivation is that this is a (very slightly simplified) equivalent version of the famous Kadison-Singer problem. A solution would have important consequences in operator theory, harmonic analysis, and C*-algebra. Many people have worked on this problem, but perhaps not in the above form, which I feel exposes the combinatorial difficulty which is the real root of the problem.

Nik Weaver
  • 42,041
  • 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 – Gerhard Paseman May 12 '12 at 17:11
  • 3
    I too would like to see an example of such a set of vectors $v_i$. – Benjamin Young May 12 '12 at 18:32
  • 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. :-) – Greg Kuperberg May 12 '12 at 19:01
  • 3
    @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. – Nik Weaver May 12 '12 at 19:27
  • 1
    @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. – Nik Weaver May 12 '12 at 20:17
  • 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 – Gerhard Paseman May 13 '12 at 05:28
  • 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. – Seva May 14 '12 at 20:02
  • 1
    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? – Seva May 14 '12 at 20:03
  • 2
    @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)$.) – Nik Weaver May 17 '12 at 19:01
  • 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 – Gerhard Paseman May 17 '12 at 19:33
  • @Nik: exactly how do you apply Beck-Fiala (or Beck-Spencer)? – Seva May 17 '12 at 19:46
  • Also, is the case of $n$ fixed ($n=2$?) easy? – Seva May 17 '12 at 19:47
  • @Gerhard: I'm not assuming the $v_i$ are distinct, but it doesn't affect the problem if you impose that requirement. – Nik Weaver May 17 '12 at 21:28
  • @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. – Nik Weaver May 17 '12 at 21:34
  • @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$). – Nik Weaver May 17 '12 at 21:39
  • @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? – domotorp May 18 '12 at 06:57
  • 1
    @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. – Nik Weaver May 18 '12 at 09:53
  • Sorry about that! – Nik Weaver May 18 '12 at 10:07
  • Indeed. So the problem becomes interesting in high dimensions which I have no hope to imagine... – domotorp May 18 '12 at 12:47
  • @Nik: a very nice application of Fiala-Beck! – Seva May 18 '12 at 19:41
  • @Seva: thank you! But it doesn't seem so helpful. In high dimensions there are so many other directions where something can go wrong. – Nik Weaver May 19 '12 at 03:37
  • 5
    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 http://arxiv.org/abs/1101.4324 – Guillaume Aubrun May 22 '12 at 09:01
  • @Guillaume: this looks really interesting. Thank you. – Nik Weaver May 22 '12 at 19:24

2 Answers2

16

This paper contains a proposed solution to the problem. The acknowledgements suggest that MO might have facilitated the solution, should it be correct. (I'm speculating that Gil Kalai found out about Nik Weaver's formulation of the problem from this MO question.)

Jon Bannon
  • 6,987
  • 6
  • 68
  • 110
2

This is mainly a comment. My first guess would be that if it is true, then a random subset of density $1/2$ works. A result in this direction is Lemma 3.2 in

M. Rudelson, Contact points of convex bodies, Israel Journal of Mathematics, 1997, Volume 101, Number 1, Pages 93-124.

It says:

Lemma :Let $x_1,...,x_k$ be vectors in $\mathbb R^n$, $\varepsilon_1,...,\varepsilon_k$ be independent Bernoulli variables, taking values $1,-1$ with probability $1/2$. Then $${\mathbb E} \left\| \sum_{i=1}^k \varepsilon_i |x_i\rangle {\langle x_i} | \right\|\leq C \log(n) \sqrt{\log(k)} \max_i \|x_i\| \left\| \sum_{i=1}^k |x_i\rangle \langle x_i| \right\|^{1/2}$$ for some absolute constant C.

In your case, this says that a random set of density $1/2$ solves the easier problem where $\delta$ may depend on $n$ and $k$. At the same time it proves much more, since there is even concentration around $1/2$. More precisely, if $ \sum_{i=1}^k |x_i\rangle \langle x_i| =1$ and $\|x_i\|< \delta$, then

$${\mathbb E} \left\|\frac12 - \sum_{i=1}^k \eta_i |x_i\rangle {\langle x_i} | \right\|\leq C/2 \log(n) \sqrt{\log(k)} \cdot \delta,$$ where $\eta_i$ are independent Bernoulli with values in $\{0,1\}$.

Since $n \leq k \delta^2$ (looking at the trace), an easy calculation shows that $\delta$ only depends on $k$. At the same time, it seems to me that the problem is getting easier if $k$ is larger, but I cannot substantiate this claim. Remark 3.3 in the same paper shows that the inequality cannot be improved to become independent of $n$ and $k$. This somehow shows that choosing a random subset is too naive; at least when one studies the expected value of the norm as in the inequality above.

Andreas Thom
  • 25,252
  • 4
    Note that a random subset of density 1/2 cannot work in general for Nik's question : if the initial set contains 1000 copies of a small multiple of each vector from the canonical basis in $\mathbb{R}^n$, and $n$ is very large, then typically a random half-set will miss one of the vectors. – Guillaume Aubrun May 23 '12 at 09:50