Consider a vector $v$ such that $v \sim \mathrm{Unif}(\mathbb{S}^{d-1})$, the uniform distribution on the unit sphere in $d$ dimensions.

Question: is there an upper bound on the probability that $v$ has a sparse spectrum? (e.g. $\mathbb{P}\left( |\mathrm{supp}(\hat{v})| \leq \sqrt{d}\right)$, where $\hat{v}$ is the DFT of $v$)? Any pointers to references are more than welcome.

  • $\begingroup$ What is g hat for? $\endgroup$ – Carlos Campos May 24 '19 at 23:53
  • $\begingroup$ @CarlosCampos: Sorry, that was a typo. $\hat{v}$ is the DFT of the vector $v$. $\endgroup$ – VHarisop May 24 '19 at 23:54

Your Answer

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

Browse other questions tagged or ask your own question.