or equivalently: `rowspan(C-D)` $\perp$ `rowspan(Y)` and `colspan(C-D)` $\perp$ `colspan(X)`. Since `colspan(C)` $\subseteq$ `colspan(X)`, `rowspan(C)` $\subseteq$ `rowspan(Y)`, this yields the claim. □

### E.3. Proof for (7.14)

*Proof.* The proof is given when $\sigma$ is the identity permutation $\sigma = (1, \dots, L-1)$. The proof when $\sigma$ is the “converse” permutation $\sigma = (L-1, \dots, 1)$ is similar, replacing rows by columns, left-*-unitarity by right-*-unitarity, etc. We begin by preliminaries on key matrices involved in the expression of the matrices $B_J$, $B_{J-1}$ and $B_p$ appearing in (7.14). We then highlight simple orthogonality conditions which imply (7.14). Finally we prove these orthogonality conditions.

**Preliminaries.** Since $\sigma_{\ell} = \ell$, $\ell \in \llbracket L-1 \rrbracket$, it is not difficult to check by induction on $J \in \llbracket L-1 \rrbracket$ that at the $J$th iteration of Algorithm 6.1, at line 18, we have

1. partition = $(I_1, \dots, I_J)$ where $I_\ell = \{\ell\}, \ell \in \llbracket J-1 \rrbracket$ and $I_J = \llbracket J, L \rrbracket$;

2. $s = J$ (from line 9).

3. $j = J$ and $I_j = I_J = \llbracket J, L \rrbracket$, i.e., $q = J, t = L$ (line 10).

Denoting $(\hat{\mathbf{X}}_\ell)_{\ell=1}^L$ the final output of Algorithm 6.1, one can also check by induction that the list factors obtained at the end of the $J$-th iteration (cf. lines 18 and 20 of Algorithm 6.1) is a tuple of the form:

$$ (\hat{\mathbf{X}}_1, \dots, \hat{\mathbf{X}}_{J-1}, \mathbf{X}_{\llbracket J, J \rrbracket}, \mathbf{X}_{\llbracket J+1, L \rrbracket}). $$

Indeed, the value of the first $J-1$ factors in the list factors are left-$r_\ell$-unitary factors for appropriate $r_\ell$, $\ell \in \llbracket J-1 \rrbracket$ (cf. Lemma 6.3). Therefore, their values during pseudo-orthonormalization operations in the next iterations $J+1, J+2, \dots, L-1$ do not change anymore, which means that they are equal to $\hat{\mathbf{X}}_1, \dots, \hat{\mathbf{X}}_{J-1}$. The factor $\mathbf{X}_{\llbracket J, J \rrbracket} = \mathbf{X}_{\llbracket q, s \rrbracket}$ will be pseudo-orthonormalized at the next iteration if $J < L-1$.

**Expression of $B_J$**. By the convention of (7.9) and the above observation, we have $\mathbf{X}_{\text{left}}^{(J)} = \mathbf{X}_{\llbracket 1, 1 \rrbracket} \cdots \mathbf{X}_{\llbracket J-1, J-1 \rrbracket} = \prod_{\ell=1}^{J-1} \hat{\mathbf{X}}_\ell$ (by convention this is the identity if $J=1$) and $\mathbf{X}_{\text{right}}^{(J)} = \mathbf{I}_{a_L b_L d_L}$. The matrices $\mathbf{X}_{\llbracket q, s \rrbracket}$ $\mathbf{X}_{\llbracket s+1, t \rrbracket}$, $\mathbf{X}_{I_j}$ of line 18 of Algorithm 6.1 correspond to $\mathbf{X}_{\llbracket J, J \rrbracket}$, $\mathbf{X}_{\llbracket J+1, L \rrbracket}$ and $\mathbf{X}_{\llbracket J, L \rrbracket}$, hence the matrix $B_J$ from (7.10) is

