On the Complexity of Sparse Label Propagation
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2018-07-01
|
| Series: | Frontiers in Applied Mathematics and Statistics |
| Subjects: | |
| Online Access: | https://www.frontiersin.org/article/10.3389/fams.2018.00022/full |
| _version_ | 1828337682689818624 |
|---|---|
| author | Alexander Jung |
| author_facet | Alexander Jung |
| author_sort | Alexander Jung |
| collection | DOAJ |
| description | 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 clustered graph signals representing the label information contained in 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). |
| first_indexed | 2024-04-13T22:18:22Z |
| format | Article |
| id | doaj.art-7a489aa1ad75467e8fb4ce4019438e31 |
| institution | Directory Open Access Journal |
| issn | 2297-4687 |
| language | English |
| last_indexed | 2024-04-13T22:18:22Z |
| publishDate | 2018-07-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Applied Mathematics and Statistics |
| spelling | doaj.art-7a489aa1ad75467e8fb4ce4019438e312022-12-22T02:27:22ZengFrontiers Media S.A.Frontiers in Applied Mathematics and Statistics2297-46872018-07-01410.3389/fams.2018.00022390046On the Complexity of Sparse Label PropagationAlexander JungThis 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 clustered graph signals representing the label information contained in 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).https://www.frontiersin.org/article/10.3389/fams.2018.00022/fullgraph signal processingsemi-supervised learningconvex optimizationcompressed sensingcomplexitycomplex networks |
| spellingShingle | Alexander Jung On the Complexity of Sparse Label Propagation Frontiers in Applied Mathematics and Statistics graph signal processing semi-supervised learning convex optimization compressed sensing complexity complex networks |
| title | On the Complexity of Sparse Label Propagation |
| title_full | On the Complexity of Sparse Label Propagation |
| title_fullStr | On the Complexity of Sparse Label Propagation |
| title_full_unstemmed | On the Complexity of Sparse Label Propagation |
| title_short | On the Complexity of Sparse Label Propagation |
| title_sort | on the complexity of sparse label propagation |
| topic | graph signal processing semi-supervised learning convex optimization compressed sensing complexity complex networks |
| url | https://www.frontiersin.org/article/10.3389/fams.2018.00022/full |
| work_keys_str_mv | AT alexanderjung onthecomplexityofsparselabelpropagation |