Zoology: Measuring and Improving Recall in Efficient Language Models — part 9/14

Cleaned-text code points [123560, 139148). Bibliography omitted here; source.md includes it.

Similarly, for any input 𝐮 BaseConv ∈ ℝ N × d \bm{u}_{\textsc{BaseConv}}\in\mathbbm{R}^{N\times d} and ( N , L , d , N ′ , d ) − (N,L,d,N^{\prime},d)- Coyote such that 𝐳 BaseConv ≡ BaseConv ​ ( 𝐮 ) \bm{z}_{\textsc{BaseConv}}\equiv\textsc{BaseConv}(\bm{u}) with a set of filters 𝐡 ℓ \bm{h}^{\ell} for ℓ ∈ [ L ] \ell\in[L] , there exists a series of Hyena layers such that we have Hyena ⁡ ( Hyena ⁡ ( … ​ Hyena ​ ( 𝒖 BaseConv , 𝒉 ) ) ) ⏟ L ​ layers ≡ 𝒛 BaseConv . \underbrace{\mathrm{Hyena}\left(\mathrm{Hyena}\left(\ldots\mathrm{Hyena}(\bm{u}_{\textsc{BaseConv},\bm{h}})\right)\right)}_{L\text{ layers}}\equiv\bm{z}_{\textsc{BaseConv}}.

###### Proof.

For the input 𝒖 Hyena ∈ ℝ N × d \bm{u}_{\mathrm{Hyena}}\in\mathbbm{R}^{N\times d} , the output of the ℓ \ell th layer 𝒛 Hyena ℓ ∈ ℝ N ′ × d ′ \bm{z}^{\ell}_{\mathrm{Hyena}}\in\mathbbm{R}^{N^{\prime}\times d^{\prime}} for Hyena is given by (see Algorithm 3 ) 𝒛 Hyena ℓ ≡ 𝒑 Hyena ℓ ⊙ ( 𝒉 l ∗ 𝒛 ℓ − 1 ) , \displaystyle\bm{z}^{\ell}_{\mathrm{Hyena}}\equiv\bm{p}^{\ell}_{\mathrm{Hyena}}\odot(\bm{h}^{l}\ast\bm{z}^{\ell-1}), where 𝒑 Hyena ℓ ≡ Linear ​ ( 𝒖 Hyena ) ∈ ℝ N ′ × d \bm{p}^{\ell}_{\mathrm{Hyena}}\equiv\texttt{Linear}(\bm{u}_{\mathrm{Hyena}})\in\mathbbm{R}^{N^{\prime}\times d} . Now, using the original input 𝒖 Hyena ∈ ℝ N × d \bm{u}_{\mathrm{Hyena}}\in\mathbbm{R}^{N\times d} to Hyena, we define the following input for BaseConv using one layer: 𝒖 BaseConv ≡ ( 𝒖 Hyena 𝟎 ( N ′ − N ) × d 𝒖 Hyena ) \bm{u}_{\textsc{BaseConv}}\equiv\begin{pmatrix}\bm{u}_{\mathrm{Hyena}}\\ \hline\cr\\ \bm{0}^{(N^{\prime}-N)\times d}\\ \hline\cr\\ \bm{u}_{\mathrm{Hyena}}\end{pmatrix} Then, we simply use the 𝚛𝚎𝚖𝚎𝚖𝚋𝚎𝚛 N , N , N ′ − N , N ′ − N ( 𝒖 BaseConv : 𝒖 Hyena , 𝒖 Hyena , 𝒉 Hyena ℓ , 𝒑 Hyena ℓ ) {\tt remember}_{N,N,N^{\prime}-N,N^{\prime}-N}(\bm{u}_{\textsc{BaseConv}}:\bm{u}_{\mathrm{Hyena}},\bm{u}_{\mathrm{Hyena}},\bm{h}^{\ell}_{\mathrm{Hyena}},\bm{p}^{\ell}_{\mathrm{Hyena}}) primitive for BaseConv . Consequently, this allows us to “remember” the input 𝒖 Hyena \bm{u}_{\mathrm{Hyena}} in the output of the previous BaseConv layer 𝒛 BaseConv ℓ − 1 \bm{z}^{\ell-1}_{\textsc{BaseConv}} . We then use this to retrieve 𝒑 Hyena ℓ ≡ linear ⁡ ( 𝒖 Hyena ) \bm{p}^{\ell}_{\mathrm{Hyena}}\equiv\mathrm{linear}(\bm{u}_{\mathrm{Hyena}}) with the projection used for BaseConv given by p BaseConv ℓ ≡ Linear ​ ( 𝒛 BaseConv ℓ − 1 ) ≡ ( 𝟏 N × d 𝒑 Hyena ℓ . ) p^{\ell}_{\textsc{BaseConv}}\equiv\texttt{Linear}(\bm{z}^{\ell-1}_{\textsc{BaseConv}})\equiv\begin{pmatrix}\bm{1}^{N\times d}\\ \hline\cr\\ \bm{p}^{\ell}_{\mathrm{Hyena}}.\end{pmatrix} Overall, the output of the ℓ \ell th layer for BaseConv is given by 𝒛 BaseConv ℓ ≡ ( 𝒑 Hyena ℓ ⊙ ( 𝒉 Hyena ℓ ∗ 𝒖 Hyena ) 𝟎 ( M − N ) × d 𝒖 Hyena ) ≡ ( 𝒛 Hyena ℓ 𝟎 ( M − N ) × d 𝒖 Hyena ) \bm{z}^{\ell}_{\textsc{BaseConv}}\equiv\begin{pmatrix}\bm{p}^{\ell}_{\mathrm{Hyena}}\odot\left(\bm{h}^{\ell}_{\mathrm{Hyena}}\ast\bm{u}_{\mathrm{Hyena}}\right)\\ \hline\cr\\ \bm{0}^{(M-N)\times d}\\ \hline\cr\\ \bm{u}_{\mathrm{Hyena}}\end{pmatrix}\equiv\begin{pmatrix}\bm{z}^{\ell}_{\mathrm{Hyena}}\\ \hline\cr\\ \bm{0}^{(M-N)\times d}\\ \hline\cr\\ \bm{u}_{\mathrm{Hyena}}\end{pmatrix} Hence, we can reproduce the output of the ℓ \ell th layer of Hyena using five layers of BaseConv after augmenting the input and using the remembering primitive ( Proposition H.10 ) with internal dimension N ′ + N N^{\prime}+N .

