Separated sets in unions of frames

~ James

In celebration of the recent resolution of the Kadison-Singer problem by Marcus, Spielman, and Srivastava, here is a question on isotropic point sets on which Kadison-Singer does not (seem to) shed any light. A positive resolution would likely have strong implications for the Sparsest Cut problem and SDP hierarchies. The question arose in discussions with Shayan Oveis Gharan, Prasad Raghavendra, and David Steurer.

Open Question: Do there exist constants \varepsilon, \delta > 0 such that for any k \in \mathbb N, the following holds? Let \mathcal B_1, \mathcal B_2, \ldots, \mathcal B_k \subseteq \mathbb R^k be a collection of k orthonormal bases and define W = \mathcal B_1 \cup \mathcal B_2 \cup \cdots \cup \mathcal B_k. Then there are subsets A,B \subseteq W with |A|,|B| \geq \varepsilon |W| and \min_{x \in A, y \in B} \|x-y\|_2 \geq \delta.

[Some additional notes: One piece of intuition for why the question should have a positive resolution is that these k orthonormal bases which together comprise at most k^2 vectors cannot possibly “fill” k-dimensional space in a way that achieves k-dimensional isoperimetry. One would seem to need \exp(O(k)) points for this.

One can state an equivalent question in terms of vertex expansion. Say that a graph G=(V,E) on k^2 vertices is a vertex expander if |N(S)| \geq 1.1 |S| for all subsets S \subseteq V with |S| \leq |V|/2. Here, N(S) denotes all the nodes that are in S or are adjacent to S. Then one can ask whether there exists a 1-1 mapping from V to \mathcal B_1 \cup \cdots \cup \mathcal B_k for some orthonormal bases \{\mathcal B_i\} such that the endpoints of every edge are mapped at most o(1) apart (as k \to \infty).]

7 thoughts on “Separated sets in unions of frames”

  2. Strictly speaking, there is no direct implication because this question is the “hard part” of a more general question. The more general question is to find such separated sets given any set of n \leq k^{O(1)} unit vectors in isotropic position.

    The implication is as follows: For every \delta > 0, there is a number C(\delta) such that Sparsest Cut admits a C(\delta)-approximation in time 2^{n^{\delta}}, i.e. sub-exponential time constant factor approximations to (uniform) Sparsest Cut.

  3. What is your precise definition of isotropic position? Is it that the covariance matrix (the sum of uu^T over vectors u in the set) is a multiple of the identity or is it exactly the identity? Seems like it’s the former, but just want to make sure.

  4. More specifically, the general condition is as follows: Given n unit vectors v_1, v_2, \ldots, v_n \in \mathbb R^k, we assume that \frac{1}{n} \sum_{i=1}^n v_i v_i^T = \frac{1}{k} I. Of course, a special case is when the vectors \{v_i\} can be partitioned into orthonormal bases.

  5. Is it important that the bases are over the reals? I think I can see a construction of such sets over complex vector spaces.

Leave a comment