$$ (E.17) \quad \mathbf{B}_J := \mathbf{X}_{\text{left}}^{(J)} \mathbf{X}_{\llbracket q, s \rrbracket} \mathbf{X}_{\llbracket s+1, t \rrbracket} \mathbf{X}_{\text{right}}^{(J)} = \mathbf{X}_{\text{left}}^{(J)} \mathbf{X}_{\llbracket J, J \rrbracket} \mathbf{X}_{\llbracket J+1, L \rrbracket}, \quad \forall J \in \llbracket L-1 \rrbracket. $$

Given the nature of (7.14) we also express $B_{J-1}$ and $B_p$ for $p \in \llbracket J, L-1 \rrbracket$.

Equation (E.17) also reads $\mathbf{B}_J = \mathbf{X}_{\llbracket 1, 1 \rrbracket} \cdots \mathbf{X}_{\llbracket J, J \rrbracket} \mathbf{X}_{\llbracket J+1, L \rrbracket}$, hence for $J \in \llbracket 2, L-1 \rrbracket$

$$ (E.18) \quad \begin{aligned} \mathbf{B}_{J-1} &= \mathbf{X}_{\llbracket 1, 1 \rrbracket} \cdots \mathbf{X}_{\llbracket J-1, J-1 \rrbracket} \mathbf{X}_{\llbracket J, L \rrbracket} \\ &= \mathbf{X}_{\text{left}}^{(J)} \mathbf{X}_{\llbracket J, L \rrbracket}. \end{aligned} $$

This indeed holds for all $J \in \llbracket L-1 \rrbracket$: for $J=1$, the convention below (7.10) yields $\mathbf{B}_{J-1} = \mathbf{B}_0 := \mathbf{A}$, and $\mathbf{X}_{\llbracket 1, L \rrbracket} = \mathbf{A}$ (line 5 of Algorithm 6.1). As $\mathbf{X}_{\text{left}}^{(J)}$ is the identity, this shows (E.18) for $J=1$.

For $p > J$ we have $\mathbf{X}_{\text{left}}^{(p)} = \mathbf{X}_{\text{left}}^{(J)} \hat{\mathbf{X}}_J \cdots \hat{\mathbf{X}}_{p-1}$, and one easily deduces from (E.17) that

$$ (E.19) \quad \mathbf{B}_p = \mathbf{X}_{\text{left}}^{(J)} \left( \prod_{\ell=J}^{p-1} \hat{\mathbf{X}}_\ell \right) \mathbf{X}_{\llbracket p, p \rrbracket} \mathbf{X}_{\llbracket p+1, L \rrbracket}, \quad \forall J, p \in \llbracket L-1 \rrbracket \text{ such that } p \ge J, $$

where again by convention an empty matrix product is the identity.
**Expression of** $\langle \mathbf{B}_{J-1} - \mathbf{B}_J, \mathbf{B}_p \rangle$. From now on we fix $J \in \llbracket L \rrbracket$ and $p \in \llbracket J, L-1 \rrbracket$, and rewrite $\langle \mathbf{B}_{J-1} - \mathbf{B}_J, \mathbf{B}_p \rangle$ where we recall that the inner-product is associated to the Frobenius norm on matrices. Denote

$$ (E.20) \qquad \begin{aligned} \tilde{\mathbf{B}}_{J-1} &:= \mathbf{X}_{\llbracket J,L \rrbracket}, \\ \tilde{\mathbf{B}}_J &:= \mathbf{X}_{\llbracket J,J \rrbracket} \mathbf{X}_{\llbracket J+1,L \rrbracket}, \\ \tilde{\mathbf{B}}_p &:= \left( \prod_{\ell=J}^{p-1} \hat{\mathbf{X}}_{\ell} \right) \mathbf{X}_{\llbracket p,p \rrbracket} \mathbf{X}_{\llbracket p+1,L \rrbracket}. \end{aligned} $$

