Efficient Generalized Fused Lasso and Its Applications
Efficient Generalized Fused Lasso and Its Applications
复制标题
DOI：
10.1145/2847421
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Bo Xin;Y. Kawahara;Yizhou Wang;Lingjing Hu;Wen Gao
中科院分区：
文献类型：
--
作者：
Bo Xin;Y. Kawahara;Yizhou Wang;Lingjing Hu;Wen Gao
广义融合套索（GFL）惩罚变量与l1范数的基础上的变量和他们的成对差异。GFL在应用于先验信息使用变量图表示的数据时很有用。然而，现有的GFL算法产生高的计算成本，并不扩展到高维问题。在这项研究中，我们提出了一个快速和可扩展的算法GFL。基于融合惩罚是切割函数的Lovász扩展这一事实，我们证明了优化的关键构建块等价于递归求解图切割问题。因此，我们使用一个参数流算法来解决GFL在一个有效的方式。与现有的GFL算法相比，该算法具有显著的加速比。此外，所提出的优化框架是非常普遍的，通过设计不同的切割函数，我们还讨论了GFL的扩展到有向图。利用所提出的算法的可扩展性，我们证明了我们的算法的应用程序阿尔茨海默氏病（AD）和视频背景减除（BS）的诊断。在AD问题中，我们将AD的诊断公式化为GFL正则化分类。我们的实验评估表明，诊断性能是有前途的。我们观察到，所选择的关键体素结构良好，即，连接，根据交叉验证是一致的，并且与先前的病理学知识一致。在BS问题中，GFL自然地对任意前景进行建模，而无需预定义的像素分组。即使通过应用简单的背景模型，例如，稀疏的线性组合的前帧，我们实现了国家的最先进的性能在几个公共数据集。
Generalized fused lasso (GFL) penalizes variables with l1 norms based both on the variables and their pairwise differences. GFL is useful when applied to data where prior information is expressed using a graph over the variables. However, the existing GFL algorithms incur high computational costs and do not scale to high-dimensional problems. In this study, we propose a fast and scalable algorithm for GFL. Based on the fact that fusion penalty is the Lovász extension of a cut function, we show that the key building block of the optimization is equivalent to recursively solving graph-cut problems. Thus, we use a parametric flow algorithm to solve GFL in an efficient manner. Runtime comparisons demonstrate a significant speedup compared to existing GFL algorithms. Moreover, the proposed optimization framework is very general; by designing different cut functions, we also discuss the extension of GFL to directed graphs. Exploiting the scalability of the proposed algorithm, we demonstrate the applications of our algorithm to the diagnosis of Alzheimer’s disease (AD) and video background subtraction (BS). In the AD problem, we formulated the diagnosis of AD as a GFL regularized classification. Our experimental evaluations demonstrated that the diagnosis performance was promising. We observed that the selected critical voxels were well structured, i.e., connected, consistent according to cross validation, and in agreement with prior pathological knowledge. In the BS problem, GFL naturally models arbitrary foregrounds without predefined grouping of the pixels. Even by applying simple background models, e.g., a sparse linear combination of former frames, we achieved state-of-the-art performance on several public datasets.