Semi-supervised learning in network-structured data via total variation minimization
- Author
- Alexander Jung, Alfred O. Hero, Alexandru-Cristian Mara (UGent) , Saeed Jahromi, Ayelet Heimowitz and Yonina C. Eldar
- Organization
- Abstract
- 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.
- Keywords
- Signal Processing, Electrical and Electronic Engineering, Machine learning, semisupervised learning, optimization, big data applications, network theory (graphs), FLOW, RECOVERY, SIGNALS
Downloads
-
(...).pdf
- full text (Published version)
- |
- UGent only
- |
- |
- 815.18 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-8638002
- MLA
- Jung, Alexander, et al. “Semi-Supervised Learning in Network-Structured Data via Total Variation Minimization.” IEEE TRANSACTIONS ON SIGNAL PROCESSING, vol. 67, no. 24, 2019, pp. 6256–69, doi:10.1109/tsp.2019.2953593.
- APA
- Jung, A., Hero, A. O., Mara, A.-C., Jahromi, S., Heimowitz, A., & Eldar, Y. C. (2019). Semi-supervised learning in network-structured data via total variation minimization. IEEE TRANSACTIONS ON SIGNAL PROCESSING, 67(24), 6256–6269. https://doi.org/10.1109/tsp.2019.2953593
- Chicago author-date
- Jung, Alexander, Alfred O. Hero, Alexandru-Cristian Mara, Saeed Jahromi, Ayelet Heimowitz, and Yonina C. Eldar. 2019. “Semi-Supervised Learning in Network-Structured Data via Total Variation Minimization.” IEEE TRANSACTIONS ON SIGNAL PROCESSING 67 (24): 6256–69. https://doi.org/10.1109/tsp.2019.2953593.
- Chicago author-date (all authors)
- Jung, Alexander, Alfred O. Hero, Alexandru-Cristian Mara, Saeed Jahromi, Ayelet Heimowitz, and Yonina C. Eldar. 2019. “Semi-Supervised Learning in Network-Structured Data via Total Variation Minimization.” IEEE TRANSACTIONS ON SIGNAL PROCESSING 67 (24): 6256–6269. doi:10.1109/tsp.2019.2953593.
- Vancouver
- 1.Jung A, Hero AO, Mara A-C, Jahromi S, Heimowitz A, Eldar YC. Semi-supervised learning in network-structured data via total variation minimization. IEEE TRANSACTIONS ON SIGNAL PROCESSING. 2019;67(24):6256–69.
- IEEE
- [1]A. Jung, A. O. Hero, A.-C. Mara, S. Jahromi, A. Heimowitz, and Y. C. Eldar, “Semi-supervised learning in network-structured data via total variation minimization,” IEEE TRANSACTIONS ON SIGNAL PROCESSING, vol. 67, no. 24, pp. 6256–6269, 2019.
@article{8638002,
abstract = {{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.}},
author = {{Jung, Alexander and Hero, Alfred O. and Mara, Alexandru-Cristian and Jahromi, Saeed and Heimowitz, Ayelet and Eldar, Yonina C.}},
issn = {{1053-587X}},
journal = {{IEEE TRANSACTIONS ON SIGNAL PROCESSING}},
keywords = {{Signal Processing,Electrical and Electronic Engineering,Machine learning,semisupervised learning,optimization,big data applications,network theory (graphs),FLOW,RECOVERY,SIGNALS}},
language = {{eng}},
number = {{24}},
pages = {{6256--6269}},
title = {{Semi-supervised learning in network-structured data via total variation minimization}},
url = {{http://doi.org/10.1109/tsp.2019.2953593}},
volume = {{67}},
year = {{2019}},
}
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: