On the Duality between Network Flows and Network Lasso
Many applications generate data with an intrinsic network structure such as time series data, image data or social network data. The network Lasso (nLasso) has been proposed recently as a method for joint clustering and optimization of machine learning models for networked data. The nLasso extends the Lasso from sparse linear models to clustered graph signals. This paper explores the duality of nLasso and network flow optimization. We show that, in a very precise sense, nLasso is equivalent to a minimum-cost flow problem on the data network structure. Our main technical result is a concise characterization of nLasso solutions via existence of certain network flows. The main conceptual result is a useful link between nLasso methods and basic graph algorithms such as clustering or maximum flow.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringTime SeriesTime Series AnalysisSimilar Papers 제목 키워드 기반
Formulating Beurling LASSO for Source Separation via Proximal Gradient Iteration
Beurling LASSO generalizes the LASSO problem to finite Radon measures regularized via their total variation. Despite its theoretical appeal, this space is hard to parametrize, which poses an algorithmic challenge. We pro…
Mind the duality gap: safer rules for the Lasso
Screening rules allow to early discard irrelevant variables from the optimization in Lasso problems, or its derivatives, making solvers faster. In this paper, we propose new versions of the so-called $\textit{safe rules}…
Local Graph Clustering with Network Lasso
We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and s…
ClusteringGraph ClusteringAnalysis of Network Lasso for Semi-Supervised Regression
We apply network Lasso to semi-supervised regression problems involving network structured data. This approach lends quite naturally to highly scalable learning algorithms in the form of message passing over an empirical…
ClusteringregressionStable Feature Selection from Brain sMRI
Neuroimage analysis usually involves learning thousands or even millions of variables using only a limited number of samples. In this regard, sparse models, e.g. the lasso, are applied to select the optimal features and …
feature selection