52
$\begingroup$

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.

Improve this question
$\endgroup$
23
  • 3
    $\begingroup$ I too would like to see an example of such a set of vectors $v_i$. $\endgroup$
    – Benjamin Young
    Commented May 12, 2012 at 18:32
  • 3
    $\begingroup$ @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. $\endgroup$
    – Nik Weaver
    Commented May 12, 2012 at 19:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – Nik Weaver
    Commented May 12, 2012 at 20:17
  • 2
    $\begingroup$ @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)$.) $\endgroup$
    – Nik Weaver
    Commented May 17, 2012 at 19:01
  • 5
    $\begingroup$ 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 $\endgroup$
    – Guillaume Aubrun
    Commented May 22, 2012 at 9:01

2 Answers 2

Reset to default
16
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm not so sure he did find out from here, but I guess that he can always drop by to confirm or refute. $\endgroup$
    – Yemon Choi
    Commented Jun 18, 2013 at 10:28
  • 1
    $\begingroup$ I mostly posted this so that if someone from the community finds an error with the proposed solution he or she will post it here. Please do so if you find any mistake with the argument. (KS is certainly newsworthy!) $\endgroup$
    – Jon Bannon
    Commented Jun 18, 2013 at 10:41
  • 2
    $\begingroup$ My initial impression is that the solution is correct. $\endgroup$
    – Nik Weaver
    Commented Jun 18, 2013 at 17:33
  • $\begingroup$ @Nik: This would be fantastic! $\endgroup$
    – Jon Bannon
    Commented Jun 18, 2013 at 21:34
  • $\begingroup$ Some context can be found here: arxiv.org/pdf/math/0510024v2.pdf $\endgroup$
    – Jon Bannon
    Commented Jun 19, 2013 at 0:02
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – Guillaume Aubrun
    Commented May 23, 2012 at 9:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .