Completion of high-rank ultrametric matrices using selective entries - Singh, Aarti; Krishnamurthy, Akshay; Balakrishnan, Sivaraman; Xu, Min (International Conference on Signal Processing and Communication, 2012)
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× 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 × 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.