Least Squares Approximation of Additive Trees

Several authors have proposed procedures for fitting an additive tree to a distance, and some of them make use of the least squares principle, e.g. Sattath & Tversky (1977), Carroll & Pruzansky (1980) and de Soete (1983). However, a rigorous mathematical treatment of the underlying least squares approximation problem is missing. We start to fill this gap by considering the approximation problem for a fixed tree structure. We present a characterization of the unique solution based on the comparison of averages. Some conclusions from this characterization give a first insight to the general approximation problem with unknown tree structure. Let X be a finite set of objects. Following Buneman (1971), a tree structure on X can be represented by a system of compatible splits: Each edge of the tree structure is represented by a bipartition {A, Ac} of X, called a split, and two splits {A, Ac} and {B, BC} are called compatible, if A ⊆B ⋁ A ⊆ Bc ⋁ Ac ⊆ ⋁Ac ⊆ Bc holds (cp. fig. 1).