Semi-Supervised Learning in Network-Structured Data via Total Variation Minimization

Alex Jung, Alfred Hero, Alexandru Mara, Saeed Basirian Jahromi, Ayelet Heimowitz, Yonina C. Eldar

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

7 Sitaatiot (Scopus)

Abstrakti

We provide an analysis and interpretation of total variation (TV) minimization for semi-supervised learning from partially-labeled network-structured data. Our approach exploits an intrinsic duality between TV minimization and network flow problems. In particular, we use Fenchel duality to establish a precise equivalence of TV minimization and a minimum cost flow problem. This provides a link between modern convex optimization methods for non-smooth Lasso-Type problems and maximum flow algorithms. We show how a primal-dual method for TV minimization can be interpreted as distributed network optimization. Moreover, we derive a condition on the network structure and available label information that ensures that TV minimization accurately learns (approximately) piece-wise constant graph signals. This condition depends on the existence of sufficiently large network flows between labeled data points. We verify our analysis in numerical experiments.
AlkuperäiskieliEnglanti
Artikkeli8902040
Sivut6256-6269
Sivumäärä14
JulkaisuIEEE Transactions on Signal Processing
Vuosikerta67
Numero24
DOI - pysyväislinkit
TilaJulkaistu - 2019
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki

Sukella tutkimusaiheisiin 'Semi-Supervised Learning in Network-Structured Data via Total Variation Minimization'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä