1
$\begingroup$

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?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.