[Note: This question is trivially impossible, though I leave the original form below. If 
is the uniform measure on 
, then any two sets of 
measure are at distance 
by concentration of measure. Thus it is impossible to find 
sets satisfying the desired bound. I will try to think of the right question and repost. Unfortunately, I now recall having gone down this path a few times before, and I fear there may not be a relevant elementary open question after all.]
Here is an interesting and elementary (to state) open question whose resolution would give an optimal higher-order Cheeger esimate. The goal is to replace the factor 
in Theorem 1 of the previous post with a 
factor, or even an optimal bound of 
.
Fix 
and let 
denote a probability measure on the 
-dimensional sphere 
. For the purpose of this question, one can assume that is supported on a finite number of points. Suppose also that is isotropic in the sense that, for every 
,
Now our goal is to find, for some 
, a collection of (measurable) subsets 
such that 
for each 
, and such that for 
, we have
In Lemma 5 of the previous post, we proved that this is possible for 
and 
. In this paper, we improve the estimate on 
somewhat, though the best-known is still 
for some 
.
Question:
Is it possible to achieve 
? One could even hope for and 
.
Two extreme cases are when (1) is uniform on , or (2) is uniform on the standard basis 
. In the first case, one can easily achieve 
(in fact, one could even get 
sets satisfying these bounds). In the second case, taking each set to contain a single basis vector achieves 
and 
.
If one only wants to find, say, 
sets instead of 
sets, then it is indeed possible to achieve and 
. [Update: This is actually impossible for the reasons stated above. To get the corresponding bounds, we do a random projection into 
dimensions. This only preserves the original Euclidean distances on average.] Furthermore, for , this bound on is asymptotically the best possible.
Like this:
Like Loading...
How much slack is allowed in the isotropic condition? Suppose $\mu$ is supported on $x_1,\ldots,x_n$ and we don’t have $\sum_i x_ix_i^T = k^{-1}\cdot I$, but we do have, say, $\|\sum_i x_ix_i^T – k^{-1}\cdot I\| \le \gamma$. Is there some value of $\gamma>0$ that is still acceptable for your application?
Comment by minilek — February 23, 2013 @ 5:28 pm
Oh right $\mu$ is part of the input …my above question is probably nonsense.
Comment by minilek — February 23, 2013 @ 5:30 pm
It’s possible that it holds in this greater generality, but even the perfect isotropy case is open.
Comment by James Lee — February 24, 2013 @ 10:42 am