Now, for the input 𝒖 BaseConv ∈ ℝ N × d \bm{u}_{\textsc{BaseConv}}\in\mathbbm{R}^{N\times d} , the output of the ℓ \ell th layer for BaseConv is given by z BaseConv ℓ ≡ Linear ​ ( z BaseConv ℓ − 1 ) ⊙ conv ⁡ ( h l , z BaseConv ℓ − 1 ) . \displaystyle z^{\ell}_{\textsc{BaseConv}}\equiv\texttt{Linear}(z^{\ell-1}_{\textsc{BaseConv}})\odot\mathrm{conv}(h^{l},z^{\ell-1}_{\textsc{BaseConv}}). Here, we show inductively that simply using ℓ \ell -many Hyena models recursively simulates z BaseConv ℓ z^{\ell}_{\textsc{BaseConv}} . For ℓ = 1 \ell=1 , we have Hyena ⁡ ( 𝒖 BaseConv , 𝒉 ) ≡ Linear ​ ( 𝒖 BaseConv ) ⊙ ( 𝒉 1 ∗ 𝒖 BaseConv ) ≡ 𝒛 BaseConv 1 . \mathrm{Hyena}(\bm{u}_{\textsc{BaseConv},\bm{h}})\equiv\texttt{Linear}(\bm{u}_{\textsc{BaseConv}})\odot(\bm{h}^{1}\ast\bm{u}_{\textsc{BaseConv}})\equiv\bm{z}^{1}_{\textsc{BaseConv}}. We now assume that ( ℓ − 1 ) (\ell-1) -many recursive Hyena models produce z BaseConv ( ℓ − 1 ) z^{(\ell-1)}_{\textsc{BaseConv}} . For the ℓ \ell th layer, we then have Hyena ⁡ ( Hyena ⁡ ( … ​ Hyena ​ ( 𝒖 BaseConv , 𝒉 ) ) ) \displaystyle\mathrm{Hyena}\left(\mathrm{Hyena}\left(\ldots\mathrm{Hyena}(\bm{u}_{\textsc{BaseConv},\bm{h}})\right)\right) ≡ \displaystyle\equiv\quad Hyena ⁡ ( z BaseConv ( l − 1 ) ) \displaystyle\mathrm{Hyena}\left(z^{(l-1)}_{\textsc{BaseConv}}\right) ≡ \displaystyle\equiv\quad linear ⁡ ( z BaseConv ( l − 1 ) ) ⊙ conv ⁡ ( h l , z BaseConv ( l − 1 ) ) \displaystyle\mathrm{linear}\left(z^{(l-1)}_{\textsc{BaseConv}}\right)\odot\mathrm{conv}\left(h^{l},z^{(l-1)}_{\textsc{BaseConv}}\right) ≡ \displaystyle\equiv\quad z BaseConv ℓ . \displaystyle z^{\ell}_{\textsc{BaseConv}}. ∎

