On the Complexity of Sparse Label Propagation
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Authors
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Frontiers in Applied Mathematics and Statistics, Volume 4, pp. 1-7
Abstract
This paper investigates the computational complexity of sparse label propagation which has been proposed recently for processing network structured data. Sparse label propagation amounts to a convex optimization problem and might be considered as an extension of basis pursuit from sparse vectors to network structured datasets. Using a standard first-order oracle model, we characterize the number of iterations for sparse label propagation to achieve a prescribed accuracy. In particular, we derive an upper bound on the number of iterations required to achieve a certain accuracy and show that this upper bound is sharp for datasets having a chain structure (e.g., time series).Description
Keywords
Other note
Citation
Jung, A 2018, 'On the Complexity of Sparse Label Propagation', Frontiers in Applied Mathematics and Statistics, vol. 4, 22, pp. 1-7. https://doi.org/10.3389/fams.2018.00022