12
$\begingroup$

Let $O$ be a $d$-dimensional rotation matrix (i.e., it has real entries and $OO^T = O^TO = I$). Let $\mathbf{x}$ be a uniformly random bitstring of length $d$, i.e., $\mathbf{x} \sim U(\{0,1\}^d)$. In other words, $\mathbf{x}$ is a vertex of the Hamming cube, selected uniformly at random. I would like to show that there exists a $C > 0$ such that $$\mathbb{P}\left[\|O\mathbf{x}\|_1 \leq \frac{d}{4}\right] \leq 2^{-Cd}.$$ I am horribly stuck, any ideas on how to approach this problem would be very much appreciated. Below are some of my own attempts. This question is cross-posted at math stack exchange here.


Observation 1: If $O = I$, then the statement holds.

If $O = I$, then $\|O\mathbf{x}\|_1 = \|\mathbf{x}\|_1$ is simply the number of ones in the bitstring. Among the $2^d$ choices for $\mathbf{x}$, the number of choices that satisfies $\|\mathbf{x}\|_1 \leq d/4$ is

$$1 + \binom{d}{1} + \binom{d}{2} + \cdots + \binom{d}{\lfloor d/4\rfloor} \leq 2^{dH(\lfloor d/4\rfloor/d)} \leq 2^{dH(1/4)},$$ hence the probability is upper bounded by $2^{-d(1-H(1/4))}$. Here, $H(\cdot)$ is the binary entropy function, i.e., $H(p) = -p\log_2(p) - (1-p)\log_2(1-p)$.

Observation 2: Numerical experiments support this result. Below is a plot of the probability versus the dimension, where $O$ is selected at random:

Plot of the probability versus the dimension

The blue line is the probability. The orange line is the bound derived in the case where $O = I$.

For comparison, here is the same numerical experiment, but with $O = I$:

enter image description here

Thus, it appears that the introduction of $O$ decreases the probability.

Both plots are obtained by sampling $100000$ $\mathbf{x}$'s at random. The code is here:

import numpy as np
import matplotlib.pyplot as plt
import random
from scipy.stats import ortho_group

H = lambda p : -p * np.log2(p) - (1-p) * np.log2(1-p)
C = 1 - H(1/4)
print(C)

N = 100000
ds,Ps = [],[]
for d in range(2,40):
    O = ortho_group.rvs(dim = d)
    # O = np.eye(d)
    P = 0
    for _ in range(N):
        x = random.choices(range(2), k = d)
        if np.linalg.norm(O @ x, ord = 1) <= d/4: P += 1/N
    print(d,P)
    ds.append(d)
    Ps.append(P)

fig = plt.figure()
ax = fig.gca()
ax.plot(ds, Ps)
ax.plot(ds, [2**(-C*d) for d in ds])
ax.set_yscale('log')
ax.set_xlabel('d')
ax.set_ylabel('P')
plt.show()
$\endgroup$
7
  • 1
    $\begingroup$ I don't know about your question, but it should not be too difficult to show that, on average over $O$, your question has a positive answer. Your question then boils down to concentration inequalities for the $\ell_1$ norm of a random uniform point on the unit sphere if $\mathbf{R}^d$, which are certainly well-known. This at least explains your numerical evidence. $\endgroup$ Apr 16 at 16:05
  • $\begingroup$ Thanks for the reply! Indeed, on average over $O$ it should work out. :) But in this case I'm specifically looking for an argument that works for all $O$ (or find an $O$ for which the statement doesn't hold, of course :p) $\endgroup$
    – arriopolis
    Apr 16 at 16:49
  • $\begingroup$ Is the $\frac 1 4$ in your question important, or are you happy with another constant, say $\frac 1 {10}$? $\endgroup$ Apr 16 at 16:53
  • $\begingroup$ I would also be fine with changing d/4 to d/10 or d/10000. If this is still too hard, then even though d/log(d) would be somewhat weaker, it would still be interesting. What interests me most is the method behind the proof, not the precise constants. :) $\endgroup$
    – arriopolis
    Apr 16 at 16:56
  • 2
    $\begingroup$ Maybe one can use the Sauer-Shelah lemma and argue that if the probability is too large, then there is a subcube $\{0,1\}^{cn}$ "inside" the $\ell_1$ unit ball, which is not possible because e.g. of mean width estimates? $\endgroup$ Apr 16 at 17:26
