Fourier approximation of the jacobian matrix in large-scale non-linear least square problems

Abstract

Esta memoria propone un enfoque novedoso para resolver sistemas de ecuaciones no lineales sobredeterminados de gran tamaño sin necesidad de almacenar explícitamente la matriz Jacobiana y su transpuesta. El enfoque utiliza técnicas de compresión de vectores basadas en la transformada de Fourier para generar una matriz Jacobiana “sparse” que puede almacenarse de manera explícita. Además, se desarrolla un algoritmo para calcular de manera eficiente el producto de la matriz Jacobiana transpuesta por un vector para problemas de mínimos cuadrados de gran tamaño. Los objetivos de esta investigación son dos: introducir un método de aproximación efectivo para la matriz Jacobiana y proporcionar un algoritmo eficiente para calcular el producto de la matriz Jacobiana transpuesta con un vector. Al aprovechar la transformada de Fourier, nuestro enfoque logra importantes ahorros computacionales y reduce los requisitos de almacenamiento asociados con sistemas de gran escala. Esto resulta especialmente valioso en escenarios donde el almacenamiento explícito de la matriz Jacobiana y su transpuesta es inviable debido a la dimensionalidad del problema. El comportamiento del enfoque propuesto se estudia ampliamente en el contexto del algoritmo ns-LSQR, que resuelve problemas de mínimos cuadrados utilizando aproximaciones de la matriz Jacobiana y su transpuesta. Nuestros hallazgos demuestran que el método de aproximación propuesto es viable en realidad; sin embargo, cuando disminuye el porcentaje de componentes en la aproximación, se requiere una mayor dimensión del subespacio de Krylov para garantizar la convergencia del método. Esto destaca el equilibrio entre la precisión de la aproximación y la eficiencia computacional. El algoritmo calcula de manera eficiente el producto de la matriz Jacobiana transpuesta con un vector mediante el uso de la aproximación propuesta y propiedades de la Transformada de Fourier con una complejidad computacional de O((n + 1) m log(m)) permitiendo la solución de sistemas no lineales sobredeterminados de gran escala. This undergraduate thesis proposes a novel approach to solving large-scale overdetermined nonlinear systems of equations without the need for explicit storage of the Jacobian matrix and its transpose. The approach utilizes vector compression techniques based on the Fourier transform to generate a sparse Jacobian matrix that can be stored explicitly. Additionally, an algorithm is developed for efficiently computing the product of the Jacobian matrix transposed with a vector for large-scale least-squares problems. The objectives of this research are twofold: to introduce an effective approximation method for the Jacobian matrix and to provide an efficient algorithm for computing the product of the transposed Jacobian matrix with a vector. By leveraging the Fourier transform, our approach achieves significant computational savings and reduces the storage requirements associated with large-scale systems. This makes it particularly valuable in scenarios where explicit storage of the Jacobian matrix and its transpose is infeasible due to the problem’s dimensionality. The behavior of the proposed approach is extensively studied within the context of the ns-LSQR algorithm, which solves least-squares problems using approximations of the Jacobian matrix and its transpose. Our findings demonstrate that the proposed approximation method is actually viable however when the percentage of components in the approximation decreases, a higher dimension of the Krylov subspace is required to ensure the convergence of the method. This highlights the trade-off between approximation accuracy and computational efficiency. The algorithm efficiently calculates the product of the transpose Jacobian matrix with a vector by using the proposed approximation and properties of the Fourier Transform with a computational complexity of O((n + 1) m log(m)), allowing the solution of large-scale overdetermined nonlinear systems.