6
$\begingroup$

Consider $n$ i.i.d spherically distributed random vectors $z_1 ,\cdots , z_n \sim \text{Unif}(\mathbb{S}^{d-1})$. What is the best lower bound on $n$ for which whp there exists a constant $c>0$ such that the following bound holds for all $v\in \mathbb{R}^d\backslash \{0\}$:

\begin{equation} cn\leq \left\vert\left\{i:\langle z_i,v \rangle>0 \right\} \right\vert \end{equation}

$\endgroup$
3
  • 1
    $\begingroup$ Note that $n \ge d$ since otherwise, you can always find a $v$ that is orthogonal to all of the $z_i$'s so the set is empty. $\endgroup$ Jul 28 '21 at 2:04
  • $\begingroup$ "whp"? Is that, with high probability? $\endgroup$ Nov 25 '21 at 1:24
  • $\begingroup$ Sorry for the late response. Yes, whp means with high probability. $\endgroup$ Dec 8 '21 at 21:53
6
$\begingroup$

$\newcommand\PP{\mathbb P}$ Surely $n_\min \lesssim d$, because it works for $c = 1/4$ and $n=160d$.

We use that the number of "distinct" $v$ with respect to the classifiers $\textrm{sgn}\langle \cdot, z_i \rangle$ is $$ \sum_{i=0}^{d-1} \binom{n-1}{i} \le \left( \frac{ne}{d} \right)^d $$

The proof can be found in [Bürgisser and Cucker (2013), Lemma 13.7]. (Anyone has a better reference?)

Let $X = \lvert \left\{ i ~:~ \langle z_i, e_1 \rangle \right\} \rvert$ for a basis vector $e_1$. Then, by the union bound $$ \PP \left[ ~\exists v ~~ \lvert \left\{ i ~:~ \langle z_i, v \rangle > 0 \right\}\rvert < cn \right] \\ \le \left( \frac{ne}{d} \right)^d \PP \left[ X < cn \right] \\ \le \exp(d\log(n) - \frac{n}{16} + d - d \log{d}) \\ = \exp(\log(160)d - 9d) \xrightarrow{d \to \infty} 0$$

where we used the Chernoff bound on $\PP[X < cn]$, in the form $$ \PP\left[X \le (1 - \delta) \mathbb E[X] \right] \le \exp(-\frac12 \delta^2 \mathbb E[X]). $$

As noted in the comment by Sandeep Silwal, $n_{\text{min}} \ge d$ due to the strict inequality sign in the question. So the answer to the original question is $n_{\text{min}} = \Theta(d)$.

$\endgroup$
2
  • 1
    $\begingroup$ you meant $<cn, \exists v$ in the first line of the chain of inequalities? $\endgroup$ Jul 13 '21 at 19:21
  • 1
    $\begingroup$ Thank you for the fix! I will check again, but it seems correct now. $\endgroup$ Jul 13 '21 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.