### H.4 Linear Arithmetic Circuits

In this section we show the relation between linear arithmetic circuits and BaseConv . We recall a few definitions from [ Dao et al., 2020 ] .

###### Definition H.13 (Linear Arithmetic Circuit [ Bürgisser et al., 1996 ] ) .

An arithmetic circuit is called a linear arithmetic circuit if it only uses addition, subtraction and scalar multiplication. Further, every multiplication has a fixed constant from 𝔽 \mathbbm{F} as at least one of its two inputs. In other words, all gates in the circuit are linear functions of their inputs (i.e. of the form a ​ x + b ​ y ax+by for fixed constants a , b ∈ 𝔽 a,b\in\mathbbm{F} ).

###### Definition H.14 (Butterfly Matrices [ Dao et al., 2020 ] ) .

A butterfly factor of size k ≥ 2 k\geq 2 (denoted as 𝐁 k \mathbf{B}_{k} ) is a matrix of the form 𝐁 k = \mathbf{B}_{k}= [ 𝐃 1 𝐃 2 𝐃 3 𝐃 4 ] \left[\begin{array}[]{ll}\mathbf{D}_{1}&\mathbf{D}_{2}\\ \mathbf{D}_{3}&\mathbf{D}_{4}\end{array}\right] where each 𝐃 i \mathbf{D}_{i} is a k 2 × k 2 \frac{k}{2}\times\frac{k}{2} diagonal matrix. We restrict k k to be a power of 2 .

A butterfly factor matrix of size n n with block size k k (denoted as 𝐁 k ( n ) \mathbf{B}_{k}^{(n)} ) is a block diagonal matrix of n k \frac{n}{k} (possibly different) butterfly factors of size k k : 𝐁 k ( n ) = diag ⁡ ( [ 𝐁 k ] 1 , [ 𝐁 k ] 2 , … , [ 𝐁 k ] n k ) \mathbf{B}_{k}^{(n)}=\operatorname{diag}\left(\left[\mathbf{B}_{k}\right]_{1},\left[\mathbf{B}_{k}\right]_{2},\ldots,\left[\mathbf{B}_{k}\right]_{\frac{n}{k}}\right) Finally, a butterfly matrix of size n n (denoted as 𝐁 ( n ) \mathbf{B}^{(n)} ) is a matrix that can be expressed as a product of butterfly factor matrices: 𝐁 ( n ) = 𝐁 n ( n ) ​ 𝐁 n 2 ( n ) ​ … ​ 𝐁 2 ( n ) \mathbf{B}^{(n)}=\mathbf{B}_{n}^{(n)}\mathbf{B}_{\frac{n}{2}}^{(n)}\ldots\mathbf{B}_{2}^{(n)} . Equivalently, we may define 𝐁 ( n ) \mathbf{B}^{(n)} recursively as a matrix that can be expressed in the following form: 𝐁 ( n ) = 𝐁 n ( n ) ​ [ [ 𝐁 ( n 2 ) ] 1 0 0 [ 𝐁 ( n 2 ) ] 2 ] \mathbf{B}^{(n)}=\mathbf{B}_{n}^{(n)}\left[\begin{array}[]{cc}{\left[\mathbf{B}^{\left(\frac{n}{2}\right)}\right]_{1}}&0\\ 0&{\left[\mathbf{B}^{\left(\frac{n}{2}\right)}\right]_{2}}\end{array}\right] (Note that [ 𝐁 ( n 2 ) ] 1 \left[\mathbf{B}^{\left(\frac{n}{2}\right)}\right]_{1} and [ 𝐁 ( n 2 ) ] 2 \left[\mathbf{B}^{\left(\frac{n}{2}\right)}\right]_{2} may be different.)

