source_extract/section-camera/method.tex

\section{PolyILR}

\begin{figure}[t]
    \centering
    \resizebox{0.48\textwidth}{!}{\input{figure/polyilr-construction}}
    \vspace{-10pt}
    \caption{\emph{PolyILR} from $\mathcal{T}$ on $d=6$ leaves to $V \in \mathbb{R}^{d\times(d-1)}$. Colors indicate generating nodes; white entries are zeros.}
    \vspace{-15pt}
    \label{fig:poly-construction}
\end{figure}

% We resolve this challenge by constructing an orthonormal decomposition of the Aitchison tangent space in \eqref{eq:main_tangent_clr} aligned with arbitrary trees. 
We describe the high-level idea in \S\ref{sec:intuition}, the formal construction in \S\ref{sec:construction}, and properties in \S\ref{sec:properties}. 

\vspace{-9.7pt}
\subsection{From Hierarchy to Geometry}\label{sec:intuition}

\textbf{Goal.} We seek an orthonormal decomposition of $\mathcal{H}$ reflecting the full branching structure of $\mathcal{T}$. We do not just want predictive log-ratios or useful balances, but a complete coordinate system where each coordinate corresponds to a location in $\mathcal{T}$. Such a basis must capture the full local structure at each node, maintain orthonormality within and across nodes, span $\mathcal{H}$, and be canonical. The first ensures complete encoding, the next two define a valid ILR basis in \eqref{eq:main_ilr_transform}. And the last one ensures reproducibility. It is not obvious such a construction exists.

\textbf{Key insight.} To address this, we (i) associate local geometric structure to each internal node and (ii) assemble them into global structure. We attach to each node a structured object encoding all relative comparisons among its children. The specific structure and canonicity follow from requiring the global basis to be a valid ILR basis and a deterministic choice of local basis. We make this precise in \S\ref{sec:construction}. 

\textbf{(i) Local structure.} Consider an internal node $u$ with $k_u$ children. The global basis will act on compositions, comparing leaves (via geometric mean) within each child clade. Since compositions carry only relative information (as in \S\ref{sec:background}), we encode relative differences among these $k_u$ clades and not absolute levels. This requires $k_u - 1$ degrees of freedom: one contrast distinguishes two children, two contrasts distinguish three, and so on. Each internal node thus contributes a $(k_u - 1)$-dimensional structure.

\textbf{(ii) Global assembly.} Local contrasts live at nodes, but ILR coordinates must be global vectors on leaves. We write a weighted inner product at each node to account for the number of descendant leaves in each child clade. Orthonormality under this weighted inner product (locally) guarantees global orthonormality in $\mathbb{R}^d$ after spreading to leaves.

We now formalize our construction, \textbf{PolyILR} (Figure~\ref{fig:poly-construction}).

\vspace{-5pt}
\subsection{PolyILR Construction}\label{sec:construction}

\textbf{Setup.} Let $\mathcal{T}$ be any rooted tree with $d$ leaves. Our data live in the Aitchison simplex $\Delta^{d-1}$, where each component corresponds to a leaf of $\mathcal{T}$. Our goal is to construct a valid ILR basis $V \in \mathbb{R}^{d \times (d-1)}$ such that each column of $V$ corresponds to a specific internal node of $\mathcal{T}$.

\textbf{Local contrast subspace.} Consider a node $u$ with $k_u$ children. We define the local contrast subspace at $u$ as
\begin{equation}
    \scalebox{0.9}{$\displaystyle S_u = \left\{ h \in \mathbb{R}^{k_u} : \sum_{r=1}^{k_u} h_r = 0 \right\}.$}
    \label{eq:main_local_contrast_space}
\end{equation}
This is the $(k_u - 1)$-dimensional subspace orthogonal to $\mathbf{1}$, capturing all relative comparisons among the $k_u$ children (see \S\ref{sec:intuition}). Notice that this zero-sum constraint is not arbitrary: it is, in fact, forced by the ILR requirement that $V^\top \mathbf{1} = 0$. Since each column of $V$ must be orthogonal to $\mathbf{1}$, and each column is formed by spreading a local vector $\mathbf{h}$ from node $u$, we require $\mathbf{h}^\top \mathbf{1} = 0$ locally.

\textbf{Weighted inner product.} To ensure that local orthonormality extends globally, we equip $S_u$ with a \emph{weighted inner product}. Let $n_r$ denote the number of leaves descending from child $r \in \{1,\dots,k_u\}$. We define:
\begin{equation}
    \langle h, h' \rangle_w = \sum_{r=1}^{k_u} \frac{h_r h'_r}{n_r}.
    \label{eq:main_weighted_inner_prod}
\end{equation}
This accounts for unequal subtree sizes: children with more descendants contribute less per leaf to the global inner product when spread. Note that $(S_u, \langle \cdot, \cdot \rangle_w)$ is a Hilbert space.

