source_extract/algorithm/polyilr_main.tex

\begin{algorithm}[bt]
\caption{PolyILR Basis Construction}
\label{alg:polyilr}
{\footnotesize
\begin{algorithmic}[1]
\REQUIRE Rooted $T$ with $d$ leaves, internal node ordering $\pi$ (DFS)
\ENSURE ILR basis $V \in \mathbb{R}^{d \times (d-1)}$
\STATE $j \leftarrow 1$
\FOR{each internal node $u$ from $\pi$}
    \STATE $k_u \leftarrow$ number of children of $u$
    \FOR{$r = 1, \ldots, k_u$}
        \STATE $C_u^{(r)} \leftarrow$ leaves descending from $r$-th child
        \STATE $n_r \leftarrow |C_u^{(r)}|$
    \ENDFOR
    \STATE $\mathcal{S}_u \leftarrow \{\mathbf{h} \in \mathbb{R}^{k_u} : \sum_r h_r = 0\}$
    \STATE $\langle \mathbf{h}, \mathbf{h}' \rangle_w \leftarrow \sum_r h_r h'_r / n_r$
    \STATE $H^{(u)} \leftarrow$ Helmert matrix in $\mathbb{R}^{k_u \times (k_u-1)}$
    \STATE $\widetilde{H}^{(u)} \leftarrow$ Gram-Schmidt on $H^{(u)}$ under $\langle \cdot, \cdot \rangle_w$
    \FOR{$m = 1, \ldots, k_u - 1$}
        \FOR{$i = 1, \ldots, d$}
            \IF{$i \in C_u^{(r)}$ for some $r$}
                \STATE $V_{i,j} \leftarrow \widetilde{H}^{(u)}_{r,m} / n_r$
            \ELSE
                \STATE $V_{i,j} \leftarrow 0$
            \ENDIF
        \ENDFOR
        \STATE $j \leftarrow j + 1$
    \ENDFOR
\ENDFOR
\STATE \textbf{return} $V$
\end{algorithmic}
}
\end{algorithm}