From Definition H.14 , we observe that size n n butterfly factor is comprised of three vectors 𝒅 , 𝒅 + , 𝒅 − ∈ ℝ n \bm{d,d^{+},d^{-}}\in\mathbbm{R}^{n} such that 𝒅 \displaystyle\bm{d} = ( diag − 1 ⁡ ( 𝐃 1 ) , diag − 1 ⁡ ( 𝐃 4 ) ) , \displaystyle=\left(\operatorname{diag}^{-1}\left({\bf D}_{1}\right),\operatorname{diag}^{-1}\left({\bf D}_{4}\right)\right), 𝒅 + \displaystyle\bm{d}^{+} = ( 𝟎 n 2 , diag − 1 ⁡ ( 𝐃 2 ) ) , and \displaystyle=\left(\bm{0}^{\tfrac{n}{2}},\operatorname{diag}^{-1}\left({\bf D}_{2}\right)\right),\text{ and } 𝒅 − \displaystyle\bm{d}^{-} = ( diag − 1 ⁡ ( 𝐃 3 ) , 𝟎 n 2 ) , \displaystyle=\left(\operatorname{diag}^{-1}\left({\bf D}_{3}\right),\bm{0}^{\tfrac{n}{2}}\right),

where diag − 1 ⁡ ( 𝐃 ) : ℝ n × n ↦ ℝ n \operatorname{diag}^{-1}({\bf D}):\mathbbm{R}^{n\times n}\mapsto\mathbbm{R}^{n} is the mapping from diagonal matrices to the vector of its diagonal entries. Let us define 𝐃 𝟏 , 𝐃 𝟐 , 𝐃 𝟑 ∈ ℝ n × n {\bf D_{1},D_{2},D_{3}}\in\mathbbm{R}^{n\times n} as diag ⁡ ( 𝒅 ) , diag ⁡ ( 𝒅 + ) \operatorname{diag}\left(\bm{d}\right),\operatorname{diag}\left(\bm{d^{+}}\right) , and diag ⁡ ( 𝒅 − ) \operatorname{diag}\left(\bm{d^{-}}\right) respectively. Then we note that

𝐃 1 ≡ [ 𝐃 1 𝟎 𝟎 𝐃 4 ] 𝐃 2 ​ 𝑺 n 2 ≡ [ 𝟎 𝐃 2 𝟎 𝟎 ] 𝑺 n 2 ​ 𝐃 3 ≡ [ 𝟎 𝟎 𝐃 3 𝟎 ] {\bf D}_{1}\equiv\left[\begin{array}[]{ll}\mathbf{D}_{1}&\mathbf{0}\\ \mathbf{0}&\mathbf{D}_{4}\end{array}\right]\qquad{\bf D}_{2}\bm{S}^{\tfrac{n}{2}}\equiv\left[\begin{array}[]{ll}\mathbf{0}&\mathbf{D}_{2}\\ \mathbf{0}&\mathbf{0}\end{array}\right]\qquad\bm{S}^{\tfrac{n}{2}}{\bf D}_{3}\equiv\left[\begin{array}[]{ll}\mathbf{0}&\mathbf{0}\\ \mathbf{D}_{3}&\mathbf{0}\end{array}\right] (5)

where 𝐒 k ∈ 𝔽 n × n {\bf S}^{k}\in\mathbbm{F}^{n\times n} is a shift matrix for i ∈ [ n / 2 ] i\in[n/2] . This gives us the following proposition:

