public lookup table
\(T \in \mathbb{F}^{m \times m}\)
\(T=\begin{bmatrix}1&0&0&…\\0&1&0&…\\0&0&1&…\\…&…&…&…\end{bmatrix}\)
the table to be looked up
\(M \in \mathbb{F}^{n \times m}\), the goal is to prove each row of \(M\) belongs to the rows of \(T\)
for example, \(M\) is as blow (to make it more intuitive to look at)
\(M=\begin{bmatrix}0&0&1&…\\1&0&0&…\\0&0&1&…\\…&…&…&…\end{bmatrix}\)
form a dense representation of \(M\), Index \(I (k)=j\) is a mapping from [0.. n-1] to [o.. m-1]
table \( I\)
\(I=\begin{bmatrix}0&2\\1&0\\2&2\\3&…\\…&…\end{bmatrix}\)
One can split table \(T\) by columns, each column as a individual indexed table \(T_{\mathsf{col}[j]}\), \(k \in {[0,…m-1]}\)
\(T_{\mathsf{col[0]}}=\begin{bmatrix}0&1\\1&0\\2&0\\3&0\\…&0\end{bmatrix}, T_{\mathsf{col[1]}}=\begin{bmatrix}0&0\\1&1\\2&0\\3&0\\…&0\end{bmatrix}, T_{\mathsf{col[2]}}=\begin{bmatrix}0&0\\1&0\\2&1\\3&0\\…&0\end{bmatrix}, …\)
now we can represent table \(M\) use logup* as
\(M=\begin{bmatrix}&&&\\T_{\mathsf{col}[0]}[I[k]]&T_{\mathsf{col}[1]}[I[k]]&T_{\mathsf{col}[2]}[I[k]]&…\\&&&\end{bmatrix}\)
\(k \in {[0,…n-1]}\)
namely
\(M(k,j)=T_{\mathsf{col}[j]}[I[k]]\)
\(\widetilde{M}(r_{row},j)=\sum\limits_{k\in \{0,1\}^{\log n}}\widetilde{eq}(r_{row},k)T_{\mathsf{col}[j]}[I[k]]\)
\(=<\widetilde{eq}_{r_{row}}, I^*T_{\mathsf{col}[j]}>=<{\widetilde{eq}_{r_{row}}}_{^*}I,T_{\mathsf{col}[j]}>\)
since when \(i \neq j: \)\(T_{\mathsf{col}[j]}[i]=0\)
\(\widetilde{M}(r_{row},j)={\widetilde{eq}_{r_{row}}}_{^*}I[j]\)
define the pushforward of \({\widetilde{eq}_{r_{row}}}\) and \(I\) as \(P\)
\(\widetilde{M}(r_{row},j)=\sum\limits_{I[k]=j} \widetilde{eq}(r_{row},k)=P(j)\)
compute the evaluation of the MLE of matrix \(M\)
\(\widetilde{M}(r_x,r_y)=\sum\limits_{j\in \{0,1\}^{\log m}} \widetilde{eq}(r_y,j) \cdot \widetilde{M}(r_{row},j)\)
\(=\sum\limits_{j\in \{0,1\}^{\log m}} \widetilde{eq}(r_y,j) \cdot P(j)\)
\(=\widetilde{P}(r_y)\)