Skip to Main content Skip to Navigation
Journal articles

Efficient recursive least squares solver for rank-deficient matrices

Abstract : Updating a linear least squares solution can be critical for near real-time signalprocessing applications. The Greville algorithm proposes a simple formula for updating the pseudoinverse of a matrix A ∈ R n×m with rank r. In this paper, we explicitly derive a similar formula by maintaining a general rank factorization, which we call rank-Greville. Based on this formula, we implemented a recursive least squares algorithm exploiting the rank-deficiency of A, achieving the update of the minimum-norm least-squares solution in O(mr) operations and, therefore, solving the linear least-squares problem from scratch in O(nmr) operations. We empirically confirmed that this algorithm displays a better asymptotic time complexity than LAPACK solvers for rank-deficient matrices. The numerical stability of rank-Greville was found to be comparable to Cholesky-based solvers. Nonetheless, our implementation supports exact numerical representations of rationals, due to its remarkable algebraic simplicity.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03254881
Contributor : Stephan N. Steinmann Connect in order to contact the contributor
Submitted on : Monday, June 21, 2021 - 11:58:38 AM
Last modification on : Tuesday, January 4, 2022 - 5:49:42 AM
Long-term archiving on: : Wednesday, September 22, 2021 - 6:04:34 PM

Identifiers

Citation

Ruben Staub, Stephan N. Steinmann. Efficient recursive least squares solver for rank-deficient matrices. Applied Mathematics and Computation, Elsevier, 2021, 399, pp.125996. ⟨10.1016/j.amc.2021.125996⟩. ⟨hal-03254881⟩

Share

Metrics

Les métriques sont temporairement indisponibles