{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T00:52:24Z","timestamp":1747183944491,"version":"3.40.5"},"reference-count":39,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"vor","delay-in-days":73,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Computer Graphics Forum"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many problems in computer graphics and vision can be formulated as a nonlinear least squares optimization problem, for which numerous off\u2010the\u2010shelf solvers are readily available. Depending on the structure of the problem, however, existing solvers may be more or less suitable, and in some cases the solution comes at the cost of lengthy convergence times. One such case is semi\u2010sparse optimization problems, emerging for example in localized facial performance reconstruction, where the nonlinear least squares problem can be composed of hundreds of thousands of cost functions, each one involving many of the optimization parameters. While such problems can be solved with existing solvers, the computation time can severely hinder the applicability of these methods. We introduce a novel iterative solver for nonlinear least squares optimization of large\u2010scale semi\u2010sparse problems. We use the nonlinear Levenberg\u2010Marquardt method to locally linearize the problem in parallel, based on its first\u2010order approximation. Then, we decompose the linear problem in small blocks, using the local Schur complement, leading to a more compact linear system without loss of information. The resulting system is dense but its size is small enough to be solved using a parallel direct method in a short amount of time. The main benefit we get by using such an approach is that the overall optimization process is entirely parallel and scalable, making it suitable to be mapped onto graphics hardware (GPU). By using our minimizer, results are obtained up to one order of magnitude faster than other existing solvers, without sacrificing the generality and the accuracy of the model. We provide a detailed analysis of our approach and validate our results with the application of performance\u2010based facial capture using a recently\u2010proposed anatomical local face deformation model.<\/jats:p>","DOI":"10.1111\/cgf.13927","type":"journal-article","created":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T11:37:33Z","timestamp":1594640253000},"page":"247-259","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast Nonlinear Least Squares Optimization of Large\u2010Scale Semi\u2010Sparse Problems"],"prefix":"10.1111","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1156-3760","authenticated-orcid":false,"given":"M.","family":"Fratarcangeli","sequence":"first","affiliation":[{"name":"Chalmers University of Technology"},{"name":"DisneyResearch|Studios"}]},{"given":"D.","family":"Bradley","sequence":"additional","affiliation":[{"name":"DisneyResearch|Studios"}]},{"given":"A.","family":"Gruber","sequence":"additional","affiliation":[{"name":"ETH Zurich"}]},{"given":"G.","family":"Zoss","sequence":"additional","affiliation":[{"name":"DisneyResearch|Studios"},{"name":"ETH Zurich"}]},{"given":"T.","family":"Beeler","sequence":"additional","affiliation":[{"name":"DisneyResearch|Studios"}]}],"member":"311","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"key":"e_1_2_8_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"e_1_2_8_3_2","unstructured":"AgarwalS. MierleK. Others:Ceres solver.http:\/\/ceres-solver.org. 2 9 10 11"},{"key":"e_1_2_8_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971538"},{"key":"e_1_2_8_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_8_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3092818"},{"key":"e_1_2_8_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132188"},{"key":"e_1_2_8_8_2","doi-asserted-by":"crossref","unstructured":"DaiA. NiessnerM. Zoll\u00f6ferM. IzadiS. TheobaltC.: Bundlefusion: Real\u2010time globally consistent 3d reconstruction using on\u2010the\u2010fly surface re\u2010integration.ACM Trans. Graph. (TOG)(2017). 3","DOI":"10.1145\/3054739"},{"key":"e_1_2_8_9_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13785"},{"key":"e_1_2_8_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201354"},{"key":"e_1_2_8_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982437"},{"key":"e_1_2_8_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717761"},{"key":"e_1_2_8_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0916028"},{"key":"e_1_2_8_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2231816.2231821"},{"key":"e_1_2_8_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_8_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_8_17_2","unstructured":"LewisJ. P. AnjyoK. RheeT. ZhangM. PighinF. DengZ.: Practice and theory of blendshape facial models. InEurographics 2014 \u2010 State of the Art Reports(2014) Lefebvre S. Spagnuolo M. (Eds.) The Eurographics Association pp.199\u2013218. 3"},{"key":"e_1_2_8_18_2","doi-asserted-by":"crossref","unstructured":"LevenbergK.: A method for the solution of certain non\u2010linear problems in least squares.Quart. Appl. Math. 2 (1944) 164\u2013168. 2 5","DOI":"10.1090\/qam\/10666"},{"key":"e_1_2_8_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322951"},{"key":"e_1_2_8_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982430"},{"key":"e_1_2_8_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0111030"},{"key":"e_1_2_8_22_2","unstructured":"MacklinM. ErlebenK. M\u00fcllerM. ChentanezN. JeschkeS. MakoviychukV.: Non\u2010smooth newton methods for deformable multi\u2010body dynamics.CoRR abs\/1907.04587(2019). 3"},{"key":"e_1_2_8_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2734425"},{"key":"e_1_2_8_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925886"},{"key":"e_1_2_8_25_2","unstructured":"NgA. Y. JordanM. I. WeissY.: On spectral clustering: Analysis and an algorithm. InNeural Information Processing Systems: Natural and Synthetic(Cambridge MA USA 2001) NIPS'01 MIT Press pp.849\u2013856. 5 7 8"},{"key":"e_1_2_8_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882269"},{"key":"e_1_2_8_27_2","unstructured":"SorkineO. AlexaM.: As\u2010rigid\u2010as\u2010possible surface modeling. InProceedings of the Fifth Eurographics Symposium on Geometry Processing(Aire\u2010la\u2010Ville Switzerland Switzerland 2007) SGP '07 Eurographics Association pp.109\u2013116. 6"},{"key":"e_1_2_8_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_8_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-070-4"},{"key":"e_1_2_8_30_2","unstructured":"SchloegelK. KarypisG. KumarV.:Sourcebook of parallel computing. Morgan Kaufmann Publishers Inc. San Francisco CA USA 2003 ch. Graph Partitioning for High\u2010performance Scientific Simulations pp.491\u2013541. 7"},{"key":"e_1_2_8_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073618"},{"key":"e_1_2_8_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2148230"},{"key":"e_1_2_8_33_2","doi-asserted-by":"crossref","unstructured":"TriggsB. McLauchlanP. F. HartleyR. I. FitzgibbonA. W.: Bundle adjustment \u2010 a modern synthesis. InProceedings of the International Workshop on Vision Algorithms: Theory and Practice(London UK UK 2000) ICCV '99 Springer\u2010Verlag pp.298\u2013372. 2","DOI":"10.1007\/3-540-44480-7_21"},{"key":"e_1_2_8_34_2","doi-asserted-by":"crossref","unstructured":"ThiesJ. Zollh\u00f6ferM. StammingerM. TheobaltC. NiessnerM.: Face2face: Real\u2010time face capture and reenactment of rgb videos. In2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)(June2016) pp.2387\u20132395. 2 3","DOI":"10.1109\/CVPR.2016.262"},{"key":"e_1_2_8_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_8_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925882"},{"key":"e_1_2_8_37_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13350"},{"key":"e_1_2_8_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_2_8_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661232"},{"key":"e_1_2_8_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601165"}],"container-title":["Computer Graphics Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Fcgf.13927","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/cgf.13927","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1111\/cgf.13927","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/cgf.13927","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,28]],"date-time":"2023-08-28T02:39:23Z","timestamp":1693190363000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1111\/cgf.13927"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["10.1111\/cgf.13927"],"URL":"https:\/\/doi.org\/10.1111\/cgf.13927","archive":["Portico"],"relation":{},"ISSN":["0167-7055","1467-8659"],"issn-type":[{"type":"print","value":"0167-7055"},{"type":"electronic","value":"1467-8659"}],"subject":[],"published":{"date-parts":[[2020,5]]},"assertion":[{"value":"2020-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}