Fast Nonlinear Least Squares Optimization of Large-Scale Semi-Sparse Problems

Simple item page
dc.contributor.authorFratarcangeli, Marcoen_US
dc.contributor.authorBradley, Dereken_US
dc.contributor.authorGruber, Aurelen_US
dc.contributor.authorZoss, Gasparden_US
dc.contributor.authorBeeler, Thaboen_US
dc.contributor.editorPanozzo, Daniele and Assarsson, Ulfen_US
dc.date.accessioned2020-05-24T12:51:39Z
dc.date.available2020-05-24T12:51:39Z
dc.date.issued2020
dc.description.abstractMany problems in computer graphics and vision can be formulated as a nonlinear least squares optimization problem, for which numerous off-the-shelf 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-sparse 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-scale semi-sparse problems. We use the nonlinear Levenberg-Marquardt method to locally linearize the problem in parallel, based on its firstorder 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-based facial capture using a recently-proposed anatomical local face deformation model.en_US
dc.description.number2
dc.description.sectionheadersFaces
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume39
dc.identifier.doi10.1111/cgf.13927
dc.identifier.issn1467-8659
dc.identifier.pages247-259
dc.identifier.urihttps://doi.org/10.1111/cgf.13927
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13927
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectComputing methodologies
dc.subjectMassively parallel and high
dc.subjectperformance simulations
dc.subjectAnimation
dc.titleFast Nonlinear Least Squares Optimization of Large-Scale Semi-Sparse Problemsen_US
Files
Collections
39-Issue 2