On the Complexity of Sparse Label Propagation

Frontiers in Applied Mathematics and Statistics

Jung, Alexander¹ 

[1] Department of Computer Science, Aalto University, Finland

关键词: graph signal processing;    Semi-Supervised Learning;    convex optimization;    compressed sensing;    Complexity;    complex networks;    big data;   

DOI  :  10.3389/fams.2018.00022

学科分类：数学（综合）

来源: Frontiers

【 摘 要 】

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

【 授权许可】

CC BY