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\) ultrametric matrices using only \(n log^2(n)\) entries. Since ultrametric matrices are high- rank matrices, our results extend recent work on completion of \( n \times n\) low-rank matrices that requires \(n log(n)\) 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.