“A fast sparse QR factorization for solving linear least squares problems in graphics” by Gnanasekaran and Darve
Conference:
Type(s):
Entry Number: 13
Title:
- A fast sparse QR factorization for solving linear least squares problems in graphics
Presenter(s)/Author(s):
Abstract:
A wide range of problems in computer graphics and vision can be formulated as sparse least squares problems. For example, Laplacian mesh deformation, Least Squares Conformal Maps, Poisson image editing, and as-rigid-as-possible (ARAP) image warping in- volve solving a linear or non-linear sparse least squares problem. High performance is crucial in many of these applications for interactive user feedback. For these applications, we show that the matrices produced by factorization methods such as QR have a special structure: the off-diagonal blocks are low-rank. We leverage this property to produce a fast sparse approximate QR factorization, spaQR, for these matrices in near-linear time. In our benchmarks, spaQR shows up to 57% improvement over solving the normal equations using Cholesky and 63% improvement over a standard preconditioner with Conjugate Gradient Least Squares (CGLS).
References:
Abeynaya Gnanasekaran and Eric Darve. 2021. Hierarchical Orthogonal Factorization: Sparse Least Squares Problems. arXiv:2102.09878 [math.NA]
Bruno Levy, Sylvain Petitjean, Nicolas Ray, and Jérôme Maillot. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Trans. Graph. 21 (07 2002), 362–371. https://doi.org/10.1145/566654.566590
Olga Sorkine and Marc Alexa. 2007. As-Rigid-as-Possible Surface Modeling. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (Barcelona, Spain) (SGP ’07). Eurographics Association, Goslar, DEU, 109–116.
Sorkine and D. Cohen-Or. 2004. Least-squares meshes. In Proceedings Shape Modeling Applications, 2004. 191–199. https://doi.org/10.1109/SMI.2004.1314506
