Completion of high-rank ultrametric matrices using selective entries

Ultrametric matrices are hierarchically structured matrices that arise naturally in many scenarios, e.g. delay covariance of packets sent from a source to a set of clients in a computer network, interactions between multi-scale communities in a social network, and genome sequence alignment scores in phylogenetic tree reconstruction problems. In this work, we show that it is possible to complete \(\)n\times n[\latex] ultrametric matrices using only \(\)n log^2(n)[\latex] entries. Since ultrametric matrices are high- rank matrices, our results extend recent work on completion of \(\) n \times n[\latex] low-rank matrices that requires \(\)n log(n)[\latex] randomly sampled entries. In the ultrametric setting, a random sampling of entries does not suffice, and we require selective sampling of entries using feedback obtained from entries observed at a previous stage.