Note that the expression of $\tilde{\mathbf{B}}_p$ falls back on $\mathbf{B}_J$ when $p = J$. We observe that for $k \in \{J-1, J, p\}$, $\tilde{\mathbf{B}}_k$ is a $\pi'$-factor with $\pi' = \pi_J * \dots * \pi_L$ by Proposition 4.9 since $\mathbf{X}_{\llbracket p,p \rrbracket} \in \Sigma^{\pi_p}, \mathbf{X}_{\llbracket p+1,L \rrbracket} \in \Sigma^{\pi_{p+1}*\dots*\pi_L}$ and (when $p > J$) $\hat{\mathbf{X}}_\ell \in \Sigma^{\pi_\ell}$ for $\ell \in \llbracket J, p-1 \rrbracket$.

Since the factors $\hat{\mathbf{X}}_\ell$ for $\ell \in \llbracket J-1 \rrbracket$ are $\pi_\ell$-factors, with chainable patterns $\pi_\ell$, and left-$r_\ell$-unitary for appropriate $r_\ell$'s, by Lemma 4.14 and a recursive use of Lemma C.2 their product $\mathbf{X} := \mathbf{X}_{\text{left}}^{(J)}$ is a left-$r$-unitary $\pi$-factor with $\pi := (\pi_1 * \dots * \pi_{J-1})$ and $r = r(\pi_{J-1}, \pi_J)$. As $\mathbf{Y}_1 := \tilde{\mathbf{B}}_{J-1} - \tilde{\mathbf{B}}_J$ and $\mathbf{Y}_2 := \tilde{\mathbf{B}}_p$ are $\pi'$-factors, and since by Lemma 4.17, $r(\pi, \pi') = r(\pi_{J-1}, \pi_J) = r$, left-$r$-unitarity of $\mathbf{X}$ and the parallelogram law yield

$$ \langle \mathbf{X}\mathbf{Y}_1, \mathbf{X}\mathbf{Y}_2 \rangle = \frac{1}{2} (\|\mathbf{X}\mathbf{Y}_1\|_F^2 + \|\mathbf{X}\mathbf{Y}_2\|_F^2 - \|\mathbf{X}(\mathbf{Y}_1 + \mathbf{Y}_2)\|_F^2) = \langle \mathbf{Y}_1, \mathbf{Y}_2 \rangle. $$

Combining this with the expressions of $\mathbf{B}_{J-1}, \mathbf{B}_J, \mathbf{B}_p$, we obtain:

$$ \langle \mathbf{B}_{J-1} - \mathbf{B}_J, \mathbf{B}_p \rangle = \langle \mathbf{X}_{\text{left}}^{(J)}(\tilde{\mathbf{B}}_{J-1} - \tilde{\mathbf{B}}_J), \mathbf{X}_{\text{left}}^{(J)}\tilde{\mathbf{B}}_p \rangle = \langle \tilde{\mathbf{B}}_{J-1} - \tilde{\mathbf{B}}_J, \tilde{\mathbf{B}}_p \rangle. $$

**Orthogonality conditions and their proof.** Consider the partition $\mathcal{P} := \mathcal{P}(\mathbf{S}_{\pi_{\text{left}}}, \mathbf{S}_{\pi_{\text{right}}})$ with $\pi_{\text{left}} := \pi_J$ and $\pi_{\text{right}} = \pi_{J+1}*\dots*\pi_L$. For each $k \in \{J-1, J, p\}$, since $\tilde{\mathbf{B}}_k$ is a $\pi'$-factor and $\pi' = \pi_{\text{left}} * \pi_{\text{right}}$, by Lemma 4.10 we have $\text{supp}(\tilde{\mathbf{B}}_k) \subseteq \bigcup_{P \in \mathcal{P}} R_P \times C_P$ hence

$$ \langle \tilde{\mathbf{B}}_{J-1} - \tilde{\mathbf{B}}_J, \tilde{\mathbf{B}}_p \rangle = \sum_{P \in \mathcal{P}} \langle (\tilde{\mathbf{B}}_{J-1} - \tilde{\mathbf{B}}_J)[R_P, C_P], \tilde{\mathbf{B}}_p[R_P, C_P] \rangle. $$

It follows that $\langle \mathbf{B}_{J-1} - \mathbf{B}_J, \mathbf{B}_p \rangle = 0$ is implied by the orthogonality conditions

$$ (E.21) \qquad \langle (\tilde{\mathbf{B}}_{J-1} - \tilde{\mathbf{B}}_J)[R_P, C_P], \tilde{\mathbf{B}}_p[R_P, C_P] \rangle = 0, \quad \forall P \in \mathcal{P}. $$

To conclude it remains to prove that (E.21) indeed holds for a fixed $P \in \mathcal{P}$. By the definition of $\mathbf{X}_{\llbracket J,J \rrbracket} = \mathbf{X}_{\llbracket q,s \rrbracket}$, $\mathbf{X}_{\llbracket J+1,L \rrbracket} = \mathbf{X}_{\llbracket s+1,t \rrbracket}$ and $\mathbf{X}_{\llbracket J,L \rrbracket} = \mathbf{X}_{\llbracket q,t \rrbracket}$ at line 18 of Algorithm 6.1 and line 3 of Algorithm 3.1, we obtain that

$$ \tilde{\mathbf{B}}_J[R_P, C_P] \stackrel{(\text{E.20})}{=} (\mathbf{X}_{\llbracket J,J \rrbracket} \mathbf{X}_{\llbracket J+1,L \rrbracket})[R_P, C_P] \\ \stackrel{\text{Lemma A.1}}{=} \mathbf{X}_{\llbracket J,J \rrbracket}[R_P, P] \mathbf{X}_{\llbracket J+1,L \rrbracket}[P, C_P] $$

is the best rank-$|P|$ approximation of

$$ \tilde{\mathbf{B}}_{J-1}[R_P, C_P] \stackrel{(\text{E.20})}{=} \mathbf{X}_{\llbracket J,L \rrbracket}[R_P, C_P]. $$
If the two matrices are equal then (E.21) trivially holds, otherwise we have

$$ \operatorname{rank}(\tilde{\mathbf{B}}_J[R_P, C_P]) = \operatorname{rank}(\mathbf{X}_{\ll J, J}] [R_P, P]) = |P| \\ \operatorname{colspan}(\tilde{\mathbf{B}}_J[R_P, C_P]) = \operatorname{colspan}(\mathbf{X}_{\ll J, J}] [R_P, P]). $$

Since $\mathbf{X}_{\ll J, J}$ is pseudo-orthonormalized into $\hat{\mathbf{X}}_J$ at the next iteration $J + 1$ (by design of Algorithm C.1), we also have

$$ \operatorname{colspan}(\mathbf{X}_{\ll J, J}] [R_P, P]) = \operatorname{colspan}(\hat{\mathbf{X}}_J[R_P, P]). $$

Combining these equalities with Lemma E.4 we obtain

$$ \operatorname{colspan}(\hat{\mathbf{X}}_J[R_P, P]) = \operatorname{colspan}(\tilde{\mathbf{B}}_J[R_P, C_P]) \perp \operatorname{colspan}((\tilde{\mathbf{B}}_J - \tilde{\mathbf{B}}_{J-1})[R_P, C_P]). $$

The orthogonality condition (E.21) is then implied by the fact that

$$ \operatorname{colspan}(\tilde{\mathbf{B}}_p[R_P, C_P]) \subseteq \operatorname{colspan}(\hat{\mathbf{X}}_J[R_P, P]) $$

which is trivial if $p = J$, and if $p > J$ follows from the fact by (E.20) we have $\tilde{\mathbf{B}}_p = \hat{\mathbf{X}}_J Z$ for some $Z := \sum_{\ell=\ell_{\text{right}}}^{\ell_{\text{left}}}$.

**Appendix F. On the generalization of the complementary low-rank property**

We show that the generalized complementary low-rank property associated with a chainable $\beta$ given in Definition 7.6 coincides, under some assumption on $\beta$, with the classical definition of the complementary low-rank property given in [23].

**F.1. Definition of the classical complementary low-rank property [23]**

We start by reformulating the definition of [23], based on the following terminology. A cluster tree $T$ of a set of indices $\ll n \gg$ with depth $L$ is a tree where:

* the nodes are subsets of $\ll n \gg$;

* the root is $\ll n \gg$;

* each non-leaf node has non-empty children that partition their parent;

* the only leaves are at level $L$.

By convention the root nodes are at level 0. The set of all nodes at level $\ell \in \ll L \gg$ is denoted $T(\ell)$. Notice that, by definition of a cluster tree $T$, the set of nodes $T(\ell)$ form a partition of the root node for each level $\ell$, and $T(\ell + 1)$ is finer than $T(\ell)$, in the following sense.

**DEFINITION F.1 (Finer partitions [15, Definition 1.11]).** Given two partitions $P$ and $\tilde{P}$ of $\ll n \gg$, $P$ is finer than $\tilde{P}$ if for all $I \in P$ there is a $\tilde{I} \in \tilde{P}$ with $I \subseteq \tilde{I}$.

We can now give a definition that covers the classical notion of complementary low-rank property [23].

**DEFINITION F.2 ("Classical" complementary low-rank property).** Consider two cluster trees $T^{\text{row}}$ and $T^{\text{col}}$ of $\ll m \gg$ and $\ll n \gg$ with the same depth $L$, and a set of integer rank constraints $\mathcal{R} := \{r_{R,C} | (R, C) \in T^{\text{row}}(\ell) \times T^{\text{col}}(L - \ell + 1), \ell \in \ll L \gg\} \subseteq \mathbb{N}$. A matrix $\mathbf{A}$ of size $m \times n$ satisfies the complementary low-rank property for $T^{\text{row}}$ and $T^{\text{col}}$ with rank constraints $\mathcal{R}$ if the submatrix $\mathbf{A}[R, C]$ has rank at most $r_{R,C}$ for each $(R, C) \in T^{\text{row}}(\ell) \times T^{\text{col}}(L - \ell + 1)$ and $\ell \in \ll L \gg$.

With this definition, a matrix $\mathbf{A}$ satisfies the complementary low-rank property of [23, 25] if it is $\epsilon$-close in the Frobenius norm to a matrix $\tilde{\mathbf{A}}$ satisfying Definition F.2 in the particular case where $T^{\text{row}}$ and $T^{\text{col}}$ are dyadic trees or quadtrees, where it is assumed that $\max_{R,C} r_{R,C}$ is bounded poly-logarithmically in $1/\epsilon$ and in matrix size.
**F.2. Relation with the generalized complementary low-rank property (Definition 7.6)** A cluster tree yields a hierarchical partitioning of a given set of indices. Similarly, under some appropriate conditions, a chainable architecture $\beta$ also yields a hierarchical partitioning of the row and column indices, which leads to two cluster trees.

**PROPOSITION F.3.** Consider a chainable architecture $\beta = (\pi_\ell)^{L}_{\ell=1}$ where $\pi_\ell := (a_\ell, b_\ell, c_\ell, d_\ell)$ for $\ell \in \llbracket L \rrbracket$, and denote $m \times n$ the size of the matrices in $\mathcal{B}^\beta$, as well as

$$ (F.1) \qquad S_{q,t} := S_{\pi_q * \dots * \pi_t}, \quad 1 \le q \le t \le L. $$

Recalling the notation from Definition 3.3, define for all $\ell \in \llbracket L-1 \rrbracket$:

$$ (F.2) \qquad \begin{aligned} \mathcal{P}_{L-\ell}^{\text{row}} &:= \{R_P \mid P \in \mathcal{P}(\mathbf{S}_{1,\ell}, \mathbf{S}_{\ell+1,L})\}, \\ \mathcal{P}_{\ell}^{\text{col}} &:= \{C_P \mid P \in \mathcal{P}(\mathbf{S}_{1,\ell}, \mathbf{S}_{\ell+1,L})\}. \end{aligned} $$

Assume that $a_1 = d_L = 1$. Then:

1. For each $\ell \in \llbracket L-1 \rrbracket$, $\mathcal{P}_\ell^{\text{row}}$ is a partition of $\llbracket m \rrbracket$, and $\mathcal{P}_\ell^{\text{col}}$ is a partition of $\llbracket n \rrbracket$. Moreover $\mathcal{P}_{\ell+1}^{\text{row}}$ (resp. $\mathcal{P}_\ell^{\text{col}}$) is finer than $\mathcal{P}_\ell^{\text{col}}$ (resp. than $\mathcal{P}_\ell^{\text{row}}$) when $\ell \le L-2$.

2. Consequently, when completed by $\mathcal{P}_0^{\text{row}} := \llbracket m \rrbracket$ and $\mathcal{P}_0^{\text{col}} := \llbracket n \rrbracket$, the collections $\{\mathcal{P}_\ell^{\text{row}}\}_{\ell=0}^{L-1}$ and $\{\mathcal{P}_\ell^{\text{col}}\}_{\ell=0}^{L-1}$ yield two cluster trees, denoted $T_\beta^{\text{row}}$ and $T_\beta^{\text{col}}$, of depth $L-1$ with root node $\llbracket m \rrbracket$ and $\llbracket n \rrbracket$, respectively.

3. For each $\ell \in \llbracket L-1 \rrbracket$ we have

$$ (F.3) \qquad \{(R_P, C_P) : P \in \mathcal{P}(\mathbf{S}_{1,\ell}, \mathbf{S}_{\ell+1,L})\} = T_{\beta}^{\text{row}}(L-\ell) \times T_{\beta}^{\text{col}}(\ell). $$

We postpone the proof of Proposition F.3 to immediately highlight that under its assumptions the general complementary low-rank property of Definition 7.6 coincides with the classical one of Definition F.2.

**COROLLARY F.4.** Consider a chainable architecture $\beta = (\pi_\ell)^{L}_{\ell=1}$ where $\pi_\ell := (a_\ell, b_\ell, c_\ell, d_\ell)$ for $\ell \in \llbracket L \rrbracket$, and assume that $a_1 = d_L = 1$. For any matrix $\mathbf{A}$ of appropriate size, the following are equivalent:

* $\mathbf{A}$ satisfies the generalized complementary low-rank property (Definition 7.6) associated with $\beta$;

* $\mathbf{A}$ satisfies the classical complementary low-rank property (Definition F.2) for the cluster trees $(T_\beta^{\text{row}}, T_\beta^{\text{col}})$ defined in Proposition F.3, with rank constraint $\mathcal{R}$ such that for each $\ell \in \llbracket L-1 \rrbracket$ and every $(R, C) \in T_\beta^{\text{row}}(L-\ell) \times T_\beta^{\text{col}}(\ell)$ we have $r_{R,C} = r(\pi_\ell, \pi_{\ell+1})$.

*Proof.* Since $\beta$ is chainable and $a_1 = d_L = 1$, by Lemma 4.14 we have $\pi_1 * \dots * \pi_L = (1, m, n, 1)$ for some integers $m, n$ (which turn out to be the dimensions of matrix $\mathbf{A}$) hence $S_{\pi_1 * \dots * \pi_L} = 1_{m \times n}$. Therefore, by Definition 7.6, a matrix $\mathbf{A}$ satisfies the general complementary low-rank property associated with $\beta$ if, and only if, $\text{rank}(\mathbf{A}[R_P, C_P]) \le r(\pi_\ell, \pi_{\ell+1})$ for each $P \in \mathcal{P}(\mathbf{S}_{1,\ell}, \mathbf{S}_{\ell+1,L})$ and $\ell \in \llbracket L-1 \rrbracket$ (we use the shorthand (F.1)). By Proposition F.3, this is precisely a reformulation of the classical complementary low-rank property (Definition F.2) for the trees $(T_\beta^{\text{row}}, T_\beta^{\text{col}})$.

*Proof of Proposition F.3.* The second claim is an immediate consequence of the first one. We only prove the first claim for the column partitions $\{\mathcal{P}_\ell^{\text{col}}\}_{\ell=1}^{L-1}$, since the proof is similar for the row partitions $\{\mathcal{P}_\ell^{\text{row}}\}_{\ell=1}^{L-1}$. Given $\ell \in \llbracket L-1 \rrbracket$, let us first show that $\mathcal{P}_\ell^{\text{col}}$ is a partition of $\llbracket n \rrbracket$ for any $\ell \in \llbracket L-1 \rrbracket$, where $n := a_L c_L d_L$. By (4.5): $\pi_{\ell+1} * \dots * \pi_L = (a_{\ell+1}, \frac{b_{\ell+1} d_{\ell+1}}{d_L}, \frac{a_L c_L}{a_{\ell+1}}, d_L) = (a_{\ell+1}, b_{\ell+1} d_{\ell+1}, \frac{a_L c_L}{a_{\ell+1}}, 1)$ since
$d_L = 1$. Therefore, by Definition 4.1, the elements of $\mathcal{P}_{\ell}^{\text{col}}$ partition the integer set $\llbracket n \rrbracket$ (with $n := a_L c_L = a_L c_L d_L$) into consecutive intervals of length $c_{\ell}$, where $c_{\ell} := \frac{a_L c_L}{a_{\ell+1}}$. It remains to show that each element of $\mathcal{P}_{\ell}^{\text{col}}$ can itself be partitioned into elements of $\mathcal{P}_{\ell+1}^{\text{col}}$. Since the latter are consecutive intervals of length $c_{\ell+1}$, this is a direct consequence of the fact that $c_{\ell}$ is an integer multiple of $c_{\ell+1}$: indeed, since $(\pi_{\ell+1}, \pi_{\ell+2})$ is chainable, we have: $a_{\ell+1} | a_{\ell+2}$, $\gamma = a_{\ell+2}/a_{\ell+1} \in \mathbb{N}$ and $c_{\ell} = \gamma c_{\ell+1}$.

To prove (F.3) observe that the left hand side is trivially a subset of $T_{\beta}^{\text{row}}(L-\ell) \times T_{\beta}^{\text{col}}(\ell)$, by the definition of $T_{\beta}^{\text{row}}(L-\ell) = \mathcal{P}_{L-\ell}^{\text{row}}$ and $T_{\beta}^{\text{col}}(\ell) = \mathcal{P}_{\ell}^{\text{col}}$ (cf (F.2)). The equality will follow from the fact that both sides share the same number of elements: this is a direct consequence of the fact that $|T_{\beta}^{\text{row}}(L-\ell)| = d_{\ell}$, $|T_{\beta}^{\text{col}}(\ell)| = a_{\ell+1}$, a property that we prove immediately below. Indeed, this property implies that $|T_{\beta}^{\text{row}}(L-\ell) \times T_{\beta}^{\text{col}}(\ell)| = a_{\ell+1}d_{\ell}$, and by Lemma 4.17, the number of equivalence classes $P$ of $\mathcal{P}(\mathbf{S}_{1,\ell}, \mathbf{S}_{\ell+1,L})$ is also $\frac{a_{\ell}c_{\ell}d_{\ell}}{r(\pi_{\ell}, \pi_{\ell+1})} = a_{\ell+1}d_{\ell}$. To conclude, we prove that $|T_{\beta}^{\text{row}}(L-\ell)| = d_{\ell}$, $|T_{\beta}^{\text{col}}(\ell)| = a_{\ell+1}$. By Lemma 4.14, we have $\pi_{\ell+1} * \dots * \pi_L = (a_{\ell+1}, b_{\ell+1}d_{\ell+1}, \frac{a_L c_L}{a_{\ell+1}}, 1)$ since $d_L = 1$ hence $\mathbf{S}_{\ell+1,L}$ is a block diagonal matrix with $a_{\ell+1}$ dense blocks of the same size. Tracing back all definitions this implies that $T_{\beta}^{\text{col}}(\ell) = \mathcal{P}_{\ell}^{\text{col}}$ is made of exactly $a_{\ell+1}$ consecutive intervals of the same size. The proof is similar for $T_{\beta}^{\text{row}}(L-\ell)$. $\square$