###### Proposition H.15 .

For any powers of 2, n = k ≥ 2 n=k\geq 2 , any butterfly factor matrix 𝐁 k ( n ) {\bf B}^{(n)}_{k} is equivalent to 𝐁 k ( n ) = 𝐒 k 2 ​ 𝐃 3 + 𝐃 2 ​ 𝐒 n 2 + 𝐃 1 {\bf B}^{(n)}_{k}={\bf S}^{\tfrac{k}{2}}{\bf D}_{3}+{\bf D}_{2}{\bf S}^{\tfrac{n}{2}}+{\bf D}_{1} where 𝐃 𝟑 , 𝐃 𝟐 , 𝐃 𝟏 , 𝐒 𝐧 𝟐 {\bf D_{3},D_{2},D_{1},S^{\frac{n}{2}}} are defined as in equation 5 .

We use Proposition H.15 to show that butterfly matrices can easily be computed by BaseConv .

###### Lemma H.16 .

For any n , d ≥ 2 n,d\geq 2 , k ≥ 1 k\geq 1 , and arbitrary vector 𝐱 ∈ ℝ n ​ d \bm{x}\in\mathbbm{R}^{nd} : (1) there exists a ( N , L , d , N ′ , d ′ ) − BaseConv \left(N,L,d,N^{\prime},d^{\prime}\right)-\text{{BaseConv}} that can represent 𝐁 k ( n ​ d ) ⋅ 𝒙 {\bf B}^{(nd)}_{k}\cdot\bm{x} with N = n , N ′ = 𝒪 ⁡ ( N ) N=n,N^{\prime}=\mathcal{O}(N) , L = 𝒪 ⁡ ( 1 ) L=\mathcal{O}(1) , and d ′ = 𝒪 ⁡ ( d ) d^{\prime}=\mathcal{O}(d) , and

(2) there exists a ( N , L , d , N ′ , d ′ ) − BaseConv \left(N,L,d,N^{\prime},d^{\prime}\right)-\text{{BaseConv}} that can represent 𝐁 ( n ​ d ) ⋅ 𝒙 {\bf B}^{(nd)}\cdot\bm{x} with N = n , N ′ = 𝒪 ⁡ ( N ) N=n,N^{\prime}=\mathcal{O}(N) , L = 𝒪 ⁡ ( log ⁡ n ​ d ) L=\mathcal{O}(\log nd) , and d ′ = 𝒪 ⁡ ( d ) d^{\prime}=\mathcal{O}(d) .

###### Proof.

(1) Given 𝒙 ∈ ℝ n ​ d \bm{x}\in\mathbbm{R}^{nd} , construct 𝒖 ∈ ℝ n × d \bm{u}\in\mathbbm{R}^{n\times d} where 𝒙 \bm{x} is the row-major form of 𝒖 \bm{u} . We show that BaseConv can compute 𝐁 n ​ d ⋅ 𝒙 {\bf B}_{nd}\cdot\bm{x} column by column.

Let 𝐀 = 𝐒 k 2 ​ 𝐃 3 ′ , 𝐂 = 𝐃 2 ′ ​ 𝐒 n 2 {\bf A}={\bf S}^{\tfrac{k}{2}}{\bf D}^{\prime}_{3},{\bf C}={\bf D}^{\prime}_{2}{\bf S}^{\tfrac{n}{2}} , and 𝐃 = 𝐃 1 {\bf D}={\bf D}_{1} for 𝐃 i , 𝐒 k 2 ∈ ℝ n ​ d × n ​ d {\bf D}_{i},{\bf S}^{\tfrac{k}{2}}\in\mathbbm{R}^{nd\times nd} for 1 ≤ i ≤ 3 1\leq i\leq 3 as defined in Proposition H.15 . We take 𝒅 1 = 𝟏 n ​ d ​ 𝐃 , 𝒅 2 = 𝟏 n ​ d ​ 𝐂 2 , 𝒅 3 = 𝟏 n ​ d ​ 𝐀 \bm{d}_{1}=\bm{1}^{nd}{\bf D},\ \bm{d}_{2}=\bm{1}^{nd}{\bf C}_{2},\bm{d}_{3}=\bm{1}^{nd}{\bf A} , which extracts the diagonal entries of 𝐃 i {\bf D}_{i} . With this we construct 𝐃 i ′ ∈ ℝ n × d {\bf D}^{\prime}_{i}\in\mathbbm{R}^{n\times d} where 𝒅 i \bm{d}_{i} is the row major form of 𝑫 i ′ \bm{D}^{\prime}_{i} . This implies that 𝐃 i ​ 𝒙 ≡ 𝐃 i ′ ⊙ 𝒖 . {\bf D}_{i}\bm{x}\equiv{\bf D}^{\prime}_{i}\odot\bm{u}.

