1
$\begingroup$

Let $\mathbf{1}\in\mathbb{R}^d$ be the $d$-dimensional all-ones vector and let $n\sim\mathcal{N}(0, \sigma^2 I_{d\times d})$, show that $$ \frac{\| \mathbf{1} + n \|_1}{\|\mathbf{1} + n \|_2} \ge c \sqrt{d} $$ with high probability in $d$, for constant $c$ (independent of $\sigma, d$).

That is, prove that adding Gaussian noise never significantly improves sparsity in the sense of $\ell_1 / \ell_2$ ratio. Generalization to arbitrary dense vectors are of course welcome.

Improve this question
$\endgroup$
1
  • $\begingroup$ The issue is large $d$. For that, use the LLN: The numerator grows like $dE|1+\sigma g|$ while the denominator grows like $\sqrt{ d E(1+\sigma^2 g^2)}$,where $g$ is a standard normal. So your constant $c$ is (in leading order in $d$) simply the minimum over $\sigma$ of $E|1+\sigma g| /\sqrt{E(1+\sigma^2 g^2)}$. The latter is clearly strictly positive (only need to check behavior at $0$ and infinity...) $\endgroup$
    – ofer zeitouni
    Commented May 18, 2019 at 14:06

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .