When Is Network Lasso Accurate?
Loading...
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
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2018
Major/Subject
Mcode
Degree programme
Language
en
Pages
1-11
Series
Frontiers in Applied Mathematics and Statistics, Volume 3
Abstract
The “least absolute shrinkage and selection operator” (Lasso) method has been adapted recently for networkstructured datasets. In particular, this network Lasso method allows to learn graph signals from a small number of noisy signal samples by using the total variation of a graph signal for regularization. While efficient and scalable implementations of the network Lasso are available, only little is known about the conditions on the underlying network structure which ensure network Lasso to be accurate. By leveraging concepts of compressed sensing, we address this gap and derive precise conditions on the underlying network topology and sampling set which guarantee the network Lasso for a particular loss function to deliver an accurate estimate of the entire underlying graph signal. We also quantify the error incurred by network Lasso in terms of two constants which reflect the connectivity of the sampled nodes.Description
Keywords
big data, compressed sensing, convex optimization, total variation regularization, machine learning, complex networks, network flow
Citation
Jung , A , Tran Quang , N & Mara , A 2018 , ' When Is Network Lasso Accurate? ' , Frontiers in Applied Mathematics and Statistics , vol. 3 , 28 , pp. 1-11 . https://doi.org/10.3389/fams.2017.00028