Then we can decompose 𝐁 n ​ d ⋅ 𝒙 {\bf B}_{nd}\cdot\bm{x} into 𝐁 n ​ d ​ 𝒙 ≡ 𝐃 1 ⊙ 𝒖 + 𝐃 2 ⊙ 𝒖 + 𝐃 3 ⊙ 𝒖 . {\bf B}_{nd}\bm{x}\equiv{\bf D}_{1}\odot\bm{u}+{\bf D}_{2}\odot\bm{u}+{\bf D}_{3}\odot\bm{u}.

By Lemma H.7 , each Hadamard product 𝐀 ⊙ 𝒖 , 𝐁 ⊙ 𝒖 , 𝐂 ⊙ 𝒖 {\bf A}\odot\bm{u},{\bf B}\odot\bm{u},{\bf C}\odot\bm{u} can be trivially be performed with a single layer BaseConv model. Let each of these model outputs be denoted 𝒚 𝟏 , 𝒚 𝟐 , 𝒚 𝟑 \bm{y_{1},y_{2},y_{3}} , respectively. Finally all that remains is to compute the 𝒚 𝟏 + 𝒚 𝟐 + 𝒚 𝟑 \bm{y_{1}+y_{2}+y_{3}} . We achieve this using layers of add primitives 11 11 11 Recall that add n ( 𝒚 : 𝒙 , 𝑺 ) \texttt{add}_{n}(\bm{y}:\bm{x},\bm{S}) adds the subvector 𝒙 \bm{x} to 𝑺 \bm{S} for the input 𝒚 \bm{y} . : add n ( 𝒚 1 : 𝒚 1 , 𝟎 ) \displaystyle\texttt{add}_{n}(\bm{y}^{1}:\bm{y}_{1},\bm{0}) add n ( 𝒚 2 : 𝒚 2 , 𝒚 1 ) \displaystyle\texttt{add}_{n}(\bm{y}^{2}:\bm{y}_{2},\bm{y}_{1}) add n ( 𝒚 3 : 𝒚 3 , 𝒚 1 + 𝒚 2 ) , \displaystyle\texttt{add}_{n}(\bm{y}^{3}:\bm{y}_{3},\bm{y}_{1}+\bm{y}_{2}), where using by Proposition H.9 and Lemma H.11 , this requires six more layers, and we get 𝒚 3 ≡ 𝒚 𝟏 + 𝒚 𝟐 + 𝒚 𝟑 ≡ 𝐁 n ​ d ​ 𝒙 . \bm{y}^{3}\equiv\bm{y_{1}+y_{2}+y_{3}}\equiv{\bf B}_{nd}\bm{x}. Then we can construct the ( N , L , d , N ′ , d ′ ) − BaseConv \left(N,L,d,N^{\prime},d^{\prime}\right)-\text{{BaseConv}} as desired with L = O ⁡ ( 1 ) L=O(1) layers.

(2) From Definition H.14 , 𝐁 ( n ​ d ) = 𝐁 n ​ d ( n ​ d ) ​ 𝐁 n ​ d 2 ( n ​ d ) ​ … ​ 𝐁 2 ( n ​ d ) \mathbf{B}^{(nd)}=\mathbf{B}_{nd}^{(nd)}\mathbf{B}_{\frac{nd}{2}}^{(nd)}\ldots\mathbf{B}_{2}^{(nd)} . From (1), BaseConv can compute any butterfly matrix by simulating the log ⁡ ( n ​ d ) \log(nd) butterfly factor matrices which comprise 𝐁 ( n ​ d ) \mathbf{B}^{(nd)} . With Lemma H.11 , this creates a BaseConv with 5 ⋅ log ⁡ ( n ​ d ) = 𝒪 ⁡ ( log ⁡ ( n ​ d ) ) 5\cdot\log(nd)=\mathcal{O}(\log(nd)) layers. Lemma H.11

