Let us assume $X\in\mathbb{R}^{n\times d}, rank(X)=d$, integer $k\in\mathbb{N},k\ll d$, positive constant $0<\epsilon<1$, and $\mathcal{S}\subset \mathbb{R}^d$ denotes the unit sphere. We also denote $k$-sparse spans of $X$ by $Y = \{X\beta : \beta\in\mathbb{R}^d,|\beta|_0=k\}$.

We would like to find the largest integer $m$ such that there exists vectors $\{v_1,...,v_m\}\subset (Y\cap\mathcal{S})$ that satisfiy $\forall i\neq j\in[m] : \langle v_i,v_j \rangle\ge \epsilon $, i.e., no pairs of vectors has angle less than $\cos^{-1}{\epsilon}$. What is the largest that $m$ can be with regard to $d,n, k$, and $\epsilon$? In other words, which configuration of $X$ would lead to the largest possible $m$? Asymptotic upper bounds are desirable.

This problem has some resemblance to spherical code. If we only consider vectors on the sphere, it would be spherical code with dimension $d$. If we take the intersection of unit sphere with one $k$-dimensional hyperplane we get a $k$-dimensional unit sphere and the answer would be spherical code for dimension $k$. But as we take the intersection with $\binom{d}{k}$ hyperplanes of dimension $k$, the answer must lie somewhere in between these two.

Is there any reference, book, article that could point to possible answers? Any ideas how to formulate this problem in a way that is more approachable? I know that there are some semi-definite programming approaches to find upper bound for kissing numbers, like this. Could they possibly be adopted for our purposes?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.