$s \in [l]$, $\pi_s$ is contained in a single column of $\alpha$. The number of partitions into pairings of each multiset $\alpha_{:j}$ is at most $|\alpha_{:j}|^{\frac{|\alpha_{:j}|}{2}-1}$. We deduce that the total number of satisfying partitions is at most $|\alpha|^{\frac{|\alpha|}{2}-r_{\alpha}}$. Since $|\alpha| \ge 2\#\alpha$, we upper-bound this quantity by $|\alpha|^{\alpha|\alpha|-\#\alpha-r_{\alpha}}$.

Plugging this with Lemma D.1 in Theorem 2.5 leads us to

$$|\kappa_{x,\alpha}| \le \lambda^{|\alpha|} \rho^{r_{\alpha}} |\alpha|^{2(|\alpha|-r_{\alpha}-\#\alpha+2)} \min \left( \left(\frac{1}{K}\right)^{\#\alpha+r_{\alpha}-\frac{|\alpha|}{2}-1}, \frac{1}{K} \right),$$

which concludes the proof of the lemma.

**D.8. Proof of Lemma D.3.** Let $\alpha \in \mathbb{N}^{n \times p} \ne 0$. We shall suppose successively that one of the conditions of Lemma D.3 is not satisfied and prove that $\kappa_{x,\alpha} = 0$.

1. We suppose that either $\alpha_1 := 0$ or $\alpha_2 := 0$. By symmetry, we suppose that $\alpha_2 := 0$. Then, the label $k_2^*$ is independent of the random variables $(X_{ij})_{ij \in \alpha} \cup \{k_1^*\}$. And since $k_2^*$ follows a uniform law on $[K]$, we directly deduce that $x = \mathbf{1}_{k_1^* = k_2^*}$ is also independent from $(X_{ij})_{ij \in \alpha} \cup \{k_1^*\}$ (and a fortiori from $(X_{ij})_{ij \in \alpha}$). By Lemma B.2, we have $\kappa_{x,\alpha} = 0$.

2. We suppose that there exists $i_0 \in \text{supp}(\alpha)$ such that $\sum_{j \in [p]} \alpha_{i_0 j} = 1$ and we shall prove that $\kappa_{x,\alpha} = 0$. $\varepsilon_{i_0}$ is symmetric and independent from the other random variables. In particular, $x, (X_{ij})_{ij \in \alpha}$ has the same distribution as $x, ((-1)^{1_{i=i_0}} X_{ij})_{ij \in \alpha}$ and so $\kappa_{x,\alpha} = -\kappa_{x,\alpha}$. We deduce $\kappa_{x,\alpha} = 0$.

3. We suppose that there exists $j_0 \in [p]$ such that $\sum_{i \in [n]} \alpha_{ij_0} = 1$. It is clear in that case that there does not exist any decomposition $\alpha = \beta_1 + \dots + \beta_l$ with $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$. Hence, Theorem 2.5 ensures that $\kappa_{x,\alpha} = 0$.

4. Let us suppose that the graph $G_{\alpha}^{-} \cup \{(u_1, u_2)\}$ is not connected. Let $\beta_1 + \dots + \beta_l = \alpha$ with $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$. Let us prove that $C_{x,\beta_1, \dots, \beta_l}$ is null. The fact that $G_{\alpha}^{-} \cup \{(u_1, u_2)\}$ is disconnected implies that the graph $\mathcal{W}$ of $[0, l]$ defined is Section D.1 is also disconnected. We deduce from Lemma D.4 that $C_{x,\beta_1, \dots, \beta_l}$ is null. This being true for all decompositions, we conclude that $\kappa_{x,\alpha} = 0$.

## APPENDIX E: PROOF OF THEOREM 5.1

Theorem 5.1 states two LD lower bounds (41) and (42) in two different regimes. We prove them separately in Subsections E.1 and prf:lowerboundbi1.

**E.1. Reduction to a $L$-dimensional problem: Proof of (42).** Without loss of generality, we suppose that $\sigma^2 = 1$. Let us fix $D \in \mathbb{N}$ and let us suppose that

$$\zeta' := \lambda^4 D^{10} \frac{5p^2}{L} \max \left(1, \frac{n}{K^2}\right) < 1.$$

Working conditionally on $l^*, \varepsilon^r, \varepsilon^c$, we get

$$ \begin{aligned} MMSE_{\le D} &= \inf_{f \in \mathbb{R}_D[Y]} \mathbb{E} \left[ (f(Y) - x)^2 \right] \\ &= \inf_{f \in \mathbb{R}_D[Y]} \mathbb{E}_{l^*} \left[ \mathbb{E} \left[ (f(Y) - x)^2 | l^*, \varepsilon^r, \varepsilon^c \right] \right] \\ &\ge \mathbb{E}_{l^*, \varepsilon^r, \varepsilon^c} \left[ \inf_{f \in \mathbb{R}_D[Y]} \mathbb{E} \left[ (f(Y) - x)^2 | l^*, \varepsilon^r, \varepsilon^c \right] \right] . \end{aligned} $$
In the following, we fix $l^*, \varepsilon^r, \varepsilon^c$ and we consider

$$MMSE_{\leq D}(l^*, \varepsilon^r, \varepsilon^c) = \inf_{f \in \mathbb{R}_D[Y]} \mathbb{E} \left[ (f(Y) - x)^2 |l^*, \varepsilon^r, \varepsilon^c \right].$$

Let us suppose that, for all $l \in [L]$, we have, $|\{j \in [p], l_j^* = l\}| \leq 5/p$. We write

$$MMSE_{\leq D}(l^*, \varepsilon^r, \varepsilon^c) = \frac{1}{K} - \mathrm{corr}^2_{\leq D}(l^*, \varepsilon^r, \varepsilon^c).$$

We shall upper-bound $corr^2_{\leq D}(l^*, \varepsilon^r, \varepsilon^c)$ using Proposition 2.1 which states that

$$corr^2_{\leq D}(l^*, \varepsilon^r, \varepsilon^c) \leq \sum_{\alpha \in \mathbb{N}^{n \times p}} \frac{\kappa_{x,\alpha}(l^*, \varepsilon^r, \varepsilon^c)^2}{\alpha!},$$

where $\kappa_{x,\alpha}(l^*, \varepsilon^r, \varepsilon^c) = \mathrm{Cum}(x, (X_{ij})_{ij \in \alpha} |l^*, \varepsilon^r, \varepsilon^c)$, where we see $\alpha$ as a multiset of $[n] \times [p]$. This conditional biclustering model is a special case of the latent model (1) with

$$Z = (k^*, l^*, \varepsilon^r, \varepsilon^c), \quad \delta_{ij}(k^*) = \varepsilon_i^r \varepsilon_j^c, \quad \text{and} \quad \theta_{i,j}(k^*) = (k_i^*, l_j^*),$$

where $l^*, \varepsilon^r, \varepsilon^c$ are considered as deterministic. Combining Proposition 2.1 and Theorem 2.5, we need to upper-bound, for any multiset $\alpha$ and any decomposition $\alpha = \beta_1 + \dots + \beta_l$ with $|\beta_s| = 2$, the cumulant

$$C_{x,\beta_1,\dots,\beta_l}(l^*, \varepsilon^r, \varepsilon^c) = \mathrm{Cum} \left( x, \prod_{ij \in \beta_1} \varepsilon_i^r \varepsilon_j^c \mathbf{1}_{\Omega_{\beta_1}(k^*,l^*)}, \dots, \prod_{ij \in \beta_l} \varepsilon_i^r \varepsilon_j^c \mathbf{1}_{\Omega_{\beta_l}(k^*,l^*)} \middle| l^*, \varepsilon^r, \varepsilon^c \right),$$

with $\Omega_{\beta}(k^*, l^*) := \{|\{(k_i^*, l_j^*) : (i,j) \in \beta\}| = 1\}$. Building on Lemma C.1, we derive the following upper-bound, whose proof is postponed to the end of the section.

**LEMMA E.1.** We recall that $\#\alpha$ stands for the cardinality of the points $i \in [n]$ such that $\alpha_i \neq 0$ and that $|\alpha| := \sum_{ij} \alpha_{ij}$. We have, for all $l^*, \varepsilon^r, \varepsilon^c$, that

$$|C_{x,\beta_1,\dots,\beta_l}(l^*, \varepsilon^r, \varepsilon^c)| \leq |\alpha|^{|\alpha|} \left(\frac{1}{K}\right)^{\#\alpha-1}.$$

The number of partition of the multiset $\alpha$ into groups of size 2 is at most $|\alpha|^{\frac{|\alpha|}{2}-1} \leq |\alpha|^{\frac{|\alpha|}{2}}$. Combining this with Lemma E.1 and Theorem 2.5 leads us to

$$(73) \qquad |\kappa_{x,\alpha}(l^*, \varepsilon^r, \varepsilon^c)| \leq |\alpha|^{\frac{|\alpha|}{2}} |\alpha|^{|\alpha|} \left(\frac{1}{K}\right)^{\#\alpha-1}.$$

Then, we prune the multisets $\alpha$ for which $\kappa_{x,\alpha}(l^*, \varepsilon^r, \varepsilon^c) = 0$.

**LEMMA E.2.** Let $\alpha \in \mathbb{N}^{n \times p}$ be non-zero. If $\kappa_{x,\alpha}(l^*, \varepsilon^r, \varepsilon^c) \neq 0$, then:

1. $1, 2 \in \mathrm{supp}(\alpha)$;

2. All the elements $i \in \mathrm{supp}(\alpha) \setminus \{1, 2\}$ are such that $|\alpha_i| \geq 2$;

3. There exists a decomposition $\alpha = \beta_1 + \dots + \beta_l$, where $\beta_s = \{(i_s, j_s), (i'_s, j'_s)\}$, and such that, for all $s \in [l]$, $l_{j_s}^* = l_{j'_s}^*$.
In particular, we have $\#\alpha \ge 2$ and $|\alpha| \ge 2\#\alpha - 2$.

The last step of the proof amounts to counting the number of $\alpha$'s satisfying the conditions of Lemma E.2.

LEMMA E.3. Suppose that, for all $l \in [L]$, we have $|\{j \in [p], l_j^* = l\}| \le 5 \frac{p}{L}$. Let $d \in [D]$ and $m \in [2, \frac{d+2}{2}]$. Then, there are at most $d^2 d n^{m-2} \left(5 \frac{p^2}{L}\right)^{\frac{d}{2}}$ matrices $\alpha$ satisfying the conditions of Lemma E.2 with $|\alpha| = d$ and $\#\alpha = m$.

Combining Lemma E.3 and (73), and supposing that, for all $l \in [L]$, we have $|\{j \in [p], l_j^* = l\}| \le 5 \frac{p}{L}$, we end up with

$$ 
\begin{aligned}
corr_{\le D}^2 - \frac{1}{K^2} &\le \frac{1}{K^2} \sum_{d=1}^{D} \sum_{m \in [2, \frac{d+2}{2}]} d^{5d} \lambda^{2d} \left(\frac{n}{K^2}\right)^{m-2} \left(5 \frac{p^2}{L}\right)^{\frac{d}{2}} \\
&\le \frac{1}{K^2} \sum_{d=1}^{D} \sum_{m \in [2, \frac{d+2}{2}]} \left(\sqrt{\frac{5p^2}{L}} \lambda^{2d} d^5\right)^d \left(\frac{n}{K^2}\right)^{m-2} \\
&\le \frac{1}{K^2} \sum_{d=1}^{D} \sum_{m \in [2, \frac{d+2}{2}]} \left(\sqrt{\frac{5p^2}{L}} \lambda^{2d} D^5\right)^{d-2(m-2)} \left(\lambda^4 D^{10} \frac{5p^2 n}{LK^2}\right)^{m-2} \\
&\le \frac{1}{K^2} \sum_{d=1}^{D} \frac{d}{2} \zeta^{d/2} \\
&\le \frac{1}{K^2} \frac{\sqrt{\zeta'}}{(1 - \sqrt{\zeta'})^2}.
\end{aligned}
$$

Hence, provided that, for all $l \in [L]$, $|\{j \in [p], l_j^* = l\}| \le 5 \frac{p}{L}$, we have

$$ MMSE_{\le D}(l^*, \varepsilon^r, \varepsilon_c) \ge \frac{1}{K} - \frac{1}{K^2} \frac{\sqrt{\zeta'}}{(1 - \sqrt{\zeta'})^2}. $$

Moreover, using a large deviation Inequality for Binomial random variables –see e.g Exercise 12.9.7 of [34]–, we have that, with probability at least $1 - L \exp(-\frac{5p}{2L} \log(5))$, for all $l \in [L]$, $|\{j \in [p], l_j^* = l\}| \le 5 \frac{p}{L}$. We deduce from this that

$$ MMSE_{\le D} \ge \left(1 - L \exp\left(-\frac{5p}{2L} \log(5)\right)\right) \left(\frac{1}{K} - \frac{1}{K^2} \frac{\sqrt{\zeta'}}{(1 - \sqrt{\zeta'})^2}\right). $$

PROOF OF LEMMA E.1. Let $\beta_1, \dots, \beta_l$ such that $|\beta_s| = 2$ for $s \in [l]$ and such that $\beta_1 + \dots + \beta_l = \alpha$ and let $l^* \in [L]^p$. We seek to upper-bound
$$C_{x,\beta_1,\dots,\beta_t}(l^*,\varepsilon^r,\varepsilon^c) = \text{Cum} \left( x, \prod_{ij \in \beta_1} \varepsilon_i^r \varepsilon_j^c \mathbf{1}_{\Omega_{\beta_1}(k^*,l^*)}, \dots, \prod_{ij \in \beta_t} \varepsilon_i^r \varepsilon_j^c \mathbf{1}_{\Omega_{\beta_t}(k^*,l^*)} \middle| l^* \right),$$

with $\Omega_{\beta}(k^*, l^*) := \{|\{(k_i^*, l_j^*) : (i,j) \in \beta\}| = 1\}$. For $C_{x,\beta_1,\dots,\beta_t}(l^*)$ to be non-zero, it is necessary that, for all $s \in [l]$, $\Omega_{\beta_s}(k^*, l^*)$ is an event of positive probability conditionally on $l^*$. This condition enforces that $|\{l_j^*\}_{j \in \text{col}(\beta_s)}| = 1$ for all $s$. We can assume that the latter property is true in the following. We write $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$, for $s \in [l]$, with $l_{j_s}^* = l_{j'_s}^*$. We also take the convention $i_0 = 1, i'_0 = 2$, and $j_0 = 0$. We then have

$$C_{x,\beta_1,\dots,\beta_t}(l^*,\varepsilon^r,\varepsilon^c) = \left( \prod_{s \in [l]} \prod_{ij \in \beta_s} \varepsilon_i^r \varepsilon_j^c \right) \text{Cum} \left( \mathbf{1}\{k_{i_s}^* = k_{i'_s}^*\}_{s \in [0,l]} \right),$$

which, in turn, implies

$$|C_{x,\beta_1,\dots,\beta_t}(l^*,\varepsilon^r,\varepsilon^c)| = \left| \text{Cum} \left( \mathbf{1}\{k_{i_s}^* = k_{i'_s}^*\}_{s \in [0,l]} \right) \right|.$$

From Lemma C.1, we deduce

$$|C_{x,\beta_1,\dots,\beta_t}(l^*,\varepsilon^r,\varepsilon^c)| \le |\alpha|^{|\alpha|} \left(\frac{1}{K}\right)^{\#\alpha-1},$$

which concludes the proof of the lemma.

<figure><img src="image_4.png" /></figure>

PROOF OF LEMMA E.2. 1. By symmetry, let us suppose that $1 \notin \text{supp}(\alpha)$. Then, conditionally on $l^*, \varepsilon^r, \varepsilon^c$, $x$ is independent from $(X_{ij})_{ij \in \alpha}$. We deduce from Lemma B.2 that $\kappa_{x,\alpha}(l^*, \varepsilon^r, \varepsilon^c) = 0$.

2. Let us suppose that there exists $\underline{i} \in \text{supp}(\alpha) \setminus \{1, 2\}$ with $|\alpha_{\underline{i}}| = 1$. Consider any decomposition $\alpha = \beta_1 + \dots + \beta_t$ with $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$. Let $s_0$ be the only element such that $\underline{i} \in \text{supp}(\beta_{s_0})$. It follows that $\mathbf{1}\{k_{i_{s_0}}^* = k_{i'_{s_0}}^*\}$ is independent of $(x, (\mathbf{1}\{k_{i_s}^* = k_{i'_s}^*\})_{s \in [l] \setminus \{s_0\}})$ and thus, from Lemma B.2, we deduce $C_{x,\beta_1,\dots,\beta_t}(l^*, \varepsilon^r, \varepsilon^c) = 0$. This being true for all decompositions of $\alpha$, we have $\kappa_{x,\alpha}(l^*, \varepsilon^r, \varepsilon^c) = 0$.

3. The last point of the lemma is a direct consequence of Theorem 2.5.

<figure><img src="image_5.png" /></figure>

PROOF OF LEMMA E.3. Since we necessarily have $1, 2 \in \text{supp}(\alpha)$, there are at most $n^{m-2}$ possibilities for choosing $\text{supp}(\alpha)$. Using the third point of Lemma E.2 together with the hypothesis $|\{j \in [p], l_j^* = l\}| \le 5^{\frac{p}{L}}$, for all $l \in [L]$, we deduce that the number of possibilities
for choosing $col(\alpha)$ is at most $(\frac{5p^2}{L})^{d/2}$. Finally, there are at most $m^d|col(\alpha)|^d \le d^{2d}$ possibilities for choosing $\alpha$ once $supp(\alpha)$ and $col(\alpha)$ is determined. This concludes the proof of the lemma. $\square$

**E.2. Proof of the first lower bound (41) of MMSE<sub>D</sub>.** Without loss of generality, we suppose through the proof that $\sigma^2 = 1$. Let us fix $D \in \mathbb{N}$ and let us suppose

$$ \zeta := \lambda^4 D^8 \max \left( n, p, \frac{np}{K^2}, \frac{np}{L^2} \right) < 1 . $$

As in the proof of Theorems 3.1 and 4.1, the expression of the MMSE<sub>D</sub> can be reduced to

$$ MMSE_{\le D} = \inf_{f \in \mathbb{R}_D[Y]} \mathbb{E} \left[ (f(Y) - x)^2 \right] = \frac{1}{K} - \text{corr}_{\le D}^2 , $$

with $x = \mathbf{1}_{k_1^*=k_2^*}$ and $corr_{\le D}^2$ being defined in Equation (10). We shall, as in the proofs of Theorem 3.1 and 4.1, upper-bound $corr_{\le D}^2$ using Proposition 2.1, which states that

$$ \text{corr}_{\le D}^2 \le \sum_{\substack{\alpha \in \mathbb{N}^{n \times p} \\ |\alpha| \le D}} \frac{\kappa_{x, \alpha}^2}{\alpha!} , $$

with $\kappa_{x,\alpha} = \text{Cum}(x, (X_{ij})_{ij \in \alpha})$, where we see $\alpha$ as a multiset of $[n] \times [p]$. The biclustering model is a special case of the latent model (1), with

$$ Z = k^*, l^*, \varepsilon^r, \varepsilon^c, \quad \delta_{ij}(k^*) = \varepsilon_i^r \varepsilon_j^c, \quad \text{and} \quad \theta_{i,j}(k^*) = (k_i^*, l_j^*) . $$

Combining Proposition 2.1 and Theorem 2.5, we need to upper-bound, for any multiset $\alpha$ and any decomposition $\beta_1 + \dots + \beta_l = \alpha$, with $|\beta_s| = 2$, the cumulant

$$ C_{x, \beta_1, \dots, \beta_l} = \text{Cum} \left( x, \prod_{ij \in \beta_1} \varepsilon_i^r \varepsilon_j^c \mathbf{1}_{\Omega_{\beta_1}(k^*, l^*)}, \dots, \prod_{ij \in \beta_l} \varepsilon_i^r \varepsilon_j^c \mathbf{1}_{\Omega_{\beta_l}(k^*, l^*)} \right) , $$

with $\Omega_\beta(k^*, l^*) := \{|\{(k_i^*, l_j^*) : (i, j) \in \beta\}| = 1\}$. Building on the recursive Bound (18), we derive in Section E.3 the following upper-bound.

**LEMMA E.4.** We recall that $\#\alpha$ stands for the cardinality of the points $i \in [1, n]$ such that $\alpha_i \ne 0$ and that $|\alpha| := \sum_{ij} \alpha_{ij}$. We have

$$ |C_{x, \beta_1, \dots, \beta_l}| \le |\alpha|^{\frac{|\alpha|}{2}} \frac{1}{K} \min \left( 1, \left( \frac{1}{K \wedge L} \right)^{\#\alpha + r_{\alpha} - \frac{|\alpha|}{2} - 2} \right) . $$

Combining this bound with (55) and counting the number of partitions $\pi \in \mathcal{P}_2(\alpha)$ for which $C_{x, \beta_1(\pi), \dots, \beta_l(\pi)} \ne 0$, we prove in Section E.8 the next upper-bound on $|\kappa_{x,\alpha}|$.
LEMMA E.5. Let $\alpha \in \mathbb{N}^{n \times p}$ non-zero. We have the upper bound

$$|\kappa_{x,\alpha}| \le \lambda^{|\alpha|} |\alpha|^{|\alpha|} \frac{1}{K} \min \left( 1, \left( \frac{1}{K \wedge L} \right)^{\#\alpha + r_{\alpha} - \frac{|\alpha|}{2} - 2} \right).$$

The last stage, is to prune the multisets $\alpha$ for which $\kappa_{x,\alpha} = 0$. Next lemma gives necessary conditions for having $\kappa_{x,\alpha} \neq 0$. We refer to Section E.9 for a proof of this lemma.

LEMMA E.6. Let $\alpha \in \mathbb{N}^{n \times p}$ be non-zero. If $\kappa_{x,\alpha} \neq 0$, then

* $1, 2 \in \text{supp}(\alpha)$;

* For all $i \in \text{supp}(\alpha)$, $|\alpha_i| \ge 2$;

* For all $j \in \text{col}(\alpha)$, $|\alpha_j| \ge 2$.

In particular, we have $\#\alpha \ge 2$, $|\alpha| \ge 2r_{\alpha}$ and $|\alpha| \ge 2\#\alpha$.

For any $r \ge 1$, $m \ge 2$ and $d \ge \max(2r, 2m)$, there are at most $p^r n^{m-2} d^{2d}$ matrices $\alpha$ satisfying the conditions of Lemma E.6 with $|\alpha| = d$, $r_{\alpha} = r$ and $\#\alpha = m$. Using Proposition 2.1, we have

$$\begin{aligned} \mathrm{corr}_{\le D}^2 &\le \sum_{\substack{\alpha \in \mathbb{N}^{n \times p} \\ |\alpha| \le D}} \kappa_{x, \alpha}^2 \\ &\le \frac{1}{K^2} + \frac{1}{K^2} \sum_{d=2}^D \sum_{m=2}^{d/2} \sum_{r=1}^{d/2} p^r n^{m-2} d^{4d} \lambda^{2d} \min \left( 1, \left( \frac{1}{K \wedge L} \right)^{2m+2r-d-4} \right). \end{aligned}$$

Let us fix $r \ge 1$, $m \ge 2$ and $d \ge \max(2r, 2m)$ and let us upper-bound $p^r n^{m-2} d^{4d} \lambda^{2d} \min \left( 1, \left( \frac{1}{K \wedge L} \right)^{2m+2r-d-4} \right)$. First, we suppose that $d \ge 2(m-2+r)$ and we get

$$\begin{aligned} p^r n^{m-2} d^{4d} \lambda^{2d} \min \left( 1, \left( \frac{1}{K \wedge L} \right)^{2m+2r-d-4} \right) &\le (D^4 \lambda^2)^d p^r n^{m-2} \\ &\le (D^4 \lambda^2)^{d-2r-2(m-2)} (D^8 \lambda^4 n)^{m-2} (D^8 \lambda^4 p)^r \\ &\le \sqrt{\zeta}^{d-2r-2(m-2)} \zeta^{m-2} \zeta^r = \zeta^{d/2} . \end{aligned}$$

Then, let us suppose that $d \le 2(m-2+r)$. By symmetry of the roles of $K$ and $L$, we suppose that $K \wedge L = K$. We get

$$\begin{aligned} p^r n^{m-2} d^{4d} \lambda^{2d} \min \left( 1, \left( \frac{1}{K \wedge L} \right)^{2m+2r-d-4} \right) &= p^r n^{m-2} (2d^4)^d \lambda^{2d} \min \left( 1, \left( \frac{1}{K} \right)^{2m+2r-d-4} \right) \\ &\le p^r n^{m-2} (D^4 \lambda^2)^d \left( \frac{1}{K} \right)^{2m+2r-d-4} \\ &\le n^{\frac{d}{2}-r} \left( \frac{n}{K^2} \right)^{m-2-\left(\frac{d}{2}-r\right)} p^r (D^4 \lambda^2)^{2r+2(d/2-r)} \end{aligned}$$
$$
\begin{align*}
&\le (D^8 \lambda^4 p)^r (D^8 \lambda^4 n)^{\frac{d}{2}-r} \left(\frac{n}{K^2}\right)^{m-2-(\frac{d}{2}-r)} \\
&\le (D^8 \lambda^4 n)^{\frac{d}{2}-r} (D^8 \lambda^4 p)^{\frac{d}{2}-(m-2)} \left(D^8 \lambda^4 p \frac{n}{K^2}\right)^{m-2-(\frac{d}{2}-r)} \\
&\le \sqrt{\zeta}^d .
\end{align*}
$$

In the end, we get

$$
\begin{align*}
corr_{\le D}^2 - \frac{1}{K^2} &\le \frac{1}{K^2} \sum_{d=2}^{D} \sum_{m=2}^{d/2} \sum_{r=1}^{d/2} \sqrt{\zeta}^d \\
&\le \frac{1}{K^2} \sum_{d=2}^{D} \frac{d(d-1)}{2} \sqrt{\zeta}^d \\
&\le \frac{1}{K^2} \frac{\zeta}{(1 - \sqrt{\zeta})^3},
\end{align*}
$$

which concludes the proof of the theorem.

**E.3.** *Proof of Lemma E.4.* Let $\alpha = \beta_1 + \dots + \beta_l$ with, for $s \in [l]$, $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$. Let us upper-bound the absolute value of the cumulant

$$
C_{x, \beta_1, \dots, \beta_l} = \text{Cum} \left( x, \left( \varepsilon_{i_s}^r \varepsilon_{i'_s}^r \varepsilon_{j_s}^c \varepsilon_{j'_s}^c \mathbf{1}_{\Omega_{\beta_s}}(k^*, l^*) \right)_{s \in [l]} \right).
$$

For $S \subseteq [l]$, we write $\beta[S] := \{\beta_s, s \in S\}$ and we write $\alpha_S = \sum_{s \in S} \beta_s$. In the following, we take the convention $i_0 = 1$, $i'_0 = 2$ and $j_0 = 0$. Applying the recursion formula 18, we have, for all $S \subseteq [l]$,

$$
\begin{align}
|C_{x,\beta[S]}| &\le \mathbb{P}[\forall s \in S \cup \{0\}, k_{i_s}^* = k_{i'_s}^*] \mathbb{P}[\forall s \in S, l_{j_s}^* = l_{j'_s}^*] + \nonumber \\
&\quad + \sum_{S' \subseteq S} |C_{x,\beta[S']}| \mathbb{P}[\forall s \in S \setminus S', k_{i_s}^* = k_{i'_s}^*] \mathbb{P}[\forall s \in S \setminus S', l_{j_s}^* = l_{j'_s}^*] \nonumber \\
&\le \left(\frac{1}{K}\right)^{|supp(\alpha_S) \cup \{1,2\}| - cc(V[S \cup \{0\}])} \left(\frac{1}{L}\right)^{r_{\alpha_S} - cc(N[S])} + \nonumber \\
&\quad + \sum_{S' \subseteq S} |C_{x,\beta[S']}| \left(\frac{1}{K}\right)^{\#\alpha_{S \setminus S'} - cc(V[S \setminus S'])} \left(\frac{1}{L}\right)^{r_{\alpha_{S \setminus S'}} - cc(N[S \setminus S'])}, \tag{74}
\end{align}
$$

where $V$ and $N$ are two graphs on $[0, l]$ defined as follows. For $s, s' \in [0, l]$, $V$ has an edge between $s$ and $s'$ if and only if $\{i_s, i'_s\} \cap \{i_{s'}, i'_{s'}\} \neq \emptyset$. For $s, s' \in [0, l]$, $N$ has an edge between $s$ and $s'$ if and only if $\{j_s, j'_s\} \cap \{j_{s'}, j'_{s'}\} \neq \emptyset$ (we consider $j_0 = j'_0 = 0$ which implies that $0$ is an isolated point of $N$). We also define the graph $W$ on $[0, l]$ with an edge between $s$ and $s'$ if and only if either $V$ or $N$ has an edge between $s$ and $s'$. Finally, given a subset $S \subset [0, l]$, we define $V(S)$, $N(S)$, and $W(S)$ as the subgraphs of $V$, $N$, and $W$ induced by $S$.
The next lemma prunes the subsets $S \subseteq [l]$ such that $C_{x,\beta[S]} \neq 0$. In the following, we denote $S([l])$ the collection of all subsets $S \subseteq [l]$ such that either $S = \emptyset$ or $W[\{0\} \cup S]$ is connected and both $1, 2 \in supp(\alpha_S)$. We postpone to Section E.4 the proof of the next lemma.

**LEMMA E.7.** Let $S \subseteq [l]$ such that $C_{x,\beta[S]} \neq 0$. Then $S \in S([l])$.

In particular, we can henceforth restrict our attention to subsets $S \in S([l])$, so that

$$ (75) \qquad \begin{aligned} |C_{x,\beta[S]}| &\le \left(\frac{1}{K}\right)^{\#\alpha_S - cc(V[S \cup \{0\}])} \left(\frac{1}{L}\right)^{r_{\alpha_S} - cc(N[S])} + \\ &\quad + \sum_{\substack{S' \subseteq S \\ S' \in S([l])}} |C_{x,\beta[S']}| \left(\frac{1}{K}\right)^{\#\alpha_{S \setminus S'} - cc(V[S \setminus S'])} \left(\frac{1}{L}\right)^{r_{\alpha_{S \setminus S'}} - cc(N[S \setminus S'])} . \end{aligned} $$

In the following, let us define recursively a function $f$ on $S([l])$ satisfying, for all $S \in S([l])$,

$$ (76) \qquad f(S) = 1 + \sum_{\substack{S' \subseteq S \\ S' \in S([l])}} f(S') . $$

In particular, $f(\emptyset) = 1$. Using the connectivity of $W[S \cup \{0\}]$ whenever $S \in S([l])$ is non-empty, we prove in Section D.3 the following lemma.

**LEMMA E.8.** For all $S \in S([l])$, we have $|C_{x,\beta[S]}| \le f(S) \left(\frac{1}{K}\right)^{\#\alpha_S - cc(V[S \cup \{0\}])} \left(\frac{1}{L}\right)^{r_{\alpha_S} - cc(V[S])}$.

The next lemma, proved in Section E.6, provides an upper-bound of $f([l])$.

**LEMMA E.9.** For all $S \in S([l])$, we have $f([l]) \le |\alpha|^{\frac{|\alpha_S|}{2}}$

Combining Lemma E.9 and Lemma E.8 implies that

$$ (77) \qquad |C_{x,\beta_1, \dots, \beta_l}| \le \left(|\alpha|\right)^{\frac{|\alpha|}{2}} \frac{1}{K} \left(\frac{1}{K \wedge L}\right)^{\#\alpha + r_{\alpha} - cc(V[[0,l]]) - cc(V[[l]]) - 1} . $$

It remains to lower-bound the quantity $\#\alpha + r_{\alpha} - cc(V[[0,l]]) - cc(V[[l]])$. To do so, we shall use the connectivity of the graph $W[0,l]$. We postpone to Section E.7 the proof of the next lemma.

**LEMMA E.10.** We have

$$ \#\alpha + r_{\alpha} - cc(V[[0,l]]) - cc(V[[l]]) - 1 \ge \max \left(0, \#\alpha + r_{\alpha} - \frac{|\alpha|}{2} - 2\right) . $$

Using Lemma E.10, we are able to conclude the proof of the lemma with

$$ |C_{x,\beta_1, \dots, \beta_l}| \le |\alpha|^{\frac{|\alpha|}{2}} \frac{1}{K} \min \left( 1, \left( \frac{1}{K \wedge L} \right)^{\#\alpha + r_{\alpha} - \frac{|\alpha|}{2} - 2} \right) . $$
**E.4.** *Proof of Lemma E.7.* Let $S \notin \mathcal{S}([l])$ and let us prove that $C_{x,\beta[S]} = 0$.

Let us first suppose that $\mathcal{W}[S \cup \{0\}]$ is not connected. Let $C_1, C_2$ be a partition of $S \cup \{0\}$ with no edges of $\mathcal{W}$ connecting them. Hence, the family of random variables $((\varepsilon_i^r, k_i^*)_{i \in \cup_{s \in C_1} \{i_s, i'_s\}}, (\varepsilon_j^c, l_j^*)_{j \in \cup_{s \in C_1} \{j_s, j'_s\}})$ is independent of the family $((\varepsilon_i^r, k_i^*)_{i \in \cup_{s \in C_2} \{i_s, i'_s\}}, (\varepsilon_j^c, l_j^*)_{j \in \cup_{s \in C_2} \{j_s, j'_s\}})$. Then, Lemma B.2 implies that $C_{x,\beta[S]} = 0$.

Let us now suppose that either $1 \notin \text{supp}(\alpha_S)$ either $2 \notin \text{supp}(\alpha_S)$. Then, $1_{k_1^*=k_2^*}$ is independent from $((\varepsilon_i^r, k_i^*)_{i \in \cup_{s \in S} \{i_s, i'_s\}}, (\varepsilon_j^c, l_j^*)_{j \in \cup_{s \in S} \{j_s, j'_s\}})$. Thus, from Lemma B.2, we deduce that $C_{x,\beta[S]} = 0$.

**E.5.** *Proof of Lemma E.8.* Let us prove by induction on $S \in \mathcal{S}([l])$ that

$$|C_{x,\beta[S]}| \le f(S) \left(\frac{1}{K}\right)^{\#\alpha_S - cc(\mathcal{V}[S \cup \{0\}])} \left(\frac{1}{L}\right)^{r_{\alpha_S} - cc(\mathcal{V}[S])}.$$

The initialization is straightforward since $f(\emptyset) = 1$ and $C_{x,\beta[\emptyset]} = \frac{1}{K}$. Consider a set $S \in \mathcal{S}([l])$ non-empty and let us suppose that the result holds for all $S' \in \mathcal{S}([l])$ with $S' \subsetneq S$. Combining (75) and the induction hypothesis leads to

$$\begin{aligned} |C_{x,\beta[S]}| & \le \left(\frac{1}{K}\right)^{\#\alpha_S - cc(\mathcal{V}[S \cup \{0\}])} \left(\frac{1}{L}\right)^{r_{\alpha_S} - cc(\mathcal{N}[S])} + \\ & \qquad + \sum_{\substack{S' \subsetneq S \\ S' \in \mathcal{S}([l])}} |C_{x,\beta[S']}| \left(\frac{1}{K}\right)^{\#\alpha_{S \setminus S'} - cc(\mathcal{V}[S \setminus S'])} \left(\frac{1}{L}\right)^{r_{\alpha_{S \setminus S'}} - cc(\mathcal{N}[S \setminus S'])} \\ & \le \left(\frac{1}{K}\right)^{\#\alpha_S - cc(\mathcal{V}[S \cup \{0\}])} \left(\frac{1}{L}\right)^{r_{\alpha_S} - cc(\mathcal{N}[S])} + \left(\frac{1}{K}\right) \left(\frac{1}{K}\right)^{\#\alpha_S - cc(\mathcal{V}[S])} \left(\frac{1}{L}\right)^{r_{\alpha_S} - cc(\mathcal{N}[S])} + \\ & \qquad + \sum_{\emptyset \ne S' \subsetneq S} f(S') \left(\frac{1}{K}\right)^{\#\alpha_{S'} + \#\alpha_{S \setminus S'} - cc(\mathcal{V}[S' \cup \{0\}]) - cc(\mathcal{V}[S \setminus S'])} \left(\frac{1}{L}\right)^{r_{\alpha_{S'}} + r_{\alpha_{S \setminus S'}} - cc(\mathcal{N}[S']) - cc(\mathcal{N}[S \setminus S'])} \end{aligned}$$

Let us deal with the term corresponding to $S' = \emptyset$. It is clear that $cc(\mathcal{V}[S]) \le cc(\mathcal{V}[S \cup \{0\}]) + 1$. Thus $(\frac{1}{K})(\frac{1}{K})^{\#\alpha_S - cc(\mathcal{V}[S])}(\frac{1}{L})^{r_{\alpha_S} - cc(\mathcal{N}[S])} \le (\frac{1}{K})^{\#\alpha_S - cc(\mathcal{V}[S \cup \{0\}])}(\frac{1}{L})^{r_{\alpha_S} - cc(\mathcal{N}[S])}$.

By the recursive definition of $f(S)$, it is sufficient to prove that, for all non empty $S' \subsetneq S$, we both have

$$\#\alpha_{S'} + \#\alpha_{S \setminus S'} - cc(\mathcal{V}[S' \cup \{0\}]) - cc(\mathcal{V}[S \setminus S']) \ge \#\alpha_S - cc(\mathcal{V}[S \cup \{0\}])$$

and

$$r_{\alpha_{S'}} + r_{\alpha_{S \setminus S'}} - cc(\mathcal{N}[S']) - cc(\mathcal{N}[S \setminus S']) \ge r_{\alpha_S} - cc(\mathcal{N}[S]) .$$

Let us prove only that $\#\alpha_{S'} + \#\alpha_{S \setminus S'} - cc(\mathcal{V}[S' \cup \{0\}]) - cc(\mathcal{V}[S \setminus S']) \ge \#\alpha_S - cc(\mathcal{V}[S \cup \{0\}])$, the proof being similar for the other term. Let $q = cc(\mathcal{V}[S \cup \{0\}])$ and let $cc_1, \dots, cc_q$ be the connected components of $\mathcal{V}[S \cup \{0\}]$. Let $q' \in [q]$ and let $h = cc(\mathcal{V}[(S' \cup \{0\}) \cap$
$cc_q') + cc(V[(S \ S') \cap cc_q])$. Let $a_1, \dots, a_h$ denote the collection of those connected components. Since the graph $V[cc_q]$ is connected, we can, up to a possible reordering of these connected components, suppose that, for all $h' \in [2, h]$, $\cup_{s \in a_{h'}} \{i_s, i'_s\}$ intersects $\cup_{h''<h'} \cup_{s \in a_{h''}} \{i_s, i'_s\}$. We deduce that

$$
\begin{align*}
\sum_{h' \in [h]} |\cup_{s \in a_{h'}} \{i_s, i'_s\}| &= |\cup_{s \in a_1} \{i_s, i'_s\}| + \sum_{h' \ge 2} |\cup_{s \in a_{h'}} \{i_s, i'_s\}| \\
&\ge |\cup_{s \in a_1} \{i_s, i'_s\}| + \sum_{h' \ge 2} (1 + |\cup_{s \in a_{h'}} \{i_s, i'_s\} \setminus (\cup_{h''<h'} \cup_{s \in a_{h''}} \{i_s, i'_s\})|) \\
&\ge |\cup_{s \in cc_{q'}} \{i_s, i'_s\}| + cc(V[S' \cap cc_{q'}]) + cc(V[(S \setminus S') \cap cc_{q'}]) - 1 .
\end{align*}
$$

Together with the fact that $\sum_{h' \in [h]} |\cup_{s \in a_{h'}} \{i_s, i'_s\}| = |\cup_{s \in (S' \cup \{0\}) \cap cc_{q'}} \{i_s, i'_s\}| + |\cup_{s \in (S' \setminus S) \cap cc_{q'}} \{i_s, i'_s\}|$, this leads us to

$$
\begin{align*}
|\cup_{s \in (S' \cup \{0\}) \cap cc_{q'}} \{i_s, i'_s\}| + |\cup_{s \in (S \setminus S') \cap cc_{q'}} \{i_s, i'_s\}| - cc(V[S' \cap cc_{q'}]) - cc(V[(S \setminus S') \cap cc_{q'}]) \\
\geq |\cup_{s \in cc_{q'}} \{i_s, i'_s\}| - 1 .
\end{align*}
$$

Summing other all $q' \in [q]$ leads us to

$$
\#\alpha_{S'} + \#\alpha_{S \setminus S'} - cc(V[S' \cup \{0\}]) - cc(V[S \setminus S']) \geq \#\alpha_S - cc(V[S \cup \{0\}]) .
$$

This concludes the proof of the lemma.

**E.6. Proof of Lemma E.9.** We proceed by induction to prove that, for all $S \in S([l])$, we have $f(S) \le |\alpha|^{\frac{|\alpha_S|}{2}}$. The initialization is trivial since $f(\emptyset) = 1$ and $\alpha_\emptyset = 0$. Let us take $S \in S([l])$ non empty and let us suppose that the result holds for all $S' \subsetneq S$. For all $s \in S$, let $S^*(s)$ the maximal element of $S([l])$ which is included in $S \setminus \{s\}$. The existence of such an element in provided from the fact that the set of elements $S' \in S([l])$ with $S' \subseteq S \setminus \{s\}$ is not empty (it contains $\emptyset$) and is stable by union. We have

$$
\begin{align*}
f(S) = 1 + \sum_{\substack{S' \subsetneq S \\ S' \in S([l])}} f(S') &\le 1 + \sum_{s \in S} \sum_{\substack{S' \subsetneq S^*(s) \\ S' \in S([l])}} f(S') \\
&\le 1 + \sum_{s \in S} [2f(S^*(s)) - 1] \\
&\le 2 \sum_{s \in S} f(S^*(s)).
\end{align*}
$$

Applying the induction hypothesis leads to

$$
f(S) \leq 2 \sum_{s \in S} |\alpha|^{\frac{|\alpha_{S^*(s)}|}{2}} .
$$

Since $S^*(s)$ does not contain $s$, it follows that $|\alpha_{S^*}| \le |\alpha_S| - 2$. We deduce that

$$
f(S) \le 2 \sum_{s \in S} |\alpha|^{\frac{|\alpha_S|}{2} - 1} = \frac{2|S|}{|\alpha|} |\alpha|^{\frac{|\alpha_S|}{2}} \le (|\alpha|)^{\frac{|\alpha_S|}{2}},
$$

where the last inequality comes from the fact that $|S| \le \frac{|\alpha|}{2}$. This concludes the induction and the proof of the lemma.
**E.7.** **Proof of Lemma E.10.** Recall that $\mathcal{V} = \mathcal{V}[[0, l]]$ and that $\mathcal{W} = \mathcal{W}[[0, l]]$. For short, we write $\mathcal{N}' = \mathcal{N}[[l]]$.

We know that $\{1, 2\} \subset \text{supp}(\alpha)$ and that they are in the same connected component of $\mathcal{V}$. Thus, it is clear that $\#\alpha + r_\alpha - cc(\mathcal{N}') - cc(\mathcal{V}) \ge 1$. It remains to prove that

$$ \#\alpha + r_{\alpha} - cc(\mathcal{N}') - cc(\mathcal{V}) \ge \#\alpha + r_{\alpha} - \frac{|\alpha|}{2} - 1, $$

which is equivalent to

$$ |\alpha| \ge 2 (cc(\mathcal{N}') + cc(\mathcal{V}) - 2) . $$

We shall use the fact that $\mathcal{W}$ is connected. We write $q = cc(\mathcal{N}')$. We write $J_1, \dots, J_q$ the partition of $\text{col}(\alpha)$ induced by the equivalence relation; $j$ and $j'$ are equivalent if and only if there exists $s, s'$ in the same connected component of $\mathcal{N}'$ such that $j \in \text{col}(\beta_s)$ and $j' \in \text{col}(\beta_{s'})$. For $R \subseteq [l]$, we write $q(R) \subseteq [q]$ the collection of $q'$ such that $\sum_{s \in R} \sum_{j \in J_{q'}} |(\beta_s):j| \ne 0$. In other words, $q(R)$ also corresponds to the collection of connected components of $\mathcal{N}'$ that intersect with $R$. Let us finally write $t = cc(\mathcal{V})$ and $cc_1, \dots, cc_t$ the connected components of $\mathcal{V}$.

The graph $\mathcal{W}$ corresponds to the superposition of $\mathcal{V}$ and of $\mathcal{N}'$. Connected components in $\mathcal{V}$ are connected by edges in $\mathcal{N}$.

Besides, recall that $\mathcal{W}$ is connected. Hence, we can assume, without loss of generality, that for all $t' \in [2, t]$, $q(cc_{t'} \setminus \{0\})$ intersects $\cup_{t'' \le t' - 1} q(cc_{t''} \setminus \{0\})$. For all $t' \in [t]$, it is clear that $|\alpha_{cc_{t'} \setminus \{0\}}| \ge 2|q(cc_{t'} \setminus \{0\})|$. Hence, we conclude that

$$ \begin{aligned} |\alpha| &\ge \sum_{t' \le t} |\alpha_{cc_{t'} \setminus \{0\}}| \ge \sum_{t' \le t} 2q(cc_{t'} \setminus \{0\}) \\ &\ge 2 \sum_{t' \le t} (1_{\{t' \ne 1\}} + |q(cc_{t'} \setminus \{0\}) \setminus \cup_{t'' \le t' - 1} q(cc_{t''} \setminus \{0\})|) \\ &\ge 2(t - 1) + 2|q([l])| = 2t + 2q - 1. \end{aligned} $$

This concludes the proof of the lemma.

**E.8.** **Proof of Lemma E.5.** In order to get a satisfying upper-bound of $|\kappa_{x,\alpha}|$ from Inequality Theorem 2.5 and Lemma E.4, it is sufficient to remark that $\mathcal{P}_2(\alpha)$ contains at most $|\alpha|^{\frac{|\alpha|}{2} - 1}$ elements.

Plugging this with Lemma E.4 in Theorem 2.5 leads to

$$ |\kappa_{x,\alpha}| \le |\alpha| \frac{1}{K} \min \left( 1, \left( \frac{1}{K \wedge L} \right)^{\#\alpha + r_{\alpha} - \frac{|\alpha|}{2} - 2} \right) . $$

which concludes the proof of the lemma.

**E.9.** **Proof of Lemma E.6.** Let $\alpha \in \mathbb{N}^{n \times p}$ non-zero. Let us prove that if $\alpha$ does not satisfy the three conditions of Lemma E.6, then $\kappa_{x,\alpha} = 0$.

First, we suppose that either 1 or 2 is not in $\text{supp}(\alpha)$. This implies that $x$ is independent from $(X_{ij})_{ij \in \alpha}$ and we deduce from Lemma B.2 that $\kappa_{x,\alpha} = 0$.
Let us suppose that there exists $i_0 \in \text{supp}(\alpha)$ with $|\alpha_{i_0}| = 1$. Since $\varepsilon_{i_0}^r$ has the same law as $-\varepsilon_{i_0}^r$ and is independent from all the other variables (in particular, changing $\varepsilon_{i_0}^r$ by $-\varepsilon_{i_0}^r$ does not change the law of $(x, X)$). So, by multilinearity of cumulants, we have $\kappa_{x,\alpha} = (-1)^{|\alpha_{i_0}|} \kappa_{x,\alpha} = -\kappa_{x,\alpha}$. We deduce directly that $\kappa_{x,\alpha} = 0$.

Similarly, if there exists $j_0$ such that $|\alpha|_{:j_0} = 1$, we use the fact that changing $\varepsilon_{j_0}^c$ to $-\varepsilon_{j_0}^c$ does not change the law of $(x, X)$ and we deduce $\kappa_{x,\alpha} = (-1)^{|\alpha_{:j_0}|} \kappa_{x,\alpha} = -\kappa_{x,\alpha}$ so that $\kappa_{x,\alpha} = 0$.

## APPENDIX F: PROOF OF COROLLARY 2.6

To get the Bound (19), we start from Möbius formula – see Lemma B.1 in Appendix B –

$$ 
\begin{aligned}
|C_{x,\beta_1, \dots, \beta_t}| &\le \sum_{\pi \in \mathcal{P}([l] \cup \{x\})} (|\pi| - 1)! \mathbb{E} \left[ |x|; \bigcap_{s \in \pi_1 \setminus \{x\}} \Omega_{\beta_s} \right] \prod_{k=2}^{|\pi|} \mathbb{P} \left[ \bigcap_{s \in \pi_k} \Omega_{\beta_s} \right] \\
&\le \max_{\pi \in \mathcal{P}([l] \cup \{x\})} \left\{ \mathbb{E} \left[ |x|; \bigcap_{s \in \pi_1 \setminus \{x\}} \Omega_{\beta_s} \right] \prod_{k=2}^{|\pi|} \mathbb{P} \left[ \bigcap_{s \in \pi_k} \Omega_{\beta_s} \right] \right\} \sum_{\pi \in \mathcal{P}([l] \cup \{x\})} (|\pi| - 1)! .
\end{aligned}
$$

Denoting by $\binom{l+1}{k}$ the Stirling number of the second kind, which counts the number of partitions $\pi \in \mathcal{P}([l] \cup \{x\})$ with $k$ non-empty sets, we get

$$ 
\begin{aligned}
\sum_{\pi \in \mathcal{P}([l] \cup \{x\})} (|\pi| - 1)! &= \sum_{k=1}^{l+1} \binom{l+1}{k} (k-1)! \\
&= l! + \binom{l+1}{l} (l-1)! + \sum_{k=1}^{l-1} \binom{l}{k} k! + \sum_{k=2}^{l-1} \binom{l}{k-1} (k-1)! \\
&= \sum_{k=1}^{l} \binom{l}{k} k! + \sum_{k=1}^{l-2} \binom{l}{k} k! + \binom{l+1}{l} (l-1)! \\
&= 2 \sum_{k=1}^{l} \binom{l}{k} k! = 2 f_l,
\end{aligned}
$$

where we used for the penultimate equality that

$$ \binom{l+1}{l} (l-1)! = \frac{(l+1)}{2} l! = \frac{(l-1)}{2} l! + l! = \binom{l}{l-1} (l-1)! + l! . $$

The bound on $f_l$ readily follows from the exponential generating function evaluated at $x = 1/2$

$$ \sum_{l \ge 1} \frac{f_l}{l!} \left(\frac{1}{2}\right)^l = \frac{1}{2 - \exp(1/2)} \le 3. $$

The proof of Corollary 2.6 is complete.

## APPENDIX G: PROOF OF THE UPPER BOUNDS

**G.1. Proof of Proposition 3.2.** Let us suppose without loss of generality that $\sigma^2 = 1$. We shall introduce two different procedures corresponding to the different regimes.

Both procedures proceed from the same general scheme:
1. We split the dataset randomly into two datasets $Y^{(1)}$ and $Y^{(2)}$;

2. We compute $\hat{v}_1, \dots, \hat{v}_K$ the leading eigenvectors of $(Y^{(1)})^T Y^{(1)}$ and we project orthogonally $Y^{(2)}$ onto $\hat{v}_1, \dots, \hat{v}_K$;

3. We apply a low-dimensional clustering procedure on the projected dataset $\hat{p}(Y^{(2)})$;

4. We perform Linear Discriminant Analysis in order to assign each point of $Y^{(1)}$ to one of the clusters of $\hat{p}(Y^{(2)})$.

Let $\delta_1, \dots, \delta_n$ i.i.d uniformly taken on $\{1, 2\}$. Let $I_1 = \{i \in [n], \delta_i = 1\}$ and $I_2 = \{i \in [n], \delta_i = 2\}$. Let $Y^{(1)} \in \mathbb{R}^{|I_1| \times p}$ be the data matrix restricted to $I_1$ and $Y^{(2)} \in \mathbb{R}^{|I_2| \times p}$ be the data matrix restricted to $I_2$. Let $\hat{v}_1, \dots, \hat{v}_K$ be the $K$ leading eigenvectors of $(Y^{(1)})^T Y^{(1)}$ and let $\hat{p}$ be the orthogonal projection on $\hat{v}_1, \dots, \hat{v}_K$. The following key lemma ensures that the projected centers are still well-separated.

We recall that, in this section, we assume that the partition $G^*$ is balanced in the following sense. For some constant $\gamma > 0$, we have

$$ \frac{\max_k |G_k^*|}{\min_k |G_k^*|} \le \gamma . $$

**LEMMA G.1.** We suppose $\max(K, \log(n)) \le p \le n$. There exists a constants $c_\gamma$ that only depends on $\gamma$ such that the following holds provided that $\Delta^4 \ge c_\gamma \frac{pK^2}{n}$. With probability at least $1 - \frac{4}{n^2}$, we have $\|\hat{p}(\mu_k) - \hat{p}(\mu_l)\|^2 \ge \frac{1}{4}\|\mu_k - \mu_l\|^2$ for all $k, l \in [1, K]$.

We organize the proof in the following way. In Section G.1.1, we apply [49] to the projected dataset $Y^{(2)}$ this allows to prove the second part Proposition 3.2 –see Proposition G.3 below. In Section G.1.2, we apply some hierarchical clustering procedure which will lead to the first part of Proposition 3.2 –see Proposition G.6. Finally, in Section G.1.3, we provide a proof of Lemma G.1.

Throughout the proof, we shall multiple times rely on the following lemma that ensures that the restrictions of $G^*$ to $I_1$ and $I_2$ are balanced.

**LEMMA G.2.** Suppose that $n \ge c\gamma^2 K^2$ with $c$ a numerical constant. Then, with probability higher than $1 - 1/n^2$, for all $k \in [K]$, we have $|G_k^* \cap I_1| \ge |G_k^*|/4$ and $|G_k^* \cap I_2| \ge |G_k^*|/4$.

In the following, we work conditionally on $I_1$ and $I_2$ and we assume, without loss of generality, that the event of Lemma G.2 holds.

**PROOF OF LEMMA G.2.** Let us fix $k \in [K]$ and let us consider $|G_k^* \cap I_1|$ which is a binomial of parameters $|G_k^*| \ge \frac{n}{K\gamma}$ and $\frac{1}{2}$. Using Hoeffding Inequality, we deduce that, for $t > 0$,

$$ \mathbb{P} \left[ \left| G_k^* \cap I_1 \right| - \frac{|G_k^*|}{2} \ge t \right] \le 2 \exp \left( \frac{-2t^2}{|G_k^*|} \right) . $$

Taking $t = \frac{|G_k^*|}{4}$, applying an union bound on all $k \in [K]$, yields that the desired result holds with probabilily higher than $1 - 2K \exp[-(\min_{k=1,...,K} |G_k^*|)/4]$ which is larger than $1 - 1/n$ as soon since $|G_k^*| \ge n/[K\gamma] \ge c^{1/2}\sqrt{n}$. $\square$
**Data:** $Y_1, \dots, Y_n$

Draw $(\delta_i)_{i \in [1, n]}$ independently and uniformly on $\{1, 2\}$;

Compute $\hat{v}_1, \dots, \hat{v}_K$ the leading eigenvectors of $(Y^{(1)})^T Y^{(1)}$, with $Y^{(1)}$ the restriction of $Y$ to $I_1$;

For $i \in I_2$, compute $\hat{p}(Y_i)$ the orthogonal projection of $Y_i$ on the space $\text{Vect}(\hat{v}_1, \dots, \hat{v}_K)$ (if $p \le \max(K, \log(n))$ keep $Y_i$);

Compute $\hat{G}$ the clustering of the projected dataset $\hat{p}(Y^{(2)})$ using the method from [49];

**for** $k \in [1, K]$ **do**

$$ \text{Compute } \hat{\mu}_k := \frac{1}{|\hat{G}_k|} \sum_{i \in \hat{G}_k} Y_i $$

**end**

**for** $i \in I_1$ **do**

$$ \text{Assign } i \text{ to the group } \hat{G}_k \text{ minimizing } \|Y_i - \hat{\mu}_k\|. $$

**end**

**Result:** The partition $\hat{G}$.

**Algorithm 1: Projection and iterative tensor projection**

G.1.1. *Tensor method of Li and Liu [49]*. In this section, we apply as a black-box the iterative tensor projection procedure of [49] to the projected dataset $\hat{p}(Y^{(2)})$. This polynomial-time method is described in Algorithm 1. In this subsection, we denote $\hat{G}$ the resulting estimator of the partition.

The following proposition states that $\hat{G}$ perfectly recover the unknown partition provided the separation $\Delta^2$ is large compared to $\log(n) + \sqrt{\frac{pK^2}{n}}$. This comes to the price of the condition that $n$ is at least polynomial in $K$.

**PROPOSITION G.3.** For any $\epsilon > 0$, there exist constants $c_\gamma, c'_{\gamma, \epsilon} > 0$, and $c_2 > 0$ such that the following holds. If $\Delta^2 \ge c_\gamma (\log(n)^{1+\epsilon} + \sqrt{\frac{pK^2}{n}})$ and $n \ge K^{c'_{\gamma, \epsilon}}$, the output $\hat{G}$ of Algorithm 1 satisfies

$$ \mathbb{P}[\hat{G} = G^*] \ge 1 - c_2/n^2 . $$

**PROOF OF PROPOSITION G.3.** This proof mostly builds upon Lemma G.1 and the work of [49]. Note that if $p \le \max(\log(n), K)$, one does not need to use the projection $\hat{p}$ and we can consider $\hat{p} = I_d$. In all cases, the dimension of the projected dataset is at most $\max(\log(n), K)$.

We work conditionally on $I_1$ and $I_2$. Without loss of generality, this event being of high probability when $n \ge c_\gamma K^2$, we suppose that $|I_1|, |I_2| \ge n/4$ and that for all $k \in [K]$, $|G_k^* \cap I_1|, |G_k^* \cap I_2| \ge \frac{|G_k^*|}{4}$ (Lemma G.2). Conditionally on $I_1$ and $I_2$, the dataset $Y^{(2)}$ is independent from $Y^{(1)}$ and thus $Y^{(2)}$ is independent from $\hat{p}$. We then deduce from Lemma G.1 that $\hat{p}(Y^{(2)})$ is a Gaussian mixture with $K$ groups of dimension at most $\max(\log(n), K)$ and, with high probability, with a separatition at least $\Delta/2$ between the groups. Then, we are in position to the results in Section 2.2 of [49] that we state here as a Proposition. In fact, the original theorem of Li and Liu is stated for a Gaussian mixture model where the the group of each observation is sampled at random, whereas we are considering here a setting where the partition $G^*$ is fixed in advance. Nevertheless, by closely inspecting the proof, one readily checks that their result extends to our setting.
**PROPOSITION G.4.** [49] Let $Z_1, \dots, Z_{n'} \in \mathbb{R}^{p'}$ being sampled from a mixture of Gaussian with an almost balanced partition $G'^*$ (i.e for all $k \in [K]$, $|G_k'^*| \ge \frac{n'}{\gamma 2K}$) of $[n']$ and centers $\mu'_1, \dots, \mu'_K \in \mathbb{R}^{p'}$. For all $\varepsilon > 0$, there exists positive constant $c_\gamma$, $c'_{\gamma,\varepsilon}$, and $c''$ such that the following holds. If $\min_{k \ne l} \|\mu'_k - \mu'_j\| \ge c' (\log(n))^{\frac{1}{2}+\varepsilon}$ and $n' \ge (p'K)^c$, there exists an algorithm $\hat{G}$ computable in polynomial time such that

$$ \mathbb{P}[\hat{G} = G] \ge 1 - 1/n^{c''}. $$

Suppose that $c_\gamma$ in the condition $\Delta^2 \ge c_\gamma[\log(n)^{1+\varepsilon} + \sqrt{\frac{pK^2}{n}}]$ of Proposition G.3 is large enough and that $c'_{\gamma,\varepsilon}$ such that $n \ge K^{c'_{\gamma,\varepsilon}}$ is also large enough, so that Proposition G.4 holds when applied to $\hat{p}(Y^{(2)})$. Then, we dispose of an partition $\hat{G}^{(2)}$ in $(I_2)$ computable in polynomial time which is equal to the restriction of $G^*$ to $I_2$ with high probability.

For $k \in [K]$, we write $\hat{\mu}_k^{\text{oracle}} = \frac{1}{|I_2 \cap G_k^*|} \sum_{i \in I_2 \cap G_k^*} Y_i$ and $\hat{\mu}_k^{(2)} = \frac{1}{|I_2 \cap \hat{G}_k^{(2)}|} \sum_{i \in I_2 \cap \hat{G}_k^{(2)}} Y_i$. The next Lemma characterizes a regime on which linear discriminant analysis with the centers $\hat{\mu}_k^{\text{oracle}}$ does perfect classification of $I_1$. We refer for example to Section 12.7.1 (page 271) of the textbook [34] for a proof of this lemma.

**LEMMA G.5.** [34] For $i \in I_1$, let us define $\hat{k}_i = \arg\min_{k \in [K]} \|Y_i - \hat{\mu}_k^{\text{oracle}}\|$, by breaking arbitrarily equality. There exist constants $c_\gamma$ and $c'$ such that if $\Delta^2 \ge c_\gamma (\log(n) + \sqrt{\frac{pK \log(n)}{n}})$, the following holds with probability at least $1 - \frac{c'}{n^2}$. For all $i \in I_1$, $\hat{k}_i = k_i^*$.

Then, on the high probability event on which Lemma G.5 holds and on which the clustering procedure from [49] onto the projected dataset $\hat{p}(Y^{(2)})$ recovers exactly the restriction of $G^*$ to $I_2$, Linear Discriminant Analysis with the centers $\mu_k^{(2)}$ also does perfect classification. We are then able to recover the entire partition $G^*$. This concludes the proof of the corollary.

<figure><img src="image_6.png" /></figure>

G.1.2. *Hierarchical Clustering.* In this Section, we apply a single linkage hierarchical clustering procedure on the dataset $\hat{p}(Y^{(2)})$. We consider the case where $p \ge \frac{n}{K}$. Let $\hat{G}$ be the projected hierarchical clustering procedure obtained from Algorithm 2. For any two disjoint sets $A, B$ we define the single linkage function $l(A, B) = \min_{i \in A, i' \in B} \|Y_i - Y_{i'}\|$.

The following proposition provides separation conditions under which Algorithm 2 perfectly recover the partition $G^*$ with high probability.

**PROPOSITION G.6.** There numerical constants $c$ and $c'$ and a positive constant $c_\gamma$ that only depends on $\gamma$ such that the following holds. Suppose $n \ge p \ge \frac{n}{K}$, $n \ge cK^2$, and

$$ \Delta^2 \ge c_\gamma \left( \log(n) + \sqrt{\frac{pK^2 \log(n)}{n}} \right). $$

Denoting $\hat{G}$ the output of Algorithm 2, we have $\mathbb{P}[\hat{G} = G^*] \ge 1 - c'/n^2$.

**PROOF OF PROPOSITION G.6.** If $p \le \max(\log(n), K)$, we have that $\hat{p}$ is the identity and we can therefore assume that $p \ge \max(\log(n), K)$.
**Data:** $Y_1, \dots, Y_n$

Draw $(\delta_i)_{i \in [1, n]}$ independently and uniformly on $\{1, 2\}$;

Compute $\hat{v}_1, \dots, \hat{v}_K$ the leading eigenvectors of $(Y^{(1)})^T Y^{(1)} - nI_p$, with $Y^{(1)}$ the restriction of $Y$ to $I_1$;

For $i \in I_2$, compute $\hat{p}(Y_i)$ the orthogonal projection of $Y_i$ on the space $\text{Vect}(\hat{v}_1, \dots, \hat{v}_K)$ (if $p \le \max(\log(n), K)$ keep $Y_i$);

$t \leftarrow 0;$

$G^{(0)} \leftarrow \{\{i\}_{i \in I_2}\};$

while $t < |I_2| - K$ do

Find $\hat{a}, \hat{b}$ minimizing $l(G_{\hat{a}}^{(t)}, G_{\hat{b}}^{(t)})$;

Build $G^{(t+1)}$ by merging the groups $G_{\hat{a}}^{(t)}$ and $G_{\hat{b}}^{(t)}$, the other groups remaining unchanged; $t \leftarrow t + 1$;

end

$\hat{G} := \hat{G}^{(t)}$;

for $k \in [1, K]$ do

Compute $\hat{\mu}_k := \frac{1}{|\hat{G}_k|} \sum_{i \in \hat{G}_k} X_i$

end

for $i \in I_1$ do

Assign $i$ to the group $\hat{G}_k$ minimizing $\|X_i - \hat{\mu}_k\|$.

end

**Result:** The partition $\hat{G}$.

**Algorithm 2:** Hierarchical Clustering algorithm with single linkage after splitting and projecting the dataset

Conditionally on $I_1$ and $I_2$, the dataset $Y^{(2)}$ is independent from $Y^{(1)}$ and thus $Y^{(2)}$ is independent from $\hat{p}$. We deduce from this that $\hat{p}(Y^{(2)})$ is a Gaussian mixture of dimension $\max(\log(n), K)$ which is well separated with high probability (Lemma G.1 provides a separation at least $\Delta^2/4$). With high probability, using Lemma G.2, we also have $|I_2| \ge n/4$ and for all $k \in [K] |I_2 \cap G_k^*| \ge \frac{n}{4K\gamma}$.

Hence, applying a Hierarchical procedure ensures that, if $\Delta^2 \ge c'' (\log(n) + \sqrt{K \log(n)})$ –see Proposition 4 in [28], then we recover exactly with high probability the restriction of the partition $G^*$ to $I_2$. We write the obtained partition $\hat{G}^{(2)}$. Note that the condition $\Delta^2 \ge c'' (\log(n) + \sqrt{K \log(n)})$ is ensured if the constant $c_\gamma$ in the statement of the proposition such that $\Delta^2 \ge c_\gamma[\log(n) + \sqrt{\frac{pK^2 \log(n)}{n}}]$ is large enough. Hence, $I_1$ is perfectly clustered. In turn, we deduce that $I_2$ is perfectly clustered by applying by arguing as in the previous proof. $\square$

The proof of Proposition G.6 also provides a result when we do not make any assumption on the dimension. We state this result as a proposition.

**PROPOSITION G.7.** There numerical constants $c$ and $c'$ and a positive constant $c_\gamma$ that only depends on $\gamma$ such that the following holds. Suppose $n \ge cK^2$, and

$$ \Delta^2 \ge c_\gamma \left( \log(n) + \sqrt{K \log(n)} + \sqrt{\frac{pK^2 \log(n)}{n}} \right). $$

Denoting $\hat{G}$ the output of Algorithm 2, we have $\mathbb{P}[\hat{G} = G^*] \ge 1 - c'/n^2$.
G.1.3. *Proof of Lemma G.1.* We work conditionally on $I_1$. To ease the notation, we write $Y = Y^{(1)}$ and $n' = |I_1|$. Without loss of generality, we restrict ourselves in the following to the event where $n' \ge n/4$ and for all $k \in [K]$, $|I_1 \cap G_k^*| \ge |G_k^*|/4 \ge \frac{n}{4\gamma K}$ (Lemma G.2). We remark that $\hat{v}_1, \dots, \hat{v}_K$ are also the $K$ leading eigenvectors of $Y^TY - n'I_p$. We seek to find an event of high probability on which

* the quantity $x^T(Y^TY - n'I_p)x$ is uniformly large for unit vectors such that $|\langle x, \frac{\mu_k - \mu_l}{\|\mu_k - \mu_l\|} \rangle|$ is large enough, for some $k \ne l$,

* the $(k+1)$-th eigenvalue $\hat{\lambda}_{k+1}$ of $Y^TY - n'I_p$ is small.

Such an event is provided by Lemma G.8 and G.9, respectively proven in Section G.1.3 and G.1.3.

LEMMA G.8. There exists a positive constant $c_\gamma$ that only depends on $\gamma$ such that, if $\Delta^4 \ge c_\gamma \frac{pK^2}{n}$, the following holds with probability at least $1 - \frac{2}{n^2}$. Simultaneously on all $x \in \mathbb{R}^p$ such that $\|x\| = 1$ and such that there exists $k \ne l$ with $|\langle x, \frac{\mu_k - \mu_l}{\|\mu_k - \mu_l\|} \rangle| \ge \frac{1}{2}$, we have

$$x^T (Y^T Y - n' I_p) x \ge \frac{n}{256 \gamma K} \Delta^2.$$

LEMMA G.9. There exists a positive constant $c_\gamma$ that only depends on $\gamma$ such that, if $\Delta^4 \ge c_\gamma \frac{pK^2}{n}$, the following holds with probability at least $1 - \frac{2}{n^2}$. Simultaneously on all $x \in \mathbb{R}^p$ such that $\|x\| = 1$ and such that $x \in (\mu_1, \dots, \mu_K)^\perp$, we have

$$x^T (Y^T Y - n' I_p) x \le \frac{n}{512 \gamma K} \Delta^2.$$

In the following, we suppose $\Delta^4 \ge c_1 \frac{pK^2}{n}$, with $c_1$ a numerical constant large enough such that Lemma G.8 and Lemma G.9 both hold. We restrict ourselves to the event of probability at least $1 - \frac{4}{n^2}$ defined as the union of the two events of Lemma G.8 and Lemma G.9.

Lemma G.9 implies that the $(k+1)$-th largest eigenvalue of $(Y^TY - n'I_p)$ satisfies $\hat{\lambda}_{k+1} \le \frac{n}{512\gamma K} \Delta^2$. Let $k \ne l$ and $y = \frac{\mu_k - \mu_l}{\|\mu_k - \mu_l\|}$. We decompose $y = \hat{p}(y) + (y - \hat{p}(y))$. Since $\langle y, y \rangle = 1$, then either $\langle y, \hat{p}(y) \rangle \ge \frac{1}{2}$, either $\langle y, (y - \hat{p}(y)) \rangle \ge \frac{1}{2}$.

Let us suppose that $\langle y, (y - \hat{p}(y)) \rangle \ge \frac{1}{2}$ and let us find a contradiction. Using Lemma G.8, we deduce that $(y - \hat{p}(y))^T (Y^TY - n'I_p) (y - \hat{p}(y)) \ge \frac{n}{256\gamma K} \Delta^2$. However, $y - \hat{p}(y)$ is the orthogonal projection of $y$ onto the space spread by the eigenvectors corresponding to the eigenvalues $\hat{\lambda}_{k+1}, \dots, \hat{\lambda}_p$. Thus, $(y - \hat{p}(y))^T (Y^TY - n'I_p) (y - \hat{p}(y)) \le \hat{\lambda}_{k+1} \le \frac{n}{512\gamma K} \Delta^2$, which leads to a contradiction.

Thus, $\langle y, \hat{p}(y) \rangle \ge \frac{1}{2}$. Hence, $\|\hat{p}(\mu_k) - \hat{p}(\mu_l)\|^2 = \|\mu_k - \mu_l\|^2 \|\hat{p}(y)\|^2 = \|\mu_k - \mu_l\|^2 \langle y, \hat{p}(y) \rangle^2 \ge \frac{\|\mu_k - \mu_l\|^2}{4}$. This concludes the proof of the lemma.

PROOF OF LEMMA G.8. In the proof of this lemma, we write $A \in \{0, 1\}^{n' \times K}$ for the assignment matrix defined by $A_{ik} = 1_{i \in G_k^*}$, $\mu \in \mathbb{R}^{K \times p}$ for the matrix of the means whose $k$-th
row is $\mu_k$, and $E \in \mathbb{R}^{n' \times p}$ the noise matrix $Y - E[Y]$ which is distributed as i.i.d. standard normal distributions.

Using the decomposition $Y = A\mu + E$, we have $x^T(Y^T Y - n'I_p)x = x^T(E^T E - n'I_p)x + 2x^T(A\mu)^T E x + x^T(A\mu)^T(A\mu)x$. The three following lemmas, proved in Sections G.1.3, G.1.3 and G.1.3, control each of these terms. Let us define the set of suitable unit vectors

$$ \mathcal{X} := \left\{ x \in \mathbb{R}^p : \|x\| = 1, \text{ and } \exists k \neq l \in [K] \text{ s.t. } \langle x, \frac{\mu_k - \mu_l}{\|\mu_k - \mu_l\|} \rangle \geq \frac{1}{2} \right\}. $$

LEMMA G.10. For any $x \in \mathcal{X}$, we have

$$ x^T(A\mu)^T(A\mu)x \geq \frac{n}{64\gamma K} \Delta^2 . $$

LEMMA G.11. With probability at least $1 - \frac{1}{n^2}$, simultaneously on all unit vectors $x \in \mathbb{R}^p$, we have

$$ |x^T (E E^T - n I_p) x| \leq 4 \sqrt{n'(6p + 4 \log(n))} + 48p + 32 \log(n) . $$

LEMMA G.12. With probability at least $1 - \frac{1}{n^2}$, simultaneously on all unit vectors $x \in \mathbb{R}^p$, we have

$$ |x^T(A\mu)^T E x| \leq \frac{1}{4} \|A\mu x\|^2 + 4 \left( \sqrt{K} + 7\sqrt{p+2\log(n)} \right)^2 . $$

Combining Lemmas G.10, G.11, and G.12, we deduce that, with probability at least $1 - \frac{2}{n^2}$, simultaneously on all $x \in \mathcal{X}$, we have

$$ \begin{align*} x^T (Y^T Y - n I_p) x &\geq \frac{1}{2} \|A\mu x\|^2 - 8 \left( \sqrt{K} + 7\sqrt{p+2\log(n)} \right)^2 \\ &\phantom{\geq} - 4\sqrt{n'(6p+4\log(n))} - 48p - 32\log(n) \\ &\geq \frac{n}{128\gamma K} \Delta^2 - 8 \left( \sqrt{K} + 7\sqrt{p+2\log(n)} \right)^2 \\ &\phantom{\geq} - 4\sqrt{n'(6p+4\log(n))} - 48p - 32\log(n) \\ &\geq \frac{n}{128\gamma K} \Delta^2 - c' \left( K + p + \sqrt{pn} + \sqrt{n\log(n)} \right), \end{align*} $$

with $c'$ a numerical constant. Let us now restrict ourself to the event of probability $1 - \frac{2}{n^2}$ on which, simultaneously on all $x \in \mathcal{X}$, the above inequality is true. We recall the hypothesis $n \geq p \geq \max(K, \log(n))$. Under this hypothesis, $(K + p + \sqrt{pn} + \sqrt{n\log(n)}) \leq 4\sqrt{pn}$. Thus, if the constant $c_\gamma$ such that $\Delta^4 \geq c_\gamma^{pK^2}$ is large enough, we conclude that.

$$ x^T (Y^T Y - n I_p) x \geq \frac{n}{256\gamma K} \Delta^2 . $$

It remains to prove Lemmas G.10, G.11, and G.12.

□
THE SIGNAL TERM: PROOF OF LEMMA G.10. Let us take a unit vector $x$ such that, for some $k \neq l$, we have $|\langle x, \frac{\mu_k - \mu_l}{\|\mu_k - \mu_l\|} \rangle| \geq \frac{1}{2}$. We write $y = \frac{\mu_k - \mu_l}{\|\mu_k - \mu_l\|}$ and we compute

$$x^T(A\mu)^T(A\mu)x = \sum_{k' \in [1,K]} \sum_{a \in G_{k'}^*} \langle \mu_{k'}, x \rangle^2 \geq \frac{n}{4K\gamma} (\langle x, \mu_k \rangle^2 + \langle x, \mu_l \rangle^2) .$$

Using the hypothesis $|\langle x, y \rangle| \geq \frac{1}{2}$, we deduce that $|\langle x, \mu_k - \mu_l \rangle| \geq \frac{\Delta}{2}$ and therefore $|\langle x, \mu_k \rangle| \geq \frac{\Delta}{4}$ or $|\langle x, \mu_l \rangle| \geq \frac{\Delta}{4}$. Hence, $x^T(A\mu)^T(A\mu)x \geq \frac{n}{64\gamma K}\Delta^2$. This concludes the proof of the lemma.

<figure><img src="image_7.png" /></figure>

PROOF OF LEMMA G.11. For any $x \in \mathbb{R}^p$ such that $\|x\| = 1$, we have

$$|x^T(E^T E - n' I_p)x| \leq \|E E^T - n' I_p\|_{op}.$$

We use the next lemma for upper-bounding this quantity. We refer for example to the textbook [34] (Lemma 12.10, page 273).

LEMMA G.13. There exists a random variable $\xi$ with exponential distribution of parameter 1 such that

$$\|E^T E - n' I_p\|_{op} \leq 4\sqrt{n'(6p + 2\xi)} + 48p + 16\xi.$$

Thus, with probability at least $1 - \frac{1}{n^2}$, we have

$$\|E^T E - n' I_p\|_{op} \leq 4\sqrt{n'(6p + 4\log(n))} + 48p + 32\log(n),$$

which concludes the proof of the lemma.

<figure><img src="image_8.png" /></figure>

PROOF OF LEMMA G.12. We denote $P$ the orthogonal projection onto the rows of $A\mu$. For any $x \in \mathbb{R}^p$ such that $\|x\| = 1$, we have

$$\begin{aligned}
|x^T(A\mu)^T E x| &= |\langle A\mu x, E x \rangle| = |\langle A\mu x, P E x \rangle| \\
&\leq \|A\mu x\| \|P E x\| \\
&\leq \|A\mu x\| \|P E\|_{op} \\
&\leq \frac{1}{4} \|A\mu x\|^2 + 4 \|P E\|_{op}^2 .
\end{aligned}$$

The next lemma, which is just proved below, provides an upper-bound of the quantity $\|PE\|_{op}$.

LEMMA G.14. With probability at least $1 - \frac{1}{n^2}$, we have

$$\|PE\|_{op} \leq (\sqrt{K} + 7\sqrt{p + 2\log(n)}) .$$

Lemma G.14 implies that, with probability at least $1 - \frac{1}{n^2}$, simultaneously on all $x \in \mathbb{R}^p$ with $\|x\| = 1$, we have

$$x^T(A\mu)^T E x \leq \frac{1}{4} \|A\mu x\|^2 + 4 (\sqrt{K} + 7\sqrt{K + 2\log(n)})^2 .$$

<figure><img src="image_9.png" /></figure>
PROOF OF LEMMA G.14. This lemma is stated as an exercise in [34] (exercise 12.9.6, page 288). Let $r \le K$ denote the rank of $A\mu$. We define $u_1, \dots, u_r$ an orthogonal basis of the space spanned by the rows of $A\mu$. Let $U = (u_1, \dots, u_r)$. Then $P = UU^T$. For any unit norm vector $x \in \mathbb{R}^p$, we have

$$
\begin{align*}
x^T (PE)^T (PE) x &= x^T E^T P^2 E x \\
&= x^T E^T P E x \\
&= x^T E^T U U^T E x \\
&= x^T (U^T E)^T (U^T E) x .
\end{align*}
$$

Thus, $\|PE\|_{op} = \|U^T E\|_{op}$. Moreover, the columns of $U^T E$ are independent with law $N(0, I_r)$. Let us now take again some $x \in \mathbb{R}^p$ with $\|x\| = 1$. We denote $W = U^T E$ and get

$$
\begin{align*}
\|Wx\|^2 &= x^T W^T W x = x^T (W^T W - K I_n) x + K \\
&\le K + \|W^T W - K I_n\|_{op} .
\end{align*}
$$

Thus, we have $\|W\|_{op}^2 \le K + \|W^T W - K I_p\|_{op}$. Applying Lemma G.13, we deduce the existence of an exponential random variable $\xi'$ such that $|W|_{op}^2 \le (\sqrt{K} + 7\sqrt{p+\xi'})^2$. Hence, with probability $1 - \frac{1}{n^4}$, we have

$$
\|W\|_{op} \le \sqrt{K} + 7\sqrt{p + 2\log(n)},
$$

which concludes the proof of the lemma.

<figure><img src="image_10.png" /></figure>

PROOF OF LEMMA G.9. Let $x \in (\mu_1, \dots, \mu_K)^T$ be a unit vector. We have $A\mu x = 0$. Thus, we have $x^T (Y^T Y - n' I_p) x = x^T (E^T E - n' I_p) x$. In turn, we have

$$
x^T (Y^T Y - n' I_p) x \le \|E E^T - n' I_p\|_{op} .
$$

By Lemma G.13, we have that, with probability at least $1 - \frac{1}{n^2}$,

$$
\|E^T E - n' I_p\|_{op} \le 4\sqrt{n'(6p + 4\log(n))} + 48p + 32\log(n) .
$$

Thus, with probability at least $1 - \frac{1}{n^2}$, uniformly on all unitary $x$,

$$
x^T (Y^T Y - n' I_p) x \le 4\sqrt{n'(6p + 4\log(n))} + 48p + 32\log(n),
$$

Recall $n \ge p \ge \log(n)$. If the constant $c_\gamma$ such that $\Delta^4 \ge c_\gamma \frac{pK^2}{n}$ is large enough, we have that, with the same high probability, uniformly on all such unit vectors $x$,

$$
x^T (Y^T Y - n' I_p) x \le \frac{n}{512 \gamma K} \Delta^2,
$$

which concludes the proof of the lemma.

<figure><img src="image_11.png" /></figure>
**G.2. Proof of Proposition 4.3.** Without loss of generality, we suppose that $\sigma^2 = 1$. Let $E' \in \mathbb{R}^{n \times p}$ with i.i.d $\mathcal{N}(0, \frac{1}{2})$ entries. Then $Y^{(1)} = (Y + E')/\sqrt{2}$ and $Y^{(2)} = (Y - E')/\sqrt{2}$ are two independent datasets such that, when $i \in G_k^*$, we both have $Y_i^{(1)} \sim \mathcal{N}(\mu_k/\sqrt{2}, I_p)$ and $Y_i^{(2)} \sim \mathcal{N}(\mu_k/\sqrt{2}, I_p)$. Our strategy follows the two steps;

1. Use the first dataset $Y^{(1)}$ in order to estimate the set $J^*$ of active columns;

2. Use a clustering procedure to the second dataset, keeping only columns estimated in the first step.

For the first step, we consider $\hat{J}$ collecting the $s$ columns of $Y^{(1)}$ with the largest euclidean norm. We recall the definition

$$w_{J^*} := \min_{j \in J^*} \sum_{i \in [n]} X_{ij}^2 .$$

Next lemma states that, if $w_{J^*}$ is large enough, then $\hat{J}$ contains $J^*$ with high probability.

**LEMMA G.15.** There exists a numerical constant $c_1 > 0$ such that the following holds. If

$$(78) \qquad w_{J^*}^2 := \min_{j \in J^*} \sum_{i \in [n]} X_{ij}^2 \ge c_1 \left( \sqrt{n \log(pn)} + \log(p) \right),$$

then, with probability higher than $1 - \frac{1}{n^2}$, $\hat{J}$ contains $J^*$.

Let us then work conditionally on $\hat{J}$ and let us suppose that $\hat{J}$ indeed contains $J^*$. Let $Y_j^{(2)}$ the restriction of $Y^{(2)}$ to the columns $j \in \hat{J}$. Since $Y^{(2)}$ is independent from $\hat{J}$, we deduce that $Y_j^{(2)}$ is a Gaussian Mixture with a separation $\Delta^2/2$ in dimension $s$. We can conclude the proof using Proposition 3.2. We deduce that, except when $s \in [\text{Poly-log}(n), n/K]$ and $n \in [K^2, K^c]$, with $c$ some numerical constant, if

$$\Delta^2 \ge 1 + \min \left( \sqrt{s}, \sqrt{\frac{sK^2}{n}} \right),$$

then it is possible to recover exactly $G^*$ with high probability and with an algorithm computable in polynomial time.

**PROOF OF LEMMA G.15.** In order to prove that $\hat{J}$ contains $J^*$ with high probability, it is sufficient to prove that, with high probability, for all $j \in J^*$ and for all $j' \in [p] \setminus J^*$, we have $\|Y_{:j}^{(1)}\|^2 > \|Y_{:j'}^{(1)}\|^2$. We decompose the matrix $Y^{(1)} = X/\sqrt{2} + E$ with $E$ a gaussian matrix. For $j \in [p]$, we have

$$\|Y_{:j}^{(1)}\|^2 = \frac{\|X_{:j}\|^2}{2} + \|E_{:j}\|^2 + \sqrt{2}\langle X_{:j}, E_{:j} \rangle .$$

Using Hanson-Wright inequality inequality for Gaussian variables (e.g. Lemma 1 [46]) and the tail of a gaussian random variable, we deduce that, with probability higher than $1 - \frac{1}{n^2}$, uniformly on all $j \in [p]$, we have

$$(79) \qquad \left| \|Y_{:j}^{(1)}\|^2 - n - \frac{1}{2} \|X_{:j}\|^2 \right| \le c' \left( \sqrt{n(\log(pn))} + \|X_{:j}\|\sqrt{\log(pn)} + \log(pn) \right),$$
for some $c' > 0$. On this same event of high probability, we have that, for $j \in [p]$ for which $X_{:,j} = 0$,

$$ \|Y_{:,j}^{(1)}\|^2 \le n + c' \left( \sqrt{n(\log(pn))} + \log(pn) \right). $$

In light of (79), if we take the constant $c_1$ large enough in (78), we conclude that $\min_{j \in J^*} \|Y_{:,j}\|^2 > \max_{j \notin J^*} \|Y_{:,j'}\|^2$, which concludes the proof of the lemma.

<figure><img src="image_12.png" /></figure>

**G.3. Proof of Proposition 4.6.** We suppose without loss of generality that $\sigma^2 = 1$. Let $E' \in \mathbb{R}^{n \times p}$ with i.i.d $\mathcal{N}(0, 1)$ entries. Then $Y^{(1)} = (Y + E')/\sqrt{2}$ and $Y^{(2)} = (Y - E')/\sqrt{2}$ are two independent datasets such that, when $i \in G_k^*$, we both have $Y_i^{(1)} \sim \mathcal{N}(\mu_k/\sqrt{2}, I_p)$ and $Y_i^{(1)} \sim \mathcal{N}(\mu_k/\sqrt{2}, I_p)$.

For any partition $G$ of $[n]$ into $K$ groups, we denote $B^G$ the associated normalized partnership matrix defined by

$$ B_{ij}^G = \sum_{k \in [K]} \frac{1}{|G_k|} \mathbf{1}\{i \in G_k\} \mathbf{1}\{j \in G_k\} . $$

The application $G \to B^G$ is a bijection from the set of all partitions into $K$ groups to the set of matrices (Lemma 12.3 of [34] page 262)

$$ \mathcal{B} = \{ B \in S_n(\mathbb{R})^+ : B_{ij} \ge 0, \mathrm{Tr}(B) = K, B1 = 1, B^2 = B \} . $$

To alleviate the notation, we write $B^*$ for $B^{G*}$.

For any such normalized partnership matrix $B \in \mathcal{B}$ with associated partition $G$, we define $\hat{J}(B)$ as the subset of the $s$ indices $j \in [p]$ that maximizes the square $l_2$ norm

$$ \sum_{k \in [K]} \left( \sum_{a \in G_k} Y_{aj}^{(1)} \right)^2 . $$

Then, for $B \in \mathcal{B}$ and $J \subseteq [p]$, we define the criterion on $Y^{(2)}$.

$$ \mathrm{Crit}(B, J)(Y^{(2)}) = \langle Y_J^{(2)}(Y_J^{(2)})^T - |J|I_n, B \rangle . $$

Take any two distinct $B, B' \in \mathcal{B}$. We define the partial ordering relation $\prec$ by $B \prec B'$ if

$$ (80) \qquad \mathrm{Crit}(B, \hat{J}(B) \cup \hat{J}(B'))(Y^{(2)}) \le \mathrm{Crit}(B', \hat{J}(B) \cup \hat{J}(B'))(Y^{(2)}). $$

Finally, we define $\hat{B}$ and the associated partition $\hat{G}$ as any maximal $B$ with respect to this ordering.

In fact, we will show that, provided that $\Delta^2$ and $w_{J^*}$ are large enough, we have, with high probability, $B \prec B^*$ for all $B \in \mathcal{B}$, which in turn implies that $\hat{G} = G^*$.

Let us shortly discuss the definition of our estimator. Given $B, \hat{J}(B)$ selects the columns with empirical largest norms, ie those which are most likely to contain the informative columns. Then, $B \prec B'$ corresponds to the fact that the Kmeans criterion restricted to the columns in $\hat{J}(B) \cup \hat{J}(B')$ is smaller for $B'$ than for $B$-see e.g. [62] for the connection between Kmeans criterion and Crit. Here, we use a simple sample splitting scheme to avoid technicalities in the simultaneous control of the $\hat{J}(B)$'s and of the Kmeans criterion.
The proofs proceeds with two main steps. First, by Lemma 4.2, $\hat{J}(B^*)$ contains $J^*$ with high probability as long as $w_{J^*}$ is large enough.

Then, we work conditionally on the event of Lemma 4.2. The property $J^* \subseteq \hat{J}(B^*)$ implies that, for any $B \in \mathcal{B}$, $Y_{\hat{J}(B) \cup \hat{J}(B^*)}^{(2)}$ is a gaussian mixture of dimension at most $2s$ with a separation $\Delta^2/2$. The next lemma, which builds upon previous analyses of the exact Kmeans criterion [28], states $B^*$ is a global maximum of the restricted Kmeans criterion provided the separation is large enough.

**LEMMA G.16.** Assume that $\Delta^2 \ge c\gamma^{5/2} \left[ \sqrt{\frac{sK}{n}[\log(n)]} + \log(n) \right]$ where $c$ is a large enough numerical constant and assume that $J \subseteq \hat{J}(B^*)$. With probability at least $1 - \frac{2}{n^2}$, we have

$$ \text{Crit}(B, \hat{J}(B) \cup \hat{J}(B^*)) (Y^{(2)}) < \text{Crit}(B, \hat{J}(B^*) \cup \hat{J}(B^*)) (Y^{(2)}), \\ \text{simultaneously for all } B \in \mathcal{B}. $$

Combining Lemmas 4.2 and Lemma G.16 leads to the desired result.

**G.3.1.** *Proof of Lemma 4.2.* In this proof, we write $Y$ instead of $Y^{(1)}$ for simplicity of notation. In order to prove that $J^* \subseteq \hat{J}(B^*)$ with high probability, we prove that, with high probability, uniformly on all $j \in J^*$ and $j' \notin J^*$,

$$ \sum_{k \in [K]} \left( \sum_{a \in G_k^*} Y_{aj} \right)^2 \ge \sum_{k \in [K]} \left( \sum_{a \in G_k^*} Y_{aj'} \right)^2 . $$

For any $j \in [p]$, we have that

$$ \begin{aligned} \sum_{k \in [K]} \left( \sum_{a \in G_k^*} Y_{aj} \right)^2 &= \sum_{k \in [K]} \left( |G_k^*| (\mu_k)_j + \sum_{a \in G_k^*} E_{aj} \right)^2 \\ &= \sum_{k \in [K]} |G_k^*|^2 (\mu_k)_j^2 + \sum_{k \in [K]} \left( \sum_{a \in G_k^*} E_{aj} \right)^2 + 2 \sum_{k \in [K]} (\mu_k)_j \left( \sum_{a \in G_k^*} E_{aj} \right) . \end{aligned} $$

*The quadratic noise term.* $\sum_{k \in [K]} (\sum_{a \in G_k^*} E_{aj})^2 = E_{:j}^T S E_{:j}$ with $S$ the $n \times n$ matrix defined by $S_{ij} = \sum_k \mathbf{1}\{i, j \in G_k^*\}$. Thus, using Hanson-Wright Lemma (see Appendix B.6 of [34] for example), we deduce that, with probability at least $1 - \frac{1}{n^2}$, uniformly on all $j \in [p]$, we have,

$$ \left| \sum_{k \in [K]} \left( \sum_{a \in G_k^*} E_{aj} \right)^2 - \sum_{k \in [K]} |G_k^*| \right| \le c \sqrt{\sum_{k \in [K]} |G_k^*|^2 (\log(n) + \log(p))} + c \max_{k \in [K]} |G_k^*| (\log(n) + \log(p)) \\ \le c' \gamma \left( \sqrt{\frac{n^2}{K}(\log(n) + \log(p))} + \frac{n}{K}(\log(n) + \log(p)) \right), $$

for some numerical constants $c$ and $c'$.
The cross-product term. The random variable $2\sum_{k\in[K]}(\mu_k)_j(\sum_{a\in G_k^*}E_{aj})$ is normally distributed with variance $4\sum_{k\in[K]}|G_k^*|(\mu_k)_j^2$. So, with probability at least $1 - \frac{1}{n^2}$, for all $j\in[p]$, and for some numerical constant $c$,

$$2 \left| \sum_{k \in [K]} (\mu_k)_j \left( \sum_{a \in G_k^*} E_{aj} \right) \right| \le c \sqrt{\sum_{k \in [K]} |G_k^*| (\mu_k)_j^2 (\log(n) + \log(p))} ,$$

for some constant $c > 0$.

Let us restrict ourselves to an event of high probability on which those two deviation hold. If $j \notin J^*$, then, for some $c > 0$, we have

$$\begin{align*}
\sum_{k \in [K]} \left( \sum_{a \in G_k} Y_{aj} \right)^2 - \sum_{k \in [K]} |G_k^*| &\le c \gamma \left( \sqrt{\frac{n^2}{K} (\log(n) + \log(p))} + \frac{n}{K} (\log(n) + \log(p)) \right) \\
&\le c \gamma \frac{n}{K} (\log(np) + \sqrt{K \log(np)}) \\
&\le c \gamma^2 \min_k |G_k^*| (\log(np) + \sqrt{K \log(np)}) \\
&\le \frac{1}{8} \min_k |G_k^*| w_{J^*}^2
\end{align*}$$

provided the constant $c_1$ such that $w_{J^*}^2 \ge c_1 \gamma^2 (\sqrt{K \log(np)} + \log(np))$ is large enough.

Let us turn to the case where $j \in J^*$. Provided that the numerical constant $c_1$ in the condition $w_{J^*}^2 \ge c_1 \gamma^2 (\sqrt{K (\log(np))} + \log(np))$ is large enough, we have

$$\begin{align*}
\sum_{k \in [K]} \left( \sum_{a \in G_k} Y_{aj} \right)^2 - \sum_{k \in [K]} |G_k^*| &\ge \min |G_k^*| \sum_{k \in [K]} |G_k^*| (\mu_k)_j^2 - c \sqrt{\sum_{k \in [K]} |G_k^*| (\mu_k)_j^2 \log(np)} - \min |G_k^*| \frac{1}{8} w_{J^*}^2 \\
&\ge \frac{1}{2} \min |G_k^*| w_{J^*} .
\end{align*}$$

This concludes the proof of the lemma.

### G.3.2. Proof of Lemma G.16.
In this section, for the sake of simplicity, we write $Y$ instead of $Y^{(2)}$ and for any $B \in \mathcal{B}$, we write $Y_B$ the restriction of $Y$ to the columns in $\hat{J}(B^*) \cup \hat{J}(B)$. We recall that we work conditionally on $(\hat{J}(B))_{B \in \mathcal{B}}$ and that we suppose $J \subseteq \hat{J}(B^*)$. We denote $s_B = |\hat{J}(B^*) \cup \hat{J}(B)| \le 2s$.

For $B \in \mathcal{B}$, we decompose the observations as

$$Y_B = X_B + E_B,$$

where $(X_B)_{ij} = \mu_{kj}$ if $i \in G_k^*$ and for $j \in \hat{J}(B^*) \cup \hat{J}(B)$, and $E_B \in \mathbb{R}^{n \times s_B}$ is the restriction of $Y - \mathbb{E}[Y]$ to the columns $\hat{J}(B^*) \cup \hat{J}(B)$. Let us decompose the difference of the criterions.

$$\begin{align*}
\mathrm{Crit}(B^*, \hat{J}(B^*) \cup \hat{J}(B))(Y) - \mathrm{Crit}(B, \hat{J}(B^*) \cup \hat{J}(B))(Y) \\
&= \langle Y_B Y_B^T - s_B I_n, B^* - B \rangle \\
&= \langle X_B X_B^T, B^* - B \rangle + \langle E_B E_B^T - s_B I_n, B^* - B \rangle + 2 \langle X_B (E_B)^T, B^* - B \rangle = S(B) + N(B) + C(B) .
\end{align*}$$
As mentioned earlier in the proof, this corresponds to the difference of a Kmeans criterion [62], which has been thoroughly studied in [28].

In the remainder of this proof, we write $||A||_1$ for its entry-wise $l_1$ norm. Using directly Lemma 4 from [35], we deduce that the signal term satisfies

$$ (81) \qquad S(B) = \langle X_B X_B^T, B^* - B \rangle \geq \frac{1}{4} \Delta^2 \delta_B, $$

with $\delta_B = ||B^* - B^*B||_1$. It remains to upper-bound the quadratic noise term $\langle E_B E_B^T - s_B I_n, B^* - B \rangle$ and the crossed term $\langle X_B(E_B)^T, B^* - B \rangle$ with respect to $\delta_B$. The next two lemmas provide a uniform control of these two terms.

**LEMMA G.17.** There exists a numerical constant $c_1$ such that the following holds. With probability at least $1 - \frac{1}{n^2}$, we have

$$ |N(B)| \leq c_1[\delta_B \vee 1] \left[ \sqrt{\frac{\gamma s K}{n} [\log(n) + \gamma^2]} + \log(n) + \gamma^2 \right], $$

simultaneously over all $B \in \mathcal{B}$.

**LEMMA G.18.** There exists a numerical constant $c_2$ such that the following holds. With probability at least $1 - \frac{1}{n^2}$, we have

$$ |C(B)| \leq c_2 \sqrt{S(B)(\delta_B \vee 1)(\log(n) + \gamma^2)}, $$

simultaneously for all $B \in \mathcal{B}$.

We consider henceforth that we are under the event of probability higher than $1 - 2/n^2$ where the deviation bounds in Lemma G.17 and G.18 hold. Then, for any $B \in \mathcal{B} \setminus \{B^*\}$, we have

$$ \begin{aligned} S(B) - |N(B)| - |C(B)| &\geq \frac{S(B)}{2} - (c_1 + 2c_2)[\delta_B \vee 1] \left[ \sqrt{\frac{\gamma s K}{n} [\log(n) + \gamma^2]} + \log(n) + \gamma \right] \\ &\geq \delta_B \frac{\Delta^2}{8} - (c_1 + 2c_2)[\delta_B \vee 1] \left[ \sqrt{\frac{\gamma s K}{n} [\log(n) + \gamma^2]} + \log(n) + \gamma \right]. \end{aligned} $$

Besides, we know from Lemma 9 in [28] that $\delta_B \geq m/(m) \geq 1/\gamma$ if $B \neq B^*$. Hence, $[\delta_B \vee 1] \leq \gamma \delta_B$. We deduce that

$$ S(B) - |N(B)| - |C(B)| \geq \delta_B \frac{\Delta^2}{8} - (c_1 + 2c_2)\gamma \delta_B \left[ \sqrt{\frac{\gamma s K}{n} [\log(n) + \gamma]} + \log(n) + \gamma \right], $$

This last quantity is positive provided that the constant $c$ in the condition

$$ \Delta^2 \geq c\gamma^{5/2} \left[ \sqrt{\frac{sK}{n} [\log(n)]} + \log(n) \right] $$

is large enough.

We have proved that $S(B) - |N(B)| - |C(B)| > 0$ for all $B \neq B^*$ which, in light of the definition of $S(B) + N(B) + C(B)$, leads to the desired result.
PROOF OF LEMMA G.17. Let us denote $m = \min_{k \in [K]} |G_k^*| \ge \frac{n}{K\gamma}$. For a fixed $B$, $N(B) = \langle E_B E_B^T - s_B I_n, B^* - B \rangle$ is a quadratic form of Gaussian random variables. Thus, we are in position to apply Hanson-Wright inequality for Gaussian variables–see e.g. Lemma 1 in [46]. For a fixed $B \in \mathcal{B}$, with probability higher than $1 - 2e^{-x}$, we have

$$ (82) \qquad |N(B)| \le c \left( \sqrt{s_B x \|B^* - B\|_F^2} + x \|B^* - B\|_{op} \right), $$

where $c$ is a numerical constant. The next Lemma control $\|B^* - B\|_F$ and $\|B^* - B\|_{op}$.

LEMMA G.19. For all $B$, we have $\|B - B^*\|_F \le 6\sqrt{\frac{\delta_B}{m}}$ and $\|B - B^*\|_{op} \le 2$.

We remark that the quantity $\delta_B$ is upper-bounded by $2n$. We use a peeling-type argument/For $j \in [2n]$, we denote

$$ \mathcal{B}_j := \{B \in \mathcal{B}, \delta_B \in (j-1, j]\} . $$

We shall apply the definition inequality (82) together with an union bound over $\mathcal{B}_j$, this for all $j = 1, \dots, 2n$. The following lemma is a direct consequence of Lemma 17 in [28].

LEMMA G.20. There exists a positive numerical constant $c$ such that, for any $j = 1, \dots, 2n$, we have

$$ \log [|\mathcal{B}_j|] \le c_j \left[ \log(n) + \frac{m^+}{m} \right], $$

where $m^+ = \max |G_k^*|$.

By definition, we have $m^+/m \le \gamma$. By Lemma G.20, we deduce that $\log(\mathcal{B}_j) \le c_j[\log(n) + \gamma]$ for some constant $c > 0$.

Putting everything together we conclude that, with probability at least $1 - 1/n^2$, we have

$$ |N(B)| \le c[\delta_B \vee 1] \left[ \sqrt{\frac{\gamma s K}{n} [\log(n) + \gamma]} + \log(n) + \gamma \right]. $$

<figure><img src="image_13.png" /></figure>

PROOF OF LEMMA G.19. The proof is based on standard linear algebra and follows from the computations in [35] and [28]. Since $B$ and $B^*$ are projector, we have $\|B - B^*\|_{op} \le 2$. Besides, we have

$$ B - B^* = (I - B^*)(B - B^*)(I - B^*) + B^*(B - B^*) + (B - B^*)B^* + B^*(B - B^*)B^* $$

Since $B^*$ is a projector, we have $\|B^*(B - B^*)B^*\|_F \le \|(B - B^*)B^*\|_F$. It follows that

$$ (83) \qquad \|B - B^*\|_F \le \|(I - B^*)(B - B^*)(I - B^*)\|_F + 3\|(B - B^*)B^*\|_F, $$

In the proof of Lemma 13 in [28], it is shown that

$$ \|(I - B^*)(B - B^*)(I - B^*)\|_F \le \sqrt{\frac{\delta_B}{m}} $$

Besides, it is shown in proof of Lemma 15 in [28], that

$$ \|(B - B^*)B^*\|_F \le \sqrt{2\frac{\delta_B}{m}}. $$

The result follows.

<figure><img src="image_14.png" /></figure>
PROOF OF LEMMA G.18. Observe that the random variable $C(B)$ is distributed as a Gaussian random variables whose variance is given by

$$4 \|(B^* - B)X_B\|_F^2 = \mathrm{tr}[X_B^T X_B - X_B^T B X_B] = 4S(B),$$

since $B^2 = B$ and $B^*X_B = X_B$. Then, we apply an union bound over all $\mathcal{B}_j$'s and all $\mathcal{B}_{c,j'}$. Together with Lemma G.20, this allows us to conclude that, with probability higher than $1 - 1/n^2$, we have

$$C(B) \le c \sqrt{S(B)[\delta_B] \left(\log(n) + \frac{m^+}{m}\right)},$$

simultaneously for all $B \in \mathcal{B}$. Since $m_+/m \le \gamma$, the result follows.

□

**G.4. Proof of Proposition 5.2.** As in the proof of Proposition 4.6, we express the exact Kmeans criterion in terms of partnership matrices.

Given a partition $G$, we define $B_r^G$ s the corresponding partnership matrix, that is $B_r \in \mathbb{R}^{n \times n}$ is such that $(B_r)_{ij} = 0$ if $i$ and $j$ are not in the same group, whereas $(B_r)_{i,j}$ is equal to 1 over the size of group that contains $i$ and $j$ otherwise. For short, we write $B_r^*$ for $B_r^*$. Also, $\mathcal{B}_r$ for the collection of all possible partnership matrices of size $n$ with $K$ groups.

Simarly, we define partnership matrice $B_c^H \in \mathbb{R}^{p \times p}$ associated to a partition $H$, the collection $\mathcal{B}_c$ of all such partnership matrices, whereas we denote $B_c^*$ for $B_c^*$. Finally, given the bi-Kmeans estimator $(\hat{G}, \hat{H})$ from (46), we write $\hat{B}_c$ and $\hat{B}_r$ for $\hat{B}_c^G$ and $\hat{B}_r^H$.

We will often use that any $B_r \in \mathcal{B}_c$ (resp. $B_c \in \mathcal{B}_c$) is a projection matrix and that its trace is equal to $K$ (resp. $L$).

Partnership matrices are handy representations for analyzing Kmeans criteria [62, 35]. Indeed, equipped with this notation, the bi-Kmeans estimator (46) can be reformulated as

$$(84) \qquad (\hat{B}_r, \hat{B}_c) = \arg \max_{B_r \in \mathcal{B}_r, B_c \in \mathcal{B}_c} \mathrm{Tr} [Y^T B_r Y B_c].$$

PROOF OF (84). Developing the criterion inside (46), we have that

$$(\hat{G}, \hat{H}) \in \underset{G,H}{\operatorname{argmax}} \sum_{k \in [K]} \sum_{i \in G_k} 2Y_{ij} \bar{Y}_{kl}^{G \times H} - (\bar{Y}_{kl}^{G \times H})^2.$$

Then, we observe

$$\sum_{\substack{i \in G_k \\ j \in H_l}} 2Y_{ij} \bar{Y}_{kl}^{G \times H} - (\bar{Y}_{kl}^{G \times H}) = \sum_{\substack{k \in [K] \\ l \in [L]}} |G_k| |H_l| (\bar{Y}_{kl}^{G \times H})^2 = \|B_r Y B_c\|_F^2 = \mathrm{Tr}[Y^T B_r Y B_c],$$

since $B_r$ and $B_c$ are orthogonal projectors.

□

In the following proposition, we write $m_r = \min_{a=k,...,K} |G_k^*|$ and $m_r^+ = \max_{k=1,...,K} |G_k^*|$, the respective size of the smallest group and of the largest group of the true partition of the rows. We similarly define $m_c$ and $m_c^+$. By assumption, we have $\max(m_r^+/m_r, m_c^+/m_c) \le \gamma$.
Throughout the proof of the proposition, we write $X = \mathbb{E}[Y]$ the signal matrix and $E = Y - X$ the noise matrix, whose entries are i.i.d $\mathcal{N}(0, \sigma^2)$. We suppose without loss of generality that $\sigma^2 = 1$. As for Proposition 4.6, this proof heavily builds upon the analysis of the exact Kmeans criterion in [28]. By definition of our estimator, we have

$$ \mathrm{Tr}[Y^T B_r Y B_c] \geq \mathrm{Tr}[Y^T B_r^* Y B_c^*] $$

The latter inequality implies that

$$ (85) \qquad S(\hat{B}_r, \hat{B}_c) \leq N(\hat{B}_r, \hat{B}_c) + C(\hat{B}_r, \hat{B}_c) $$

where

$$ (86) \qquad S(B_r, B_c) := \mathrm{Tr}[X^T B_r^* X B_c^*] - \mathrm{Tr}[X^T B_r X B_c] ; $$

$$ (87) \qquad N(B_r, B_c) := \mathrm{Tr}[E^T B_r E B_c] - \mathrm{Tr}[E^T B_r^* E B_c^*] ; $$

$$ (88) \qquad C(B_r, B_c) := 2\mathrm{Tr}[X^T B_r E B_c] - 2\mathrm{Tr}[X^T B_r^* E B_c^*] . $$

Here, $S(B_r, B_c)$ is a deterministic signal term that only depends on $X$, whereas $N(B_r, B_c)$ is a pure noise term that only depends on $E$. For $B_r \in \mathcal{B}_r$, we write $\delta_{B_r} = \|B_r^* - B_r^* B_r\|_1$. Similarly, for $B_c \in \mathcal{B}_c$, we write $\delta_{B_c} = \|B_c^* - B_c^* B_c\|_1$.

**LEMMA G.21.** For any $B_r$ and $B_c$, we have

$$ S(B_r, B_c) \geq \left[ \delta_{B_c} \frac{\Delta_c^2}{4} \right] \vee \left[ \delta_{B_r} \frac{\Delta_r^2}{4} \right] . $$

**LEMMA G.22.** There exists numerical constants $c, c'$ such that, with probability higher than $1 - c'/(n \vee p)^2$, we have

$$ N(B_c, B_r) \leq c \frac{m_r^+}{m_r} \delta_{B_r} \left[ \sqrt{\frac{p}{m_r m_c} \left[ \log(n \vee p) + \frac{m_r^+}{m_r} + \frac{m_c^+}{m_c} \right]} \right] \\ + c \frac{m_c^+}{m_c} \delta_{B_c} \left[ \sqrt{\frac{n}{m_r m_c} \left[ \log(n \vee p) + \frac{m_r^+}{m_r} + \frac{m_c^+}{m_c} \right]} \right] \\ + c \left[ \frac{m_r^+}{m_r} \delta_{B_r} + \frac{m_c^+}{m_c} \delta_{B_c} \right] \left[ \log(n \vee p) + \frac{m_r^+}{m_r} + \frac{m_c^+}{m_c} \right], $$

simultaneously over all $B_r$ and $B_c$.

**LEMMA G.23.** There exists numerical constants $c, c'$ such that, with probability higher than $1 - c'/(n \vee p)^2$, we have

$$ C(B_c, B_r) \leq c \sqrt{S(B_r, B_c) \left[ \delta_{B_r} \frac{m_r^+}{m_r} \left( \log(n \vee p) + \frac{m_r^+}{m_r} \right) + \delta_{B_c} \frac{m_c^+}{m_c} \left( \log(n \vee p) + \frac{m_c^+}{m_c} \right) \right]} . $$

simultaneously over all $B_r$ and $B_c$.

We now use that $m_r^+ / m_r \leq \gamma$ and $m_c^+ / m_c \leq \gamma$. By combining the two previous lemmas, we deduce that, for some numerical constants $c, c'$, with probability at least $1 - c'/(n \vee p)^2$, we have
$$ N(B_c, B_r) + C(B_c, B_r) \le \frac{S(B_r, B_r)}{2} + c\gamma^{5/2}\delta_{B_r} \left[ \sqrt{\frac{KL \log(n \lor p)}{n}} + \log(n \lor p) \right] \\ + c\gamma^{5/2}\delta_{B_c} \left[ \sqrt{\frac{KL \log(n \lor p)}{p}} + \log(n \lor p) \right]. $$

Let us specify this inequality to $\hat{B}_c$ and $\hat{B}_r$. Coming back to (85) and using the lower bound of $S(\hat{B}_c, \hat{B}_r)$ from Lemma G.21, we observe that, necessarily we have $\hat{B}_c = B_c^*$ and $\hat{B}_r = B_r^*$. It remains to prove the lemmas.

PROOF OF LEMMA G.21. By Linearity, we have

$$ S(B_r, B_c) = S(B_r^*, B_c) + \mathrm{Tr} [X^T(B_r^* - B_r)XB_c] = S(B_r^*, B_c) + \mathrm{Tr} [(XB_c)(XB_c)^T(B_r^* - B_r)], $$

since $B_c$ is a projector. Observe that the rows of $XB_c$ are identical on each group of the true partition of the rows. Hence, it follows from Lemma 4 in [35] that $\mathrm{Tr}[(XB_c)(XB_c)^T(B_r^* - B_r)] \ge 0$ for any $B_r \in \mathcal{B}_r$. Hence, we have $S(B_r, B_c) \ge S(B_r^*, B_c)$. Then, we deduce again from Lemma 4 in [35], that

$$ S(B_r^*, B_c) \ge \frac{\Delta_c^2}{4} \delta_{B_c}. $$

The result of the lemma then follows by reversing the role of $B_c$ and $B_r$.

<figure><img src="image_15.png" /></figure>

PROOF OF LEMMA G.22. We first decompose $N(B_r, B_l)$ into a sum of three terms $N(B) = N_1(B_c) + N_2(B_r) + N_3(B_r, B_c)$ where

$$ N_1(B_c) = \mathrm{Tr} [E^T B_r^* E(B_c - B_c^*)] $$

$$ N_2(B_r) = \mathrm{Tr} [E^T (B_r - B_r^*) E B_c^*] $$

$$ N_3(B_r, B_c) = \mathrm{Tr} [E^T (B_r - B_r^*) E(B_c - B_c^*)]. $$

Since $B_r^*$ is a rank K projector, observe that $N_1(B_c)$ corresponds to the pure noise term in the analysis of a Kmeans criterion for a Gaussian mixture model in dimension K with p observations and L groups. Thus, we could apply Lemma 11 in [28] to control it. Similarly, $N_2(B_r)$ corresponds to the pure noise term in the analysis of a Kmeans criterion for a Gaussian mixture model in dimension L with n observations and K groups. Still, as the term $N_3(B_r, B_c)$ is slightly more involved, we provide a dedicated proof.

For the simultaneous control of these three quantities, we will apply Hanson-Wright inequality together with a dedicated peeling argument. For any integer $j \in [1, 2n]$, (resp. $j \in [1, 2p]$), we define $\mathcal{B}_{r,j} = \{B \in \mathcal{B}_r : \delta_{B_c} \in (j-1, j]\}$ (resp. $\mathcal{B}_{c,j} = \{B_c \in \mathcal{B}_c : \delta_{B_c} \in (j-1, j]\}$). Since $\delta_{B_r}$ is always smaller than $2n$, this give us a partition of $\mathcal{B}_r \setminus \{B_r^*\}$. We shall apply Hanson-Wright inequality together with an union bound to each of these sets.

For this purpose, we need to control the Frobenius and operator norm of $B_r - B_r^*$ and of $B_c - B_c^*$. Adapting Lemma G.19 to our setting lead us to
LEMMA G.24. For all $B_r$ and $B_c$, we have

$$ (89) \qquad \|B_r - B_r^*\|_F \le 6 \sqrt{\frac{\delta_{B_r}}{m_r}} $$

$$ (90) \qquad \|B_c - B_c^*\|_F \le 6 \sqrt{\frac{\delta_{B_c}}{m_c}} $$

$$ (91) \qquad \|B_r - B_r^*\|_{op} \le 2 \text{ and } \|B_c - B_c^*\|_{op} \le 2. $$

The following lemma is a straightforward adaptation of Lemma G.20.

LEMMA G.25. There exists a positive numerical constant $c$ such that

$$ \log [|B_{r,j}|] \le cj \left[ \log(n) + \frac{m_r^+}{m_r} \right], $$

for any $j = 1, \dots, 2n$. A similar result holds for $B_{c,j}$.

Now, we are in position to apply Hanson-Wright inequality for Gaussian variables (e.g. Lemma 1 [46]) to all $B_r$ belonging to $B_{r,j}$, this for all $j = 1, \dots, 2n$. For a fixed $B_r$, the random variable $N_2(B_r)$ is of form $U^T H U$ where $U$ is a standard Gaussian vector of dimension $nK$, and $H$ is a symmetric matrix satisfying $\mathrm{tr}[H] = 0$, $\|H\|_F \le 6\sqrt{K\frac{\delta_{B_r}}{m_r}}$ and $\|H\|_{op} \le 2$. We deduce, that with probability higher than $1/(n \vee p)^2$, we have

$$ N_2(B_r) \le c[\delta_{B_r} \vee 1] \left[ \sqrt{\frac{K}{m_r}[\log(n \vee p) + \frac{m_r^+}{m_r}]} + \log(n \vee p) + \frac{m_r^+}{m_r} \right]. $$

for any $B_r \ne B_r^*$. A similar bound holds for $N_1(B_c)$. For $N_3(B_c, B_r)$, we apply Hanson-Wright inequality to all $B_r$ and $B_c$ belonging to $B_{c,j}$ and $B_{r,j'}$. The random variable $N_3(B_c, B_r)$ is of form $U^T H U$ where $U$ is a standard Gaussian vector of dimension $np$, and $H$ is a symmetric matrix defined by; for $(i, j) \in [n] \times [p]$ and $(i', j') \in [n] \times [p]$, we have $H_{(i,j),(i',j')} = (B_r - B_r^*)_{ii'} (B_c - B_c^*)_{jj'}$. This matrix satisfies $\mathrm{tr}[H] = 0$, $\|H\|_F \le 36\sqrt{\frac{\delta_{B_r} \delta_{B_c}}{m_c m_r}}$ and $\|H\|_{op} \le 4$. We deduce, that with probability higher than $1/(n \vee p)^2$, we have

$$ N_3(B_c, B_r) \le c \left[ \sqrt{\frac{\delta_{B_r} \delta_{B_c} [\delta_{B_r} + \delta_{B_c} + 1]}{m_r m_c}} \left[ \log(n \vee p) + \frac{m_r^+}{m_r} + \frac{m_c^+}{m_c} \right] \right. \\ \left. + c[\delta_{B_r} + \delta_{B_c} + 1] \left[ \log(n \vee p) + \frac{m_r^+}{m_r} + \frac{m_c^+}{m_c} \right], \right] $$

as long as $B_c \ne B_c^*$ and $B_r \ne B_r^*$. Recall that $\delta_{B_r} \le 2n$ and $\delta_{B_c} \le 2p$. Besides, we know from Lemma 9 in [28] that $\delta_{B_r} \ge m_r/(m_r^+)$ if $B_r \ne B_r^*$ and $\delta_{B_c} \ge m_c/(m_c^+)$ if $B_c \ne B_c^*$. This leads to

$$ N_3(B_c, B_r) \le c \frac{m_r^+}{m_r} \delta_{B_r} \left[ \sqrt{\frac{p}{m_r m_c} \left[ \log(n \vee p) + \frac{m_r^+}{m_r} + \frac{m_c^+}{m_c} \right]} \right. \\ \left. + c \frac{m_c^+}{m_c} \delta_{B_c} \left[ \sqrt{\frac{n}{m_r m_c} \left[ \log(n \vee p) + \frac{m_r^+}{m_r} + \frac{m_c^+}{m_c} \right]} \right] \right] $$
$$+c \left[ \frac{m_r^+}{m_r} \delta_{B_r} + \frac{m_c^+}{m_c} \delta_{B_c} \right] \left[ \log(n \lor p) + \frac{m_r^+}{m_r} + \frac{m_c^+}{m_c} \right]. \quad \square$$

PROOF OF LEMMA G.23. For a fixed $B$, $C(B)$ is distributed a Gaussian random variable whose variance is given by

$$4 \|B_r X B_c - B_r^* X B_c^*\|_F^2 = 4 \mathrm{Tr} [X^T X - X^T B_r X B_c] = 4 S(B_r, B_c),$$

since $X = B_r^* X B_c^*$. Then, we apply an union bound over all $B_{r,j}$'s and all $B_{c,j'}$. Together with Lemma G.25, this allows us to conclude that, with probability higher than $1 - c'/(n \lor p)^2$, we have

$$C(B_c, B_r) \le c \sqrt{S(B_r, B_c) \left[ \left[ \delta_{B_r} \right] \left( \log(n \lor p) + \frac{m_r^+}{m_r} \right) + \left[ \delta_{B_c} \right] \left( \log(n \lor p) + \frac{m_c^+}{m_c} \right) \right]}.$$

<figure><img src="image_16.png" /></figure>

## APPENDIX H: PROOFS FOR TECHNICAL DISCUSSIONS

PROOF OF LEMMA A.1. It is a consequence of the following lemma whose proof is given below.

LEMMA H.1. There exists a subset $\bar{J} \subseteq J^*$ and a subset $K' \subset [K]$ with $|K'| \ge \frac{9K}{10}$ satisfying:

1. For all $j \in \bar{J}$, $\sum_{k \in [K]} |G_k^*| (\mu_k)_j^2 \ge \frac{n \Delta^2 \sigma^2}{80 s \gamma}$;

2. For all $k \ne l \in K'$, $\|(\mu_k)_{\bar{J}} - (\mu_l)_{\bar{J}}\|^2 \ge \frac{1}{2} \Delta^2 \sigma^2$.

Assume that there exist $k \in K'$ and $l \in [K]$ such that $\|(\mu_k)_{\bar{J}} - (\mu_l)_{\bar{J}}\|^2 < \frac{1}{8} \Delta^2 \sigma^2$. By Lemma H.1, we deduce that for the all $k' \in K' \setminus \{k\}$, we have $\|(\mu_{k'})_{\bar{J}} - (\mu_l)_{\bar{J}}\|^2 \ge \frac{1}{8} \Delta^2 \sigma^2$. As a consequence, there exist at most $K/10$ elements $k \in K'$ such that there exists $l \in [K]$ with $\|(\mu_k)_{\bar{J}} - (\mu_l)_{\bar{J}}\|^2 < \frac{1}{8} \Delta^2 \sigma^2$. Defining $K$ by removing all these elements from $K$, we arrive at the desired conclusion. $\square$

PROOF OF LEMMA H.1. We define $\bar{J}$ the set of all $j$ such that $\sum_{k \in [K]} |G_k^*| (\mu_k)_j^2 \ge \frac{n \Delta^2 \sigma^2}{80 s \gamma}$. Since the signal is supported on $J^*$ which is of size at most $s$, we deduce that $\sum_{j \notin \bar{J}} \sum_{k \in [K]} |G_k^*| (\mu_k)_j^2 \le \frac{n \Delta^2 \sigma^2}{80 \gamma}$. Let $K^-$ the set of all $k \in [K]$ with $\|(\mu_k)_{J^* \setminus \bar{J}}\|^2_2 \ge \frac{\Delta^2 \sigma^2}{8}$. We have

$$|K^-| \frac{n \Delta^2 \sigma^2}{8} \le \frac{n \Delta^2 \sigma^2}{80 \gamma},$$

which, in turn, implies that $|K^-| \le \frac{K}{10}$.

We set $K' = [K] \setminus K^-$ which is of size at least $\frac{9K}{10}$. For $k, l \in K'$, we have

$$\|(\mu_k)_{\bar{J}} - (\mu_l)_{\bar{J}}\|^2 \ge \left( \|\mu_k - \mu_l\| - 2 \frac{\Delta \sigma}{\sqrt{8}} \right)^2 \ge \left( \frac{\sqrt{2}}{2} \Delta \sigma \right)^2 \ge \frac{1}{2} \Delta^2 \sigma^2.$$

<figure><img src="image_17.png" /></figure>
PROOF OF LEMMA 4.4. Suppose that $X$ satisfies Assumption 2 for some $\eta \ge 1$. Since $\min_{k \ne l} \frac{\|\mu_k - \mu_l\|^2}{2\sigma^2} \ge \Delta^2$, we deduce that at least all except one of the $\mu_k$'s satisfy $\|\mu_k\|^2 \ge \frac{1}{2}\Delta^2\sigma^2$. We deduce that

$$ \sum_{j \in J^*} \|X_{:j}\|^2 \ge (K-1) \min_{k \in [K]} |G_k^*| \frac{1}{2} \Delta^2 \sigma^2 \ge \frac{n(K-1)}{2K\gamma} \Delta^2 \sigma^2 . $$

On the other hand,

$$ \sum_{j \in J^*} \|X_{:j}\|^2 \le s \max_{j \in J^*} \|X_{:j}\|^2 \le s\eta w_{J^*}^2 \sigma^2 . $$

We conclude the proof of the lemma with

$$ w_{J^*}^2 \ge \frac{n(K-1)}{2sK\gamma\eta} \Delta^2 . \quad \square $$

PROOF OF LEMMA A.2. We have

$$ \begin{aligned} n(n-1) MMSE_{poly} &= \mathbb{E}[\|M^*\|_F^2] - \sup_{\hat{M} \text{ poly-time, } \mathbb{E}[\|\hat{M}\|_F^2]=1} \mathbb{E}[\langle M^*, \hat{M} \rangle_F]^2 \\ &=: \mathbb{E}[\|M^*\|_F^2] - \text{corr}^2 = \frac{n^2}{K}(1+o(1)) - \text{corr}^2. \end{aligned} $$

In particular $\text{corr}^2 = o(n^2/K)$. Since

$$ \sup_{\hat{G} \text{ poly-time}} \mathbb{E} \left[ \langle M^*, M^{\hat{G}} \rangle_F \right] \le \sqrt{\mathbb{E} \left[ \|M^{\hat{G}}\|_F^2 \right]} \text{corr} $$

and $\mathbb{E}[\|M^{\hat{G}}\|_F^2] \ge n^2/K$, we get

$$ \begin{aligned} \inf_{\hat{G} \text{ poly-time}} \mathbb{E} \left[ \|M^* - M^{\hat{G}}\|_F^2 \right] &\ge \mathbb{E} \left[ \|M^*\|_F^2 \right] + \mathbb{E} \left[ \|M^{\hat{G}}\|_F^2 \right] - 2\sqrt{\mathbb{E} \left[ \|M^{\hat{G}}\|_F^2 \right]} \text{corr} \\ &\ge \mathbb{E} \left[ \|M^*\|_F^2 \right] + \min_{a \ge n/\sqrt{K}} (a^2 - 2a \text{corr}) \\ &= \mathbb{E} \left[ \|M^*\|_K^2 \right] + \frac{n^2}{K} - \frac{2n}{\sqrt{K}} \text{corr} = \frac{2n^2}{K} (1+o(1)), \end{aligned} $$

where we used $\text{corr}^2 = o(n^2/K)$ and $\mathbb{E}[\|M^*\|_F^2] = n^2 K^{-1}(1+o(1))$ for the last two equalities. $\square$

PROOF OF PROPOSITION A.3. The proof is obtained by combining Lemma A.2 with the following lemma.

LEMMA H.2. Assume that both $G^*$ and $G$ are $\gamma$-balanced as defined in (24). Then, it follows that

$$ [1 - \text{err}(G, G^*)]^2 \le \gamma^2 - \frac{K \|M^G - M^*\|_F^2}{2n^2} . $$
PROOF OF LEMMA H.2. Without loss of generality, we assume that the permutation $\pi$ in the definition of $err(G, G^*)$ is the identity.

$$ err(G, G^*) = \frac{1}{2n} \sum_{k=1}^{K} |G_k \Delta G_k^*| = 1 - \frac{1}{n} \sum_{k=1}^{K} |G_k \cap G_k^*|, $$

which implies that $\sum_{k=1}^{K} |G_k \cap G_k^*| = n[1 - err(G, G^*)]$. Let us define $N_1(G) = |\{(i, j) : i \sim_G j\}|$, $N_1(G^*) = |\{(i, j) : i \sim^* j\}|$, and $N_{11} = |\{(i, j) : i \sim^* j \text{ and } i \sim_G j\}|$. Expanding the squares, we have, for $\gamma$-balanced partitions $G, G^*$, that

$$ (92) \qquad \|M^G - M^*\|_F^2 = 2[N_1(G) + N_1(G^*)] - 4N_{11} \le 2\gamma^2 \frac{n^2}{K} - 4N_{1,1}. $$

Furthermore,

$$ N_{11} \ge \frac{1}{2} \sum_k |G_k \cap G_k^*|^2 $$

$$ (93) \qquad \ge \frac{1}{2K} \left[ \sum_{k=1}^{K} |G_k \cap G_k^*| \right]^2 = \frac{n^2}{2K} [1 - err(G, G^*)]^2, $$

where we used Cauchy-Schwarz inequality in the second line. Plugging (93) in (92) gives

$$ \frac{K}{2n^2} \|M^G - M^*\|_F^2 \le \gamma^2 - [1 - err(G, G^*)]^2 . $$

The proof of Lemma H.2 is complete

<figure><img src="image_18.png" /></figure>

PROOF OF PROPOSITION A.4. Given any subset $I \subset \{3, \dots, n\}$ and any $j = 1, \dots, p$, define the matrix $\alpha^{(I,j)}$

$$ \alpha_{i,j}^{(I,j)} = \mathbf{1}\{j' = j\} \mathbf{1}\{i \in I \cup \{1, 2\}\} $$

By permutation invariance of the problem $\kappa_{x,\alpha^{(I,j)}}$ does not depend on $j$ and only depends on $|I|$ through its cardinality. Denote $I_0 = \{3, \dots, D\}$. By permutation invariance, we know that

$$ (94) \qquad \left(\widetilde{corr}^{(SW)}_{\le D}\right)^2 \ge p \binom{n-2}{D-2} \kappa_{x,\alpha^{(I_0,1)}}^2. $$

To alleviate the notation, we henceforth write $\alpha$ for $\alpha^{(I_0,1)}$.

From Theorem 2.5, we deduce that

$$ (95) \qquad \kappa_{x,\alpha} = \lambda^D \sum_{\pi \in \mathcal{P}_2(\alpha)} C_{x,\beta_1(\pi), \dots, \beta_l(\pi)}, $$

where $l = D/2$ here. We recall that $\beta_s = \beta_s(\pi)$ satisfies $|\beta_s(\pi)| = 2$ so that we can write $\beta_s$ as $\{(i_s, 1), (i'_s, 1)\}$. Equipped with this notation, we have

$$ (96) \qquad C_{x, \beta_1, \dots, \beta_l} = \mathrm{Cum} \left( x, z_1 \mathbf{1}_{k_{i_1}^* = k_{i'_1}^*}, \dots, z_1 \mathbf{1}_{k_{i_l}^* = k_{i'_l}^*} \right), $$
In order to compute (96), we apply the law of total cumulance (Lemma 2.3) by conditioning on $z_1$. Let us define $W_0 := x$ and $W_s = z_1 \mathbf{1}_{k_{is}^* = k_{i's}^*}$ for $s \in [l]$. Consider any partition $\bar{\pi} \in \mathcal{P}([0; l])$. By Lemma 2.3, we have

$$C_{x,\beta_1,\dots,\beta_l} = \sum_{\bar{\pi} \in \mathcal{P}([0;l])} \mathrm{Cum} \left( \mathrm{Cum} \left( (W_i)_{i \in R} | z_1 \right)_{R \in \bar{\pi}} \right)$$

Denote $R_0$ the group that contains $W_0 = x$. If $|R_0| = 1$, then $\mathrm{Cum}(W_0|z_1) = 1/K$ and is constant almost surely. As a consequence, we have $\mathrm{Cum}((W_i)_{i \in R} | z_1)_{R \in \bar{\pi}} = 0$ by Lemma B.2 since a constant is independent from any other random variable. If $|R_0| = 2$ and the other random variable $W_s \in R_0$ is of the form $z_1 \mathbf{1}_{k_1^* = k_2^*}$, we have $\mathrm{Cum}((W_i)_{i \in R_0} | z_1) = z_1 K^{-1}(1 - 1/K)$. For any other choice of $R_0$, we claim that $\mathrm{Cum}((W_i)_{i \in R} | z_1) = 0$. Indeed, conditionally to $z_1$, $\mathbf{1}_{k_1^* = k_2^*}$ is independent from all the other random variables since each $k_i^*$, for $i \in [D]$ occurs at most once in the other random variables. Now consider a group $R \neq R_0$ of $\bar{\pi}$ that do not contain 0. For the same independence argument, we have $\mathrm{Cum}((W_i)_{i \in R} | z_1) = 0$ if $|R| > 1$. We conclude that $C_{x,\beta_1,\dots,\beta_l} = 0$ unless there exists $s \in [l]$ such that $\beta_s = (1,2)$, in which case, we have

$$C_{x,\beta_1,\dots,\beta_l} = \frac{1}{K^l} \left(1 - \frac{1}{K}\right) \mathrm{Cum}(z_1, \dots, z_l)$$

Coming back to (95) and counting, we conclude that

$$\kappa_{x,\alpha} = \frac{(D-2)!}{2^{D/2-1}(D/2-1)!} \cdot \frac{1}{K^{D/2}} \lambda^D \left(1 - \frac{1}{K}\right) \mathrm{Cum}(z_1, \dots, z_l)$$

Let us lower bound the cumulant $\mathrm{Cum}(z_1, \dots, z_l)$ between Bernoulli distribution of parameter $\rho$. By Möbius formula in Lemma B.1, we have

$$\mathrm{Cum}(z_1, \dots, z_l) \ge \rho - \rho^2 \sum_{\pi \in \mathcal{P}(l)} (|\pi| - 1)! \ge \rho - 6\rho^2 l! 2^l,$$

where we used the same computation as in the proof of Corollary 2.6. Coming back to (94) and relying on our condition, we conclude that

$$(\overline{corr}^{(SW)}_{\le D})^2 \ge c' e^{-cD \log(D)} pn^{D-2} \frac{1}{K^D} \lambda^{2D} \rho^2,$$

where $c$ and $c'$ are positive numerical constants.

□