∎

Butterfly matrices comprise the kaleidoscope hierarchy, which we define below:

###### Definition H.17 (The Kaleidoscope Hierarchy [ Dao et al., 2020 ] ) .

• Define ℬ \mathcal{B} as the set of all matrices that can be expressed in the form 𝐁 ( n ) {\bf B}^{(n)} (for some n n ).

• Define ( ℬℬ ∗ ) \left(\cal{BB}^{*}\right) as the set of matrices 𝐌 {\bf M} of the form 𝐌 = 𝐌 1 ​ 𝐌 2 ∗ {\bf M}={\bf M}_{1}{\bf M}_{2}^{*} for some 𝐌 𝟏 , 𝐌 2 ∈ ℬ {\bf M_{1}},{\bf M}_{2}\in\mathcal{B} .

• Define ( ℬℬ ∗ ) w \left(\cal{BB}^{*}\right)^{w} as the set of matrices 𝐌 {\bf M} that can be expressed as 𝐌 = 𝐌 w ​ … ​ 𝐌 2 ​ 𝐌 1 {\bf M}={\bf M}_{w}\ldots{\bf M}_{2}{\bf M}_{1} , with each 𝐌 i ∈ ( ℬℬ ∗ ) ​ ( 1 ≤ i ≤ w ) . {\bf M}_{i}\in\left(\cal{BB}^{*}\right)(1\leq i\leq w). (The notation w w represents width.)

• Define ( ℬℬ ∗ ) e w \left(\cal{BB}^{*}\right)^{w}_{e} as the set of n × n n\times n matrices 𝐌 {\bf M} that can be expressed as 𝐌 = 𝐒𝐄𝐒 ⊤ {\bf M}={\bf SES}^{\top} for some e ​ n × e ​ n en\times en matrix 𝐄 ∈ ( ℬℬ ∗ ) w {\bf E}\in\left(\cal{BB}^{*}\right)^{w} , where 𝐒 ∈ 𝔽 n × e ​ n = [ 𝐈 n 0 … 0 ] ] {\bf S}\in\mathbbm{F}^{n\times en}=\begin{bmatrix}{\bf I}_{n}&0&\ldots&0\end{bmatrix}] (i.e. 𝐌 {\bf M} is the upper-left corner of 𝐄 {\bf E} ). (The notation e e represents expansion relative to n n .)

We similarly show how BaseConv can simulate any kaleidoscope matrix.

###### Lemma H.18 .

Given n , d ≥ 2 n,d\geq 2 , e > 0 e>0 for any n ​ d × n ​ d nd\times nd matrix 𝐌 ∈ ( ℬℬ ∗ ) e w {\bf M}\in\left(\cal{BB}^{*}\right)^{w}_{e} , and 𝐱 ∈ ℝ n ​ d \bm{x}\in\mathbbm{R}^{nd} there exists a ( N , L , d , N ′ , d ′ ) − BaseConv \left(N,L,d,N^{\prime},d^{\prime}\right)-\text{{BaseConv}} that can represent 𝐌 ⋅ 𝐱 {\bf M}\cdot\bm{x} with N = n , L = 𝒪 ⁡ ( w ​ log ⁡ ( e ​ n ​ d ) ) N=n,L=\mathcal{O}(w\log(end)) , N ′ = e ​ n , N^{\prime}=en, and d ′ = d \ d^{\prime}=d .

###### Proof.

By Definition H.17 , 𝐌 {\bf M} can be decomposed with respect to size e ​ n ​ d × e ​ n ​ d end\times end matrix 𝐄 = 𝐄 1 ⋅ 𝐄 2 ⋯ 𝐄 w . {\bf E}={\bf E}_{1}\cdot{\bf E}_{2}\cdots{\bf E}_{w}.