Manuscript Psy01-A@1 · Psy01-A.tex · theorem · 94477fa3

Theorem: Bernoulli-mask matrix concentration

Concentration: what survivor counts do and do not imply › An independent-mask comparison · lines 1566–1618 · proof included or linked

Psy01-A@1#thm:maskbernstein, Psy01-A@1#eq:matrixbernstein, Psy01-A@1#eq:frobeniusvariance

Back to manuscript

Let $W \in R^{m \times n}$ be fixed, and let the entries of $M$ be independent Bernoulli variables with retention probability $p$ . Define

B = W \circ M, R = i, j max \abs W_{ij},

and

v = p (1 - p) max {i max j \sum W_{ij}^{2}, j max i \sum W_{ij}^{2}} .

For $t > 0$ , in the nondegenerate case,

P {\norm B - p W_{op} \geq t} \leq (m + n) exp [- \frac{t ^{2}}{2 ( v + R t /3 )}] .

Furthermore,

E \norm B - p W_{F}^{2} = p (1 - p) \norm W_{F}^{2} .

Proof. Write

B - p W = i, j \sum X_{ij}, X_{ij} = (M_{ij} - p) W_{ij} e_{i} e_{j}^{T} .

The summands are independent, mean zero, and have norm at most $R$ . The two matrix variance sums are diagonal:

i, j \sum E X_{ij} X_{ij}^{T} = p (1 - p) diag (j \sum W_{ij}^{2})_{i},

i, j \sum E X_{ij}^{T} X_{ij} = p (1 - p) diag (i \sum W_{ij}^{2})_{j} .

Their maximal operator norm is $v$ . The rectangular matrix Bernstein inequality gives (eq:matrixbernstein). Taking the expectation of the sum of squared entries gives (eq:frobeniusvariance).

Displayed formulas in this passage

unlabeled · line 1571
$B = W \circ M, R = i, j max \abs W_{ij},$
unlabeled · line 1576
$v = p (1 - p) max {i max j \sum W_{ij}^{2}, j max i \sum W_{ij}^{2}} .$
Psy01-A@1#eq:matrixbernstein · line 1583
$P {\norm B - p W_{op} \geq t} \leq (m + n) exp [- \frac{t ^{2}}{2 ( v + R t /3 )}] .$
Psy01-A@1#eq:frobeniusvariance · line 1590
$E \norm B - p W_{F}^{2} = p (1 - p) \norm W_{F}^{2} .$
unlabeled · line 1599
$B - p W = i, j \sum X_{ij}, X_{ij} = (M_{ij} - p) W_{ij} e_{i} e_{j}^{T} .$
unlabeled · line 1605
$i, j \sum E X_{ij} X_{ij}^{T} = p (1 - p) diag (j \sum W_{ij}^{2})_{i},$
unlabeled · line 1609
$i, j \sum E X_{ij}^{T} X_{ij} = p (1 - p) diag (i \sum W_{ij}^{2})_{j} .$

Theorem: Bernoulli-mask matrix concentration

Displayed formulas in this passage

Nearby in this section