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 Citations (Scopus)

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 - Oct 26 2012
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
CountryIndia
CityBangalore
Period7/22/127/25/12

Fingerprint

social network
reconstruction
scenario
interaction
community
Sampling
Computer networks
Genes
Feedback

All Science Journal Classification (ASJC) codes

  • Communication
  • Signal Processing

Cite this

Singh, A., Krishnamurthy, A., Balakrishnan, S., & Xu, M. (2012). Completion of high-rank ultrametric matrices using selective entries. In 2012 International Conference on Signal Processing and Communications, SPCOM 2012 [6290247] (2012 International Conference on Signal Processing and Communications, SPCOM 2012). https://doi.org/10.1109/SPCOM.2012.6290247
Singh, Aarti ; Krishnamurthy, Akshay ; Balakrishnan, Sivaraman ; Xu, Min. / Completion of high-rank ultrametric matrices using selective entries. 2012 International Conference on Signal Processing and Communications, SPCOM 2012. 2012. (2012 International Conference on Signal Processing and Communications, SPCOM 2012).
@inproceedings{e9bfa4af936d40b6837b24348fdbb744,
title = "Completion of high-rank ultrametric matrices using selective entries",
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.",
author = "Aarti Singh and Akshay Krishnamurthy and Sivaraman Balakrishnan and Min Xu",
year = "2012",
month = "10",
day = "26",
doi = "https://doi.org/10.1109/SPCOM.2012.6290247",
language = "English (US)",
isbn = "9781467320122",
series = "2012 International Conference on Signal Processing and Communications, SPCOM 2012",
booktitle = "2012 International Conference on Signal Processing and Communications, SPCOM 2012",

}

Singh, A, Krishnamurthy, A, Balakrishnan, S & Xu, M 2012, Completion of high-rank ultrametric matrices using selective entries. in 2012 International Conference on Signal Processing and Communications, SPCOM 2012., 6290247, 2012 International Conference on Signal Processing and Communications, SPCOM 2012, 2012 9th International Conference on Signal Processing and Communications, SPCOM 2012, Bangalore, India, 7/22/12. https://doi.org/10.1109/SPCOM.2012.6290247

Completion of high-rank ultrametric matrices using selective entries. / Singh, Aarti; Krishnamurthy, Akshay; Balakrishnan, Sivaraman; Xu, Min.

2012 International Conference on Signal Processing and Communications, SPCOM 2012. 2012. 6290247 (2012 International Conference on Signal Processing and Communications, SPCOM 2012).

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

TY - GEN

T1 - Completion of high-rank ultrametric matrices using selective entries

AU - Singh, Aarti

AU - Krishnamurthy, Akshay

AU - Balakrishnan, Sivaraman

AU - Xu, Min

PY - 2012/10/26

Y1 - 2012/10/26

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

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

UR - http://www.scopus.com/inward/record.url?scp=84867706989&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867706989&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/SPCOM.2012.6290247

DO - https://doi.org/10.1109/SPCOM.2012.6290247

M3 - Conference contribution

SN - 9781467320122

T3 - 2012 International Conference on Signal Processing and Communications, SPCOM 2012

BT - 2012 International Conference on Signal Processing and Communications, SPCOM 2012

ER -

Singh A, Krishnamurthy A, Balakrishnan S, Xu M. Completion of high-rank ultrametric matrices using selective entries. In 2012 International Conference on Signal Processing and Communications, SPCOM 2012. 2012. 6290247. (2012 International Conference on Signal Processing and Communications, SPCOM 2012). https://doi.org/10.1109/SPCOM.2012.6290247