**F.3. Illustration of the generalized complementary low-rank property (Definition 7.6)** We give an illustration of the generalized complementary low-rank property for the square dyadic butterfly architecture $\boldsymbol{\beta} = (\boldsymbol{\pi}_{\ell})_{\ell=1}^L$ for matrices of size $n \times n$ with $n = 16$ and $L = \log_2(n) = 4$, i.e., $\boldsymbol{\pi}_{\ell} = (2^{L-\ell}, 2, 2, 2^{\ell-1})$ for $\ell \in \llbracket L \rrbracket$. Let $\mathbf{A}$ be a matrix satisfying such a property. By the second property of Definition 7.6, for each $P \in \mathcal{P}(\mathbf{S}_{\pi_1*\dots*\pi_{\ell}}, \mathbf{S}_{\pi_{\ell+1}*\dots*\pi_L})$ and $\ell \in \llbracket L-1 \rrbracket$, the rank of the submatrix $\mathbf{A}[R_P, C_P]$ is at most $r(\boldsymbol{\pi}_{\ell}, \boldsymbol{\pi}_{\ell+1})$, which is equal to 1 by Definition 4.7. Figure 7 illustrates these rank-one submatrices, by remarking that $(\boldsymbol{\pi}_1, \boldsymbol{\pi}_2 * \boldsymbol{\pi}_3 * \boldsymbol{\pi}_4) = ((1, 2, 2, 8), (2, 8, 8, 1))$, $(\boldsymbol{\pi}_1 * \boldsymbol{\pi}_2, \boldsymbol{\pi}_3 * \boldsymbol{\pi}_4) = ((1, 4, 4, 4), (4, 4, 4, 1))$ and $(\boldsymbol{\pi}_1 * \boldsymbol{\pi}_2 * \boldsymbol{\pi}_3, \boldsymbol{\pi}_4) = ((1, 8, 8, 2), (8, 2, 2, 1))$, due to Lemma 4.14.

<figure><img src="image_12.png" /><figcaption>**Fig. 7:** Illustration of the complementary low-rank property associated to the square dyadic butterfly architecture $\boldsymbol{\beta} = (\boldsymbol{\pi}_{\ell})_{\ell=1}^L$ for matrices of size $n \times n$ with $n = 16$ and $L = \log_2(n) = 4$. For each $\ell \in \llbracket L-1 \rrbracket$, we represent the partition of the matrix indices $\llbracket n \rrbracket \times \llbracket n \rrbracket$ into $\{R_P \times C_P, P \in \mathcal{P}(\mathbf{S}_{\pi_1*\dots*\pi_{\ell}}, \mathbf{S}_{\pi_{\ell+1}*\dots*\pi_L})\}$ using different colors, where each color represent one element of the partition.</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Fig. 8: Illustration of the permutation $\sigma = (5, 2, 1, 3, 4, 7, 6, 8, 9)$ corresponding to the balanced factor-bracketing tree of $[10]$.</figcaption></figure>

**Appendix G. Numerical experiments: additional details and results**

In complement to Section 8, we include further experimental details and results. In Figure 4b, we observed that the approximation error obtained by the hierarchical algorithm *with* orthonormalization operations (Algorithm 6.1) is always smaller than the noise level $\epsilon = 0.1$, as opposed to the one obtained without orthonormalization. In fact, we have the same observation for any values of $\epsilon \in \{0.01, 0.03, 0.1, 0.3\}$, as shown in Figure 9.
<figure><img src="image_14.png" /><figcaption>Fig. 9: Relative approximation errors vs. the matrix size *n*, for Algorithm 5.1 (without orthonormalization) and Algorithm 6.1 (with orthonormalization), for the instance of Problem (1.1) described in Subsection 8.2 with *r* = 4. We show mean and standard deviation on the error bars over 10 repetitions of the experiment.</figcaption></figure>