On the properties of Gromov matrices and their applications in network inference

The spanning tree heuristic is a commonly adopted procedure in network inference and estimation. It allows one to generalize an inference method developed for trees, which is usually based on a statistically rigorous approach, to a heuristic procedure for general graphs by (usually randomly) choosin...

Full description

Saved in:
Bibliographic Details
Main Authors: Ji, Feng, Tang, Wenchang, Tay, Wee Peng
Other Authors: School of Electrical and Electronic Engineering
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/145422
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-145422
record_format dspace
spelling sg-ntu-dr.10356-1454222020-12-21T07:03:53Z On the properties of Gromov matrices and their applications in network inference Ji, Feng Tang, Wenchang Tay, Wee Peng School of Electrical and Electronic Engineering Engineering::Electrical and electronic engineering Gromov Matrix Spanning Tree The spanning tree heuristic is a commonly adopted procedure in network inference and estimation. It allows one to generalize an inference method developed for trees, which is usually based on a statistically rigorous approach, to a heuristic procedure for general graphs by (usually randomly) choosing a spanning tree in the graph to apply the approach developed for trees. However, there are an intractable number of spanning trees in a dense graph. In this paper, we represent a weighted tree with a matrix, which we call a Gromov matrix. We propose a method that constructs a family of Gromov matrices using convex combinations, which can be used for inference and estimation instead of a randomly selected spanning tree. This procedure increases the size of the candidate set and hence enhances the performance of the classical spanning tree heuristic. On the other hand, our new scheme is based on simple algebraic constructions using matrices, and hence is still computationally tractable. We discuss some applications on network inference and estimation to demonstrate the usefulness of the proposed method. Ministry of Education (MOE) Accepted version This work was supported by the Singapore Ministry of Education Academic Research Fund Tier 1 Grant 2017-T1-001-059 (RG20/17). 2020-12-21T07:03:52Z 2020-12-21T07:03:52Z 2019 Journal Article Ji, F., Tang, W., & Tay, W. P. (2019). On the properties of Gromov matrices and their applications in network inference. IEEE Transactions on Signal Processing, 67(10), 2624-2638. doi:10.1109/tsp.2019.2908133 1053-587X https://hdl.handle.net/10356/145422 10.1109/tsp.2019.2908133 10 67 2624 2638 en 2017-T1-001-059 (RG20/17) IEEE Transactions on Signal Processing © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/tsp.2019.2908133 application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Electrical and electronic engineering
Gromov Matrix
Spanning Tree
spellingShingle Engineering::Electrical and electronic engineering
Gromov Matrix
Spanning Tree
Ji, Feng
Tang, Wenchang
Tay, Wee Peng
On the properties of Gromov matrices and their applications in network inference
description The spanning tree heuristic is a commonly adopted procedure in network inference and estimation. It allows one to generalize an inference method developed for trees, which is usually based on a statistically rigorous approach, to a heuristic procedure for general graphs by (usually randomly) choosing a spanning tree in the graph to apply the approach developed for trees. However, there are an intractable number of spanning trees in a dense graph. In this paper, we represent a weighted tree with a matrix, which we call a Gromov matrix. We propose a method that constructs a family of Gromov matrices using convex combinations, which can be used for inference and estimation instead of a randomly selected spanning tree. This procedure increases the size of the candidate set and hence enhances the performance of the classical spanning tree heuristic. On the other hand, our new scheme is based on simple algebraic constructions using matrices, and hence is still computationally tractable. We discuss some applications on network inference and estimation to demonstrate the usefulness of the proposed method.
author2 School of Electrical and Electronic Engineering
author_facet School of Electrical and Electronic Engineering
Ji, Feng
Tang, Wenchang
Tay, Wee Peng
format Article
author Ji, Feng
Tang, Wenchang
Tay, Wee Peng
author_sort Ji, Feng
title On the properties of Gromov matrices and their applications in network inference
title_short On the properties of Gromov matrices and their applications in network inference
title_full On the properties of Gromov matrices and their applications in network inference
title_fullStr On the properties of Gromov matrices and their applications in network inference
title_full_unstemmed On the properties of Gromov matrices and their applications in network inference
title_sort on the properties of gromov matrices and their applications in network inference
publishDate 2020
url https://hdl.handle.net/10356/145422
_version_ 1688665467774828544