4
+50
$\begingroup$

Here is an attempt to the problem for a worst-case $O$, with worse constants. So fix $O$, letting $o_i$ denote its $i$th row, and take $X$ random in $\{0,1\}^d$.

  1. We claim that $E |\langle o_i, X\rangle| \ge cst$. To see this, write $$\langle o_i, X\rangle = \langle o_i, \frac{{\bf 1}}{2}\rangle + \langle o_i, (X - \frac{{\bf 1}}{2})\rangle$$ and assume WLOG the first term on the RHS is non-negative. The second term on the RHS is a weighted sum of Rademacher random variables, and so with probability at least $\frac{1}{20}$ it is above its standard deviation, which is $\Omega(1)$ (see for example this paper of Oleszkiewicz)

  2. Adding over all $i$'s, the result holds in expectation: $E \|OX\|_1 \ge cst\cdot d$. But since the function $x \mapsto \|Ox\|_1$ is $\sqrt{d}$-Lipschitz wrt $\ell_2$ (and convex), we should be able to use concentration to say that the probability that we get below this mean minus $\frac{cst \cdot d}{2}$ is at most $e^{-cst' \cdot d}$ (see for example Corollary 4.23 of van Handel's notes). This gives the result.

$\endgroup$
6
  • $\begingroup$ Can you expand a bit the second point? I do not see directly how the corollary in Handel's notes gives the result. $\endgroup$ Apr 16 at 19:43
  • 2
    $\begingroup$ BTW, another way to see that $E\|OX\|_1 \geq cd$ is by symmetrization and Khintchine's inequality. $\endgroup$ Apr 16 at 19:44
  • 1
    $\begingroup$ @MikaeldelaSalle: I may be goofing off, but it seems by letting $f(x) := \|Ox\|_1$, van Handel's corollary should give that $f(X)$ is $d$-subgaussian (it is stated in terms of gradients but we can replace by subgradients, and the subgradients of $f$ should have $\ell_2$ norm at most $\sqrt{d}$). But $d$-subgaussian RVs have concentration $Pr(f(X) \le E f(X) - \epsilon d) \le e^{-\frac{(\epsilon d)^2}{2 d}}$, and we should get the result. $\endgroup$
    – Marco
    Apr 16 at 19:57
  • $\begingroup$ Thanks, I got it. $\endgroup$ Apr 16 at 20:11
  • $\begingroup$ Thanks a lot for the response! :) This certainly looks like an interesting approach. I will have a more careful look at the details after the weekend, and then award the bounty accordingly. $\endgroup$
    – arriopolis
    Apr 17 at 11:24
3
$\begingroup$

We prove the weaker bound $$ \mathbf{P} \left[ \|O \mathbb{x}\|_1 \leq \frac{cd}{\sqrt{\log d}} \right] \leq 2^{-Cd} $$ for some constants $C, c$.

Define the Gaussian mean width of a compact subset $A \subset \mathbf{R}^d$ as $$ w(A) = \mathbf{E} \sup_{x \in A} \langle G,x \rangle $$ where $G$ is a standard Gaussian vector in $\mathbf{R}^d$. We use the following properties

  1. If $\pi$ is an orthogonal projection, then $w(\pi(A))\leq w(A)$.
  2. If $A = \{0,1\}^k \subset \{0,1\}^n$, then $w(A)=k/\sqrt{2\pi}$.
  3. If $A=B_1^d$ (the unit $\ell_1$ ball), then $w(A) \leq \sqrt{2\log d}$.
  4. $w$ is rotation invariant

Let $A$ be the set of $x \in \{0,1\}^d$ such that $\|Ox\|_1 \leq cd/\sqrt{\log d}$. We have $w(A) \leq w(cd/\sqrt{\log d} \cdot B_1^d) \leq c\sqrt{2}d$.

If $\mathrm{card}(A) \geq 2^{dH(1/4)}$, then the Sauer--Shelah lemma implies that there is a coordinate projection $\pi$ of rank $k=d/4$ such that $\pi(A)$ identifies with $\{0,1\}^k$. Therefore, $w(A) \geq w(\pi(A))=d/4\sqrt{2\pi}$. If we choose $c=1/8\pi$, combining both estimates gives the bound $\mathrm{card}(A) < 2^{dH(1/4)}$, as needed.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for the response! :) This certainly looks like an interesting approach. I will have a more careful look at the details after the weekend, and then award the bounty accordingly. $\endgroup$
    – arriopolis
    Apr 17 at 11:24
  • $\begingroup$ Since Marco's answer provided a better scaling, I decided to award the bounty to them. Still, thanks for the solution you proposed! :) $\endgroup$
    – arriopolis
    Apr 20 at 0:16
1
$\begingroup$

Adding more detail to Mikael's point, the result seems to hold on average over $O$ because of the following:

  1. Using a Chernoff bound, we can see that the probability that for any constant $\epsilon$, with probability at least $1- e^{-C d}$ the random vector $x$ has at least $\frac{(1-\epsilon)d}{2}$ 1's.

  2. Consider a fixed vector $x \in \{0,1\}^d$. For a uniformly distributed $O$, $O x$ is uniformly distributed on the sphere of size $\sqrt{\|x\|_1}$. This has distribution essentially the same as the vector $\sqrt{\|x\|_1} (G_1,\ldots,G_d)$, where the $G_i$'s are independent Gaussians $N(0,\frac{1}{d})$ (in fact $\sqrt{\|x\|_1}$ has the same distribution as $\sqrt{\|x\|_1} (G_1,\ldots,G_d)/\|G\|_2$, or alternatively one can bypass using Gaussians and work with concentration on the sphere, as Mikael suggested).

Then in expectation (over $O$) $$E \|Ox\|_1 \approx \sqrt{\|x\|_1} \cdot \|G\|_1 = \sqrt{\|x\|_1} \cdot \sqrt{d} \sqrt{\frac{2}{\pi}},$$ where the last inequality uses the fact that the expected value of a folded Gaussian of standard deviation $\sigma$ is $\sigma \sqrt{\frac{2}{\pi}}$.

Moreover, the function $\|\cdot\|_1$ is $\sqrt{d}$ Lipschitz wrt $\ell_2$ we can use concentration of such functions over Gaussian space to get that with probability at least $1 - e^{- Cd}$ we have $$\|Ox\|_1 \ge (1-\epsilon) \sqrt{\|x\|_1} \cdot \sqrt{d} \sqrt{\frac{2}{\pi}},$$ see for example Example 4.2 in van Handel excellent notes or inequality (1.6) of Ledoux-Talagrand "Probability in Banach Spaces".

  1. Taking a union bound over the two steps above seems to give the desired result.
$\endgroup$
2
  • $\begingroup$ Thanks a lot for your idea! :) Do I understand correctly that this only works whenever $O$ is chosen randomly too? Ideally, I would like to find an argument in which $O$ is fixed (or find a single $O$ for which the claim doesn't hold, naturally :p). $\endgroup$
    – arriopolis
    Apr 16 at 16:45
  • 1
    $\begingroup$ Sorry, I should have read the question more carefully :). I'll edit the answer to make it clear that it does not address the actual question. $\endgroup$
    – Marco
    Apr 16 at 16:52

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.