On The Complexity of Sparse Label Propagation
This work addresses the computational efficiency of sparse label propagation for network-structured data, which is incremental as it builds on existing convex optimization methods.
The paper investigates the computational complexity of sparse label propagation, deriving an upper bound on the number of iterations needed to achieve a prescribed accuracy and showing it is sharp for chain-structured datasets like time series.
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).