{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T20:54:42Z","timestamp":1762376082228,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,5,5]],"date-time":"2016-05-05T00:00:00Z","timestamp":1462406400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Microsoft Research Asia Collaborative Research funding"},{"name":"Scientific Research Common Program of Beijing Municipal Commission of Education","award":["KM201610025013"],"award-info":[{"award-number":["KM201610025013"]}]},{"name":"JSPS KAKENHI","award":["26280086 and 26120524"],"award-info":[{"award-number":["26280086 and 26120524"]}]},{"name":"Okawa Foundation Research Grant","award":["2015CB351800, NSFC-61272027, NSFC-61231010, NSFC-61527804, NSFC-61421062, NSFC-61210005"],"award-info":[{"award-number":["2015CB351800, NSFC-61272027, NSFC-61231010, NSFC-61527804, NSFC-61421062, NSFC-61210005"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2016,7,14]]},"abstract":"<jats:p>\n            Generalized fused lasso (GFL) penalizes variables with\n            <jats:italic>l<\/jats:italic>\n            <jats:sup>1<\/jats:sup>\n            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\u00e1sz 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\u2019s 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.\n          <\/jats:p>","DOI":"10.1145\/2847421","type":"journal-article","created":{"date-parts":[[2016,5,6]],"date-time":"2016-05-06T12:59:12Z","timestamp":1462539552000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Efficient Generalized Fused Lasso and Its Applications"],"prefix":"10.1145","volume":"7","author":[{"given":"Bo","family":"Xin","sequence":"first","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshinobu","family":"Kawahara","sequence":"additional","affiliation":[{"name":"Osaka University, Osaka, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yizhou","family":"Wang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lingjing","family":"Hu","sequence":"additional","affiliation":[{"name":"Capital Medical University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen","family":"Gao","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,5,5]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_2_1_1","DOI":"10.1109\/TSP.2006.881199"},{"doi-asserted-by":"publisher","key":"e_1_2_2_2_1","DOI":"10.1016\/j.neuroimage.2007.07.007"},{"volume-title":"Advances in Neural Information Processing Systems (NIPS\u201910).","author":"Bach F.","unstructured":"F. Bach . 2010. Structured sparsity-inducing norms through submodular functions . In Advances in Neural Information Processing Systems (NIPS\u201910). Vol. 23 . 118--126. F. Bach. 2010. Structured sparsity-inducing norms through submodular functions. In Advances in Neural Information Processing Systems (NIPS\u201910). Vol. 23. 118--126.","key":"e_1_2_2_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_4_1","DOI":"10.1561\/2200000015"},{"doi-asserted-by":"publisher","key":"e_1_2_2_5_1","DOI":"10.1109\/TIP.2010.2101613"},{"doi-asserted-by":"publisher","key":"e_1_2_2_6_1","DOI":"10.1137\/080716542"},{"volume-title":"Convex Optimization","author":"Boyd Stephen Poythress","unstructured":"Stephen Poythress Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press . Stephen Poythress Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.","key":"e_1_2_2_7_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_8_1","DOI":"10.1007\/s11263-006-7934-5"},{"doi-asserted-by":"publisher","key":"e_1_2_2_9_1","DOI":"10.1109\/CVPR.2011.5995508"},{"doi-asserted-by":"publisher","key":"e_1_2_2_10_1","DOI":"10.1145\/1970392.1970395"},{"doi-asserted-by":"publisher","key":"e_1_2_2_11_1","DOI":"10.1109\/TIT.2005.862083"},{"doi-asserted-by":"publisher","key":"e_1_2_2_12_1","DOI":"10.1007\/s11263-009-0238-9"},{"doi-asserted-by":"publisher","key":"e_1_2_2_13_1","DOI":"10.1137\/S1064827596304010"},{"doi-asserted-by":"publisher","key":"e_1_2_2_14_1","DOI":"10.1007\/978-3-642-33415-3_11"},{"doi-asserted-by":"publisher","key":"e_1_2_2_15_1","DOI":"10.1016\/j.neuroimage.2011.11.066"},{"doi-asserted-by":"publisher","key":"e_1_2_2_16_1","DOI":"10.1016\/j.neuroimage.2011.10.003"},{"doi-asserted-by":"publisher","key":"e_1_2_2_17_1","DOI":"10.1214\/07-AOAS131"},{"key":"e_1_2_2_18_1","volume-title":"Submodular Functions and Optimization","author":"Fujishige S.","unstructured":"S. Fujishige . 2005. Submodular Functions and Optimization ( 2 nd ed.). Elsevier . S. Fujishige. 2005. Submodular Functions and Optimization (2nd ed.). Elsevier.","edition":"2"},{"key":"e_1_2_2_19_1","volume-title":"Technical Report RIMS-1571. Research Institute for Mathematical Sciences","author":"Fujishige S.","year":"2006","unstructured":"S. Fujishige , T. Hayashi , and S. Isotani . 2006 . The Minimum-Norm-Point Algorithm Applied to Submodular Function Minimization and Linear Programming . Technical Report RIMS-1571. Research Institute for Mathematical Sciences , Kyoto University . S. Fujishige, T. Hayashi, and S. Isotani. 2006. The Minimum-Norm-Point Algorithm Applied to Submodular Function Minimization and Linear Programming. Technical Report RIMS-1571. Research Institute for Mathematical Sciences, Kyoto University."},{"doi-asserted-by":"publisher","key":"e_1_2_2_20_1","DOI":"10.1137\/0218003"},{"unstructured":"P. E. Gill W. Murray and M. A. Saunders. 1999. User\u2019s Guide for SNOPT 5.3: A Fortran Package for Large-scale Nonlinear Programming. Technical Report. University of California San Diego.  P. E. Gill W. Murray and M. A. Saunders. 1999. User\u2019s Guide for SNOPT 5.3: A Fortran Package for Large-scale Nonlinear Programming. Technical Report. University of California San Diego.","key":"e_1_2_2_21_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_22_1","DOI":"10.1137\/070706318"},{"key":"e_1_2_2_23_1","volume-title":"Retrieved","author":"Grant Michael","year":"2008","unstructured":"Michael Grant , Stephen Boyd , and Yinyu Ye . 2008 . CVX: Matlab Software for Disciplined Convex Programming . Retrieved March 12, 2016, from http:\/\/cvxr.com\/cvx\/. Michael Grant, Stephen Boyd, and Yinyu Ye. 2008. CVX: Matlab Software for Disciplined Convex Programming. Retrieved March 12, 2016, from http:\/\/cvxr.com\/cvx\/."},{"doi-asserted-by":"publisher","key":"e_1_2_2_24_1","DOI":"10.1007\/978-3-642-33765-9_8"},{"doi-asserted-by":"publisher","key":"e_1_2_2_25_1","DOI":"10.1007\/978-3-642-04697-1_4"},{"doi-asserted-by":"publisher","key":"e_1_2_2_26_1","DOI":"10.5555\/1953048.2078213"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the 2004 International Conference on Image Processing (ICIP\u201904)","volume":"5","author":"Kim Kyungnam","year":"2004","unstructured":"Kyungnam Kim , Thanarat H. Chalidabhongse , David Harwood , and Larry Davis . 2004 . Background modeling and subtraction by codebook construction . In Proceedings of the 2004 International Conference on Image Processing (ICIP\u201904) , Vol. 5 . IEEE, Los Alamitos, CA, 3061--3064. Kyungnam Kim, Thanarat H. Chalidabhongse, David Harwood, and Larry Davis. 2004. Background modeling and subtraction by codebook construction. In Proceedings of the 2004 International Conference on Image Processing (ICIP\u201904), Vol. 5. IEEE, Los Alamitos, CA, 3061--3064."},{"doi-asserted-by":"publisher","key":"e_1_2_2_28_1","DOI":"10.1109\/TPAMI.2004.1262177"},{"doi-asserted-by":"publisher","key":"e_1_2_2_29_1","DOI":"10.1109\/TIP.2004.836169"},{"key":"e_1_2_2_30_1","volume-title":"SLEP: Sparse Learning with Efficient Projections. Retrieved","author":"Liu J.","year":"2016","unstructured":"J. Liu , S. Ji , and J. Ye . 2009 . SLEP: Sparse Learning with Efficient Projections. Retrieved March 12, 2016 , from http:\/\/www.yelab.net\/software\/SLEP\/. J. Liu, S. Ji, and J. Ye. 2009. SLEP: Sparse Learning with Efficient Projections. Retrieved March 12, 2016, from http:\/\/www.yelab.net\/software\/SLEP\/."},{"doi-asserted-by":"publisher","key":"e_1_2_2_31_1","DOI":"10.1145\/1835804.1835847"},{"doi-asserted-by":"publisher","key":"e_1_2_2_32_1","DOI":"10.1109\/TIP.2008.924285"},{"doi-asserted-by":"publisher","key":"e_1_2_2_33_1","DOI":"10.5555\/1953048.2078191"},{"doi-asserted-by":"publisher","key":"e_1_2_2_34_1","DOI":"10.1007\/BF01215814"},{"doi-asserted-by":"publisher","key":"e_1_2_2_35_1","DOI":"10.1006\/cviu.2000.0870"},{"doi-asserted-by":"publisher","key":"e_1_2_2_36_1","DOI":"10.1007\/s13160-012-0083-z"},{"unstructured":"A. S. Nemirovsky and D. B. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons.  A. S. Nemirovsky and D. B. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons.","key":"e_1_2_2_37_1"},{"volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Nesterov Y.","unstructured":"Y. Nesterov . 2004. Introductory Lectures on Convex Optimization: A Basic Course . Springer . Y. Nesterov. 2004. Introductory Lectures on Convex Optimization: A Basic Course. Springer.","key":"e_1_2_2_38_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_39_1","DOI":"10.1109\/34.868684"},{"doi-asserted-by":"publisher","key":"e_1_2_2_40_1","DOI":"10.1007\/s10107-007-0189-2"},{"volume-title":"Introduction to Optimization. Optimization Software","author":"Pol\u00ebi\u00ecak B. T.","unstructured":"B. T. Pol\u00ebi\u00ecak . 1987. Introduction to Optimization. Optimization Software , Publications Division , New York, NY. B. T. Pol\u00ebi\u00ecak. 1987. Introduction to Optimization. Optimization Software, Publications Division, New York, NY.","key":"e_1_2_2_41_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_42_1","DOI":"10.1109\/CVPR.1999.784637"},{"doi-asserted-by":"publisher","key":"e_1_2_2_43_1","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"doi-asserted-by":"publisher","key":"e_1_2_2_44_1","DOI":"10.1111\/j.1467-9868.2005.00490.x"},{"doi-asserted-by":"publisher","key":"e_1_2_2_45_1","DOI":"10.1214\/11-AOS878"},{"doi-asserted-by":"publisher","key":"e_1_2_2_46_1","DOI":"10.1109\/ICCV.1999.791228"},{"key":"e_1_2_2_47_1","volume-title":"Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201912)","author":"Wan Jing","year":"2012","unstructured":"Jing Wan , Zhilin Zhang , Jingwen Yan , Taiyong Li , Bhaskar D. Rao , Shiaofen Fang , Sungeun Kim , Shannon L. Risacher , Andrew J. Saykin , and Li Shen . 2012 . Sparse Bayesian multi-task learning for predicting cognitive outcomes from neuroimaging measures in Alzheimer\u2019s disease . In Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201912) . IEEE, Los Alamitos, CA, 940--947. Jing Wan, Zhilin Zhang, Jingwen Yan, Taiyong Li, Bhaskar D. Rao, Shiaofen Fang, Sungeun Kim, Shannon L. Risacher, Andrew J. Saykin, and Li Shen. 2012. Sparse Bayesian multi-task learning for predicting cognitive outcomes from neuroimaging measures in Alzheimer\u2019s disease. In Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201912). IEEE, Los Alamitos, CA, 940--947."},{"doi-asserted-by":"publisher","key":"e_1_2_2_48_1","DOI":"10.1109\/TPAMI.2008.79"},{"key":"e_1_2_2_49_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence.","author":"Xin Bo","year":"2015","unstructured":"Bo Xin , Lingjing Hu , Yizhou Wang , and Wen Gao . 2015 a. Stable feature selection from brain sMRI . In Proceedings of the 29th AAAI Conference on Artificial Intelligence. Bo Xin, Lingjing Hu, Yizhou Wang, and Wen Gao. 2015a. Stable feature selection from brain sMRI. In Proceedings of the 29th AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_2_50_1","volume-title":"Proceedings of the 28th AAAI Conference on Artificial Intelligence. 2163--2169","author":"Xin Bo","year":"2014","unstructured":"Bo Xin , Yoshinobu Kawahara , Yizhou Wang , and Wen Gao . 2014 . Efficient generalized fused lasso and its application to the diagnosis of Alzheimers disease . In Proceedings of the 28th AAAI Conference on Artificial Intelligence. 2163--2169 . Bo Xin, Yoshinobu Kawahara, Yizhou Wang, and Wen Gao. 2014. Efficient generalized fused lasso and its application to the diagnosis of Alzheimers disease. In Proceedings of the 28th AAAI Conference on Artificial Intelligence. 2163--2169."},{"doi-asserted-by":"crossref","unstructured":"Bo Xin Yuan Tian Yizhou Wang and Wen Gao. 2015b. Background subtraction via generalized fused lasso foreground modeling. arXiv:1504.03707.  Bo Xin Yuan Tian Yizhou Wang and Wen Gao. 2015b. Background subtraction via generalized fused lasso foreground modeling. arXiv:1504.03707.","key":"e_1_2_2_51_1","DOI":"10.1109\/CVPR.2015.7299099"},{"doi-asserted-by":"publisher","key":"e_1_2_2_52_1","DOI":"10.1109\/ICCV.2013.419"},{"doi-asserted-by":"publisher","key":"e_1_2_2_53_1","DOI":"10.1145\/2020408.2020549"},{"doi-asserted-by":"publisher","key":"e_1_2_2_54_1","DOI":"10.1016\/j.patrec.2005.11.005"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847421","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2847421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:26Z","timestamp":1750225406000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,5]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,14]]}},"alternative-id":["10.1145\/2847421"],"URL":"https:\/\/doi.org\/10.1145\/2847421","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"type":"print","value":"2157-6904"},{"type":"electronic","value":"2157-6912"}],"subject":[],"published":{"date-parts":[[2016,5,5]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}