Completion of high-rank ultrametric matrices using selective entries

Aarti Singh, Akshay Krishnamurthy, Sivaraman Balakrishnan, Min Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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 x 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 x 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.

Original languageEnglish (US)
Title of host publication2012 International Conference on Signal Processing and Communications, SPCOM 2012
DOIs
StatePublished - 2012
Externally publishedYes
Event2012 9th International Conference on Signal Processing and Communications, SPCOM 2012 - Bangalore, India
Duration: Jul 22 2012Jul 25 2012

Publication series

Name2012 International Conference on Signal Processing and Communications, SPCOM 2012

Other

Other2012 9th International Conference on Signal Processing and Communications, SPCOM 2012
Country/TerritoryIndia
CityBangalore
Period7/22/127/25/12

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Communication

Fingerprint

Dive into the research topics of 'Completion of high-rank ultrametric matrices using selective entries'. Together they form a unique fingerprint.

Cite this