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, 2021 at 2:04
  • $\begingroup$ "whp"? Is that, with high probability? $\endgroup$ Nov 25, 2021 at 1:24
  • $\begingroup$ Sorry for the late response. Yes, whp means with high probability. $\endgroup$ Dec 8, 2021 at 21:53

1 Answer 1

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, 2021 at 19:21
  • 1
    $\begingroup$ Thank you for the fix! I will check again, but it seems correct now. $\endgroup$ Jul 13, 2021 at 19:38

Your Answer

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

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