{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T03:06:33Z","timestamp":1772679993734,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Comput Vis"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s11263-020-01313-2","type":"journal-article","created":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T15:02:32Z","timestamp":1583334152000},"page":"1913-1936","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["MAP Inference Via $$\\ell _2$$-Sphere Linear Program Reformulation"],"prefix":"10.1007","volume":"128","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2183-5990","authenticated-orcid":false,"given":"Baoyuan","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5659-3464","authenticated-orcid":false,"given":"Li","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5511-2558","authenticated-orcid":false,"given":"Tong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5534-587X","authenticated-orcid":false,"given":"Bernard","family":"Ghanem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,4]]},"reference":[{"issue":"1\u20132","key":"1313_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10107-007-0133-5","volume":"116","author":"H Attouch","year":"2009","unstructured":"Attouch, H., & Bolte, J. (2009). On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116(1\u20132), 5\u201316.","journal-title":"Mathematical Programming"},{"issue":"2","key":"1313_CR2","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1287\/moor.1100.0449","volume":"35","author":"H Attouch","year":"2010","unstructured":"Attouch, H., Bolte, J., Redont, P., & Soubeyran, A. (2010). Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka\u2013Lojasiewicz inequality. Mathematics of Operations Research, 35(2), 438\u2013457.","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"1313_CR3","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1111\/j.2517-6161.1986.tb01412.x","volume":"48","author":"J Besag","year":"1986","unstructured":"Besag, J. (1986). On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society: Series B (Methodological), 48(3), 259\u2013279.","journal-title":"Journal of the Royal Statistical Society: Series B (Methodological)"},{"issue":"4","key":"1313_CR4","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1137\/050644641","volume":"17","author":"J Bolte","year":"2007","unstructured":"Bolte, J., Daniilidis, A., & Lewis, A. (2007). The \u0142ojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17(4), 1205\u20131223.","journal-title":"SIAM Journal on Optimization"},{"issue":"2","key":"1313_CR5","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1137\/060670080","volume":"18","author":"J Bolte","year":"2007","unstructured":"Bolte, J., Daniilidis, A., Lewis, A., & Shiota, M. (2007). Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18(2), 556\u2013572.","journal-title":"SIAM Journal on Optimization"},{"key":"1313_CR6","doi-asserted-by":"crossref","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends\u00ae in Machine Learning, 3(1), 1\u2013122.","DOI":"10.1561\/2200000016"},{"key":"1313_CR7","unstructured":"Elidan, G., Globerson, A., & Heinemann, U. (2012). Pascal 2011 probabilistic inference challenge. Retrieved July 15, 2020, from http:\/\/www.cs.huji.ac.il\/project\/PASCAL\/index.php."},{"key":"1313_CR8","unstructured":"Fu, Q., & Banerjee, H. W. A. (2013). Bethe-ADMM for tree decomposition based parallel map inference. In Uncertainty in artificial intelligence (p. 222). Citeseer."},{"key":"1313_CR9","unstructured":"Globerson, A., & Jaakkola, T. S. (2008). Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. In NIPS (pp. 553\u2013560)."},{"key":"1313_CR10","doi-asserted-by":"crossref","unstructured":"Gould, S., Fulton, R., & Koller, D. (2009). Decomposing a scene into geometric and semantically consistent regions. In ICCV (pp. 1\u20138). IEEE.","DOI":"10.1109\/ICCV.2009.5459211"},{"issue":"2","key":"1313_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1089\/cmb.2006.13.145","volume":"13","author":"A Jaimovich","year":"2006","unstructured":"Jaimovich, A., Elidan, G., Margalit, H., & Friedman, N. (2006). Towards an integrated protein\u2013protein interaction network: A relational markov network approach. Journal of Computational Biology, 13(2), 145\u2013164.","journal-title":"Journal of Computational Biology"},{"key":"1313_CR12","unstructured":"Johnson, J. K., Malioutov, D. M., & Willsky, A. S. (2007). Lagrangian relaxation for map estimation in graphical models. ArXiv preprint arXiv:0710.0013."},{"key":"1313_CR13","unstructured":"Jojic, V., Gould, S., Koller, D. (2010). Accelerated dual decomposition for map inference. In ICML (pp. 503\u2013510)."},{"key":"1313_CR14","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s11263-015-0809-x","volume":"115","author":"JH Kappes","year":"2015","unstructured":"Kappes, J. H., Andres, B., Hamprecht, F. A., Schn\u00f6rr, C., Nowozin, S., Batra, D., et al. (2015). A comparative study of modern inference techniques for structured discrete energy minimization problems. International Journal of Computer Vision, 115, 155\u2013184.","journal-title":"International Journal of Computer Vision"},{"key":"1313_CR15","doi-asserted-by":"crossref","unstructured":"Kappes, J. H., Savchynskyy, B., Schn\u00f6rr, C. (2012). A bundle approach to efficient map-inference by lagrangian relaxation. In CVPR (pp. 1688\u20131695). IEEE.","DOI":"10.1109\/CVPR.2012.6247863"},{"key":"1313_CR16","unstructured":"Karush, W. (1939). Minima of functions of several variables with inequalities as side constraints. M.Sc. Dissertation. Department of Mathematics, University of Chicago."},{"issue":"4","key":"1313_CR17","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0108053","volume":"8","author":"J Kelley","year":"1960","unstructured":"Kelley, J. (1960). The cutting-plane method for solving convex programs. Journal of the Society for Industrial and Applied Mathematics, 8(4), 703\u2013712.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"1313_CR18","volume-title":"Probabilistic graphical models: Principles and techniques","year":"2009","unstructured":"Koller, D., & Nir, F. (Eds.). (2009). Probabilistic graphical models: Principles and techniques. Cambridge, MA: MIT Press."},{"issue":"10","key":"1313_CR19","doi-asserted-by":"publisher","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","volume":"28","author":"V Kolmogorov","year":"2006","unstructured":"Kolmogorov, V. (2006). Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10), 1568\u20131583.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"1313_CR20","doi-asserted-by":"crossref","unstructured":"Komodakis, N., Paragios, N., & Tziritas, G. (2007) MRF optimization via dual decomposition: Message-passing revisited. In ICCV (pp. 1\u20138). IEEE.","DOI":"10.1109\/ICCV.2007.4408890"},{"issue":"2","key":"1313_CR21","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"FR Kschischang","year":"2001","unstructured":"Kschischang, F. R., Frey, B. J., & Loeliger, H. A. (2001). Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2), 498\u2013519.","journal-title":"IEEE Transactions on Information Theory"},{"key":"1313_CR22","doi-asserted-by":"crossref","unstructured":"Kuhn, H. W., & Tucker, A. W. (2014). Nonlinear programming. In Traces and emergence of nonlinear programming (pp. 247\u2013258). Springer.","DOI":"10.1007\/978-3-0348-0439-4_11"},{"key":"1313_CR23","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"AH Land","year":"1960","unstructured":"Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28, 497\u2013520.","journal-title":"Econometrica"},{"key":"1313_CR24","unstructured":"Laurent, M., & Rendl, F. (2002). Semidefinite programming and integer programming. Centrum voor Wiskunde en Informatica."},{"issue":"4","key":"1313_CR25","doi-asserted-by":"publisher","first-page":"2434","DOI":"10.1137\/140998135","volume":"25","author":"G Li","year":"2015","unstructured":"Li, G., & Pong, T. K. (2015). Global convergence of splitting methods for nonconvex composite optimization. SIAM Journal on Optimization, 25(4), 2434\u20132460.","journal-title":"SIAM Journal on Optimization"},{"key":"1313_CR26","first-page":"87","volume":"117","author":"S Lojasiewicz","year":"1963","unstructured":"Lojasiewicz, S. (1963). Une propri\u00e9t\u00e9 topologique des sous-ensembles analytiques r\u00e9els. Les \u00e9quations aux d\u00e9riv\u00e9es partielles, 117, 87\u201389.","journal-title":"Les \u00e9quations aux d\u00e9riv\u00e9es partielles"},{"key":"1313_CR27","unstructured":"Martins, A. F., Figeuiredo, M. A., Aguiar, P. M., Smith, N. A., Xing, E. P. (2011). An augmented lagrangian approach to constrained map inference. In ICML."},{"issue":"1","key":"1313_CR28","first-page":"495","volume":"16","author":"AF Martins","year":"2015","unstructured":"Martins, A. F., Figueiredo, M. A., Aguiar, P. M., Smith, N. A., & Xing, E. P. (2015). AD3: Alternating directions dual decomposition for map inference in graphical models. Journal of Machine Learning Research, 16(1), 495\u2013545.","journal-title":"Journal of Machine Learning Research"},{"key":"1313_CR29","doi-asserted-by":"crossref","unstructured":"Meshi, O., & Globerson, A. (2011). An alternating direction method for dual MAP LP relaxation. In Joint European conference on machine learning and knowledge discovery in databases (pp. 470\u2013483). Springer.","DOI":"10.1007\/978-3-642-23783-6_30"},{"key":"1313_CR30","unstructured":"Meshi, O., Mahdavi, M., & Schwing, A. (2015). Smooth and strong: Map inference with linear convergence. In NIPS (pp. 298\u2013306)."},{"issue":"3","key":"1313_CR31","doi-asserted-by":"publisher","first-page":"211","DOI":"10.3233\/AIC-2012-0531","volume":"25","author":"L Otten","year":"2012","unstructured":"Otten, L., & Dechter, R. (2012). Anytime and\/or depth-first search for combinatorial optimization. AI Communications, 25(3), 211\u2013227.","journal-title":"AI Communications"},{"key":"1313_CR32","unstructured":"Otten, L., Ihler, A., Kask, K., & Dechter, R. (2012). Winning the pascal 2011 map challenge with enhanced and\/or branch-and-bound. In IN NIPS WORKSHOP DISCML. Citeseer."},{"key":"1313_CR33","unstructured":"Savchynskyy, B., Schmidt, S., Kappes, J., & Schn\u00f6rr, C. (2012). Efficient MRF energy minimization via adaptive diminishing smoothing. ArXiv preprint arXiv:1210.4906."},{"key":"1313_CR34","unstructured":"Schwing, A. G., Hazan, T., Pollefeys, M., & Urtasun, R. (2012). Globally convergent dual MAP LP relaxation solvers using Fenchel\u2013Young margins. In NIPS (pp. 2384\u20132392)."},{"key":"1313_CR35","unstructured":"Schwing, A. G., Hazan, T., Pollefeys, M., & Urtasun, R. (2014). Globally convergent parallel MAP LP relaxation solver using the Frank\u2013Wolfe algorithm. In ICML (pp. 487\u2013495)."},{"key":"1313_CR36","unstructured":"Sontag, D. A. (2010). Approximate inference in graphical models using LP relaxations. Ph.D. Thesis, Massachusetts Institute of Technology."},{"key":"1313_CR37","unstructured":"Sontag, D. A., Li, Y., et al. (2012). Efficiently searching for frustrated cycles in map inference. In UAI."},{"issue":"11","key":"1313_CR38","doi-asserted-by":"publisher","first-page":"3697","DOI":"10.1109\/TIT.2005.856938","volume":"51","author":"MJ Wainwright","year":"2005","unstructured":"Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2005). Map estimation via agreement on trees: Message-passing and linear programming. IEEE Transactions on Information Theory, 51(11), 3697\u20133717.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1\u20132","key":"1313_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000001","volume":"1","author":"MJ Wainwright","year":"2008","unstructured":"Wainwright, M. J., & Jordan, M. I. (2008). Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1\u20132), 1\u2013305.","journal-title":"Foundations and Trends in Machine Learning"},{"issue":"1","key":"1313_CR40","first-page":"29","volume":"78","author":"Y Wang","year":"2017","unstructured":"Wang, Y., Yin, W., & Zeng, J. (2017). Global convergence of ADMM in nonconvex nonsmooth optimization. Journal of Scientific Programming, 78(1), 29\u201363.","journal-title":"Journal of Scientific Programming"},{"issue":"7","key":"1313_CR41","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1109\/TPAMI.2018.2845842","volume":"41","author":"B Wu","year":"2019","unstructured":"Wu, B., & Ghanem, B. (2019). $$\\ell _p$$-box ADMM: A versatile framework for integer programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(7), 1695\u20131708.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"3","key":"1313_CR42","doi-asserted-by":"publisher","first-page":"1758","DOI":"10.1137\/120887795","volume":"6","author":"Y Xu","year":"2013","unstructured":"Xu, Y., & Yin, W. (2013). A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM Journal on Imaging Sciences, 6(3), 1758\u20131789.","journal-title":"SIAM Journal on Imaging Sciences"}],"container-title":["International Journal of Computer Vision"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11263-020-01313-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11263-020-01313-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11263-020-01313-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T15:53:18Z","timestamp":1722527598000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11263-020-01313-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,4]]},"references-count":42,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["1313"],"URL":"https:\/\/doi.org\/10.1007\/s11263-020-01313-2","relation":{},"ISSN":["0920-5691","1573-1405"],"issn-type":[{"value":"0920-5691","type":"print"},{"value":"1573-1405","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,4]]},"assertion":[{"value":"8 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}