| \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} |
