ITERATIVE PROJECTION STRATEGIES FOR THE LEAST-SQUARES FITTING OF TREE-STRUCTURES TO PROXIMITY DATA

A least squares optimization strategy is first reviewed and applied to the task of fitting a given collection of symmetric proximity values defined between the objects from one set by a collection of reconstruc ted proximity values, satisfying a fixed set of constraints, generated from some specified graph-theoretic structure, such as an ultrametric or an additive tree, selected for representing the objects. Our metho d uses iterative projection on to closed convex sets defined by the co llection of given constraints characterizing the structural representa tion specified, and in contrast to least squares optimization methods that impose such constraints through the use of penalty functions, avo ids the use of the latter, as well as the implementation of any gradie nt-based optimization technique. Secondly, just as various penalty-fun ction/gradient-based optimization techniques have been turned into heu ristic search strategies for such particular structures of interest as ultrametrics or additive trees, the use of iterative projection is su ggested as a general heuristic search strategy for locating the best s tructural representations to impose in the first place, where the coll ection of constraints used may vary over the course of the optimizatio n process. Our evaluation of the expected results uses several data se ts previously analysed in the literature. Finally, several other appli cations of iterative projection as a heuristic optimization technique are discussed, including the consideration of data beyond that of a si ngle symmetric proximity matrix (for example, extensions to two-mode p roximity matrices, i.e. between two distinct object sets, and to three -way proximity matrices either symmetric or not), and to representatio ns based on sums of matrices where each is constrained separately to c onform to some desired representational structure.