\textbf{Local basis.} We choose an orthonormal basis of $S_u$. Any orthonormal basis works mathematically, but we use Helmert contrasts \citep{lancaster1965helmert} {\color{black}for canonicity}. The standard Helmert matrix $H \in \mathbb{R}^{k \times (k-1)}$ has columns:
\begin{equation}
    H_{r,m} = \begin{cases}
    \sqrt{\frac{1}{m(m+1)}} & \text{if } r \leq m, \\
    -\sqrt{\frac{m}{m+1}} & \text{if } r = m+1, \\
    0 & \text{if } r > m+1.
    \end{cases}
    \label{eq:main_helmert}
\end{equation}
The $m$-th column compares child $m+1$ against the average of children $1, \ldots, m$. For example, with $k_u = 3$ children:
\[
H^{(u)} = \begin{pmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\[4pt]
-\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\[4pt]
0 & -\frac{2}{\sqrt{6}}
\end{pmatrix}.
\]
The first column contrasts child 2 versus child 1, the second contrasts child 3 versus the average of children 1 and 2. Helmert contrasts provide a canonical choice: given an ordering of children, the basis is deterministic. Alternative orthonormal bases of $S_u$ (e.g., QR decomposition) can also work but lack this sequential interpretability. 

Here, the columns of $H^{(u)}$ are orthonormal under the standard inner product and lie in $S_u$. To obtain orthonormality under $\langle \cdot, \cdot \rangle_w$, we apply Gram-Schmidt to $H^{(u)}$ under this weighted inner product, yielding $\widetilde{H}^{(u)} \in \mathbb{R}^{k_u \times (k_u - 1)}$. This choice ensures that given $\mathcal{T}$ and a fixed ordering of children at each node, the local basis is {\em uniquely} obtained. 

\begin{figure}[t]
    \centering
    \resizebox{0.45\textwidth}{!}{\input{figure/orthonormal-spread}}
    \vspace{-5pt}
    \caption{\emph{Naive vs.\ weighted spreading (Example~\ref{ex:spreading}).} Uniform spreading (Left) vs. Weighted spreading (Right)}
    \vspace{-15pt}
    \label{fig:orthonormal-spread}
\end{figure}

\vspace{-5pt}
\paragraph{Spreading to leaves.} Each column of the local basis $\widetilde{H}^{(u)}$ is a vector in $\mathbb{R}^{k_u}$, defined on the children of $u$. We spread it to a global vector $v \in \mathbb{R}^d$ on all leaves:
\[
v_i = \begin{cases} 
\widetilde{H}^{(u)}_{r,m} / n_r & \text{if leaf } i \text{ descends from child } r, \\ 
0 & \text{otherwise.} 
\end{cases}
\]
Division by $n_r$ is key, as it ensures that orthonormality under $\langle \cdot, \cdot \rangle_w$ at node $u$ implies orthonormality in $\mathbb{R}^d$ after spreading. Consider two local vectors $\mathbf{h}, \mathbf{h}'$ orthonormal under $\langle \cdot, \cdot \rangle_w$: $\sum_r h_r h'_r / n_r = \delta_{\mathbf{h},\mathbf{h}'}$. After spreading with the $1/n_r$ weighting, their global inner product becomes:
% \begin{align*}
% \langle \mathbf{v}, \mathbf{v}' \rangle 
% &= \sum_{i=1}^d v_i v'_i 
% = \sum_{r=1}^{k_u} \sum_{i \in C_r^{(u)}} \left(\frac{h_r}{n_r}\right)\left(\frac{h'_r}{n_r}\right) \\
% &= \sum_{r=1}^{k_u} \frac{h_r h'_r}{n_r^2} \cdot n_r 
% = \sum_{r=1}^{k_u} \frac{h_r h'_r}{n_r} 
% = \delta_{\mathbf{h},\mathbf{h}'},
% \end{align*}
{\small
\begin{align*}
\langle \mathbf{v}, \mathbf{v}' \rangle 
&= \sum_{i=1}^d v_i v'_i 
= \sum_{r=1}^{k_u} \sum_{i \in C_r^{(u)}} \left(\frac{h_r}{n_r}\right)\left(\frac{h'_r}{n_r}\right) \\
&= \sum_{r=1}^{k_u} \frac{h_r h'_r}{n_r^2} \cdot n_r 
= \sum_{r=1}^{k_u} \frac{h_r h'_r}{n_r} 
= \delta_{\mathbf{h},\mathbf{h}'},
\end{align*}
}
where the second equality holds because child $r$ contributes exactly $n_r$ leaves, each with coefficient $h_r/n_r$ (similarly for $\mathbf{h}'$). So, local orthonormality means global orthonormality. 

\vspace{5pt}
\begin{example}\label{ex:spreading}
Consider $u$ with two children $n_1 = 1$ and $n_2 = 3$. The Helmert contrast is $\mathbf{h} = (1/\sqrt{2}, -1/\sqrt{2})^\top$, which satisfies $\|\mathbf{h}\|_2^2 = 1$, but spreading uniformly gives $\mathbf{v} = (1/\sqrt{2}, -1/\sqrt{2}, -1/\sqrt{2}, -1/\sqrt{2})^\top$ with $\|\mathbf{v}\|^2 = 2 \neq 1$. The weighted norm in \eqref{eq:main_weighted_inner_prod} gives $\|\mathbf{h}\|_w^2 = (1/2)/1 + (1/2)/3 = 2/3$; normalizing gives $\tilde{\mathbf{h}} = [\sqrt{3}/2, -\sqrt{3}/2]^\top$. Spreading with $\div n_r$ yields $\|\mathbf{v}\|^2 = 1$. See Figure~\ref{fig:orthonormal-spread}.
\end{example}

\input{algorithm/polyilr_main}

\textbf{Assembling it all.} Applying this procedure at every internal node of $\mathcal{T}$ and collecting all spread vectors yields the PolyILR basis $V$. The columns of $V$ are indexed by pairs $(u, m)$ for some internal node $u$ and a contrast index $m \in \{1, \ldots, k_u - 1\}$. For example, if $\mathcal{T}$ has $\ell$ internal nodes ordered as $u_1, \ldots, u_\ell$, with $u_1$ having 4 children, $u_2$ having 3, $\ldots$, and $u_\ell$ having 3 children, then the basis is
\[
V = \bigl( \underbrace{v_1, v_2, v_3}_{\text{node } u_1}, \underbrace{v_4, v_5}_{\text{node } u_2}, \ldots, \underbrace{v_{d-2}, v_{d-1}}_{\text{node } u_\ell} \bigr).
\]
See Algorithm~\ref{alg:polyilr} and Figure~\ref{fig:poly-construction}.

\begin{theorem}[PolyILR]\label{thm:polyilr}
Let $\mathcal{T}$ be any rooted tree with $d$ leaves. The matrix $V \in \mathbb{R}^{d \times (d-1)}$ from Alg.~\ref{alg:polyilr} satisfies:
% \begin{enumerate}
%     \item $V^\top \mathbf{1} = 0$ \textup{(contrast property)},
%     \item $V^\top V = I_{d-1}$ \textup{(orthonormality)}.
% \end{enumerate}
\vspace{-5pt}
\begin{enumerate}
    \item \scalebox{0.95}{$V^\top \mathbf{1} = 0$} \textup{(contrast property)},
    \item \scalebox{0.95}{$V^\top V = I_{d-1}$} \textup{(orthonormality)}.
\end{enumerate}
\vspace{-5pt}
Consequently, $\varphi(x) = V^\top \log x$ is an isometry from $(\Delta^{d-1}, \langle \cdot, \cdot \rangle_A)$ to $(\mathbb{R}^{d-1}, \langle \cdot, \cdot \rangle_2)$.
\end{theorem}

\emph{Proof idea.} The contrast property follows from each local contrast summing to zero. For orthonormality: vectors from the same node are orthonormal by construction; disjoint nodes have disjoint support. Nested nodes (one ancestor of the other) are orthogonal because the descendant's spread vector sums to zero on each child clade. Full proof and algorithm details in Appendix~\ref{appdx:proof_algo}.

\textbf{Interpretation.} Given composition $x$, each coordinate $z_j = v_j^\top \log x$ is a \emph{balance}: a log-ratio comparing geometric means of child clades at an internal node. The transformation $z = V^\top \log x \in \mathbb{R}^{d-1}$ decomposes $x$ into interpretable contrasts at every level of the hierarchy, see \S\ref{sec:polyilr-analysis}.

\vspace{-5pt}
\subsection{Properties of PolyILR}\label{sec:properties}
% We now present several useful properties of PolyILR. 

\textbf{Relation to existing methods.} When $\mathcal{T}$ is binary ($k_u = 2$ for all $u$), each node contributes {\em one} contrast, and PolyILR reduces to PhILR (see Appendix~\ref{appdx:proof_algo}). Unlike greedy balance selection \citep{rivera2018balances} or edge-based factorization, which yield isolated contrasts, PolyILR provides a complete orthonormal basis aligned with the full tree. \emph{Unlike arbitrary binarization, PolyILR respects the original topology without introducing artificial splits} (Figure~\ref{fig:binary-vs-poly}).

\textbf{Uniqueness and recoverability.}
PolyILR provides a \emph{canonical} basis $V$ aligned with $\mathcal{T}$ as follows.
\begin{proposition}
Given a rooted tree $\mathcal{T}$ with fixed leaf labels and child orderings, PolyILR produces a unique basis $V(\mathcal{T})$. Moreover, $\mathcal{T} \mapsto V(\mathcal{T})$ is injective: $\mathcal{T}$ can be recovered from $V$ via the clade supports of its columns.
\label{prop:recovery}
\end{proposition}

{\color{black}
We point out that PolyILR's \emph{canonicity} rests on two structural conventions: (i) a child ordering at each internal node and (ii) a sign convention for the Helmert columns (first nonzero entry positive). These fix the representation but not the underlying geometry: different orderings yield bases related by an orthogonal transformation within each node's block (and permutations across blocks) where sign flips change the orientation of contrasts. In practice, the ordering is inherited from the input tree and held fixed. Full proofs are in Appendix~\ref{appdx:proof_algo}.}

\emph{Summary.} PolyILR provides a canonical, tree-aligned orthonormal coordinate system for the Aitchison simplex. Each coordinate corresponds to a contrast at a specific internal node, enabling interpretable analysis at any resolution.