Projects per year
Abstract
Complex problem sets and an ever increasing amount of data presents difficult computational challenges for data scientists, and many problems often require computing resources that exceed what is readily available. A number of advanced algorithms are already available and used to solve core problems in data science, but these may rely on crude approximations or simplified models limiting their use on increasingly complicated problems. This calls for the need to develop new algorithms for implementation in key applications within data science.
Recognizing and exploiting complex structure is a necessary mathematical prerequisite for the development of new algorithms to address the computational challenges. The major part of this thesis focuses on exploiting complex rank structure that is present in many applications of interest. Specifically, we investigate how to exploit hierarchical matrix structure, that is characterized by low-rank off-diagonal blocks.
First we study a fundamental matrix nearness problem that imposes low-rank constraints on the off-diagonal blocks. This results in both new fundamental knowledge within the field of optimization and a hierarchical approximation to symmetric positive definite matrices. We apply the hierarchical approximation as a general purpose preconditioner for the conjugate gradient method, where it shows great potential for ill-posed systems.
Next we turn to the class of quasi-Newton methods, which are widely used to solve core problems in data science. We develop a new variant of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm, which we denote as hierarchical BFGS (H-BFGS). H-BFGS uses hierarchical Hessian approximations based on historical first-order information, allowing us to keep more curvature information without sacrificing scalability. We apply H-BFGS to core problems in data science with promising results.
For the final part of the thesis, we turn away from hierarchical matrices and instead focus on computed tomography (CT). This is a core imaging technique, especially known for its application within the medical field. To obtain high-quality images it is paramount that the mathematical model used to reconstruct the image corresponds with the actual experimental setup. We explore how we can incorporate uncertainties in the geometry of the experimental setup into the mathematical model to obtain higher quality reconstructions. This is done by developing a Bayesian model to sample both the reconstructed image and the geometric parameters. We apply the model to a challenging real-world tomographic data set with great results.
Recognizing and exploiting complex structure is a necessary mathematical prerequisite for the development of new algorithms to address the computational challenges. The major part of this thesis focuses on exploiting complex rank structure that is present in many applications of interest. Specifically, we investigate how to exploit hierarchical matrix structure, that is characterized by low-rank off-diagonal blocks.
First we study a fundamental matrix nearness problem that imposes low-rank constraints on the off-diagonal blocks. This results in both new fundamental knowledge within the field of optimization and a hierarchical approximation to symmetric positive definite matrices. We apply the hierarchical approximation as a general purpose preconditioner for the conjugate gradient method, where it shows great potential for ill-posed systems.
Next we turn to the class of quasi-Newton methods, which are widely used to solve core problems in data science. We develop a new variant of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm, which we denote as hierarchical BFGS (H-BFGS). H-BFGS uses hierarchical Hessian approximations based on historical first-order information, allowing us to keep more curvature information without sacrificing scalability. We apply H-BFGS to core problems in data science with promising results.
For the final part of the thesis, we turn away from hierarchical matrices and instead focus on computed tomography (CT). This is a core imaging technique, especially known for its application within the medical field. To obtain high-quality images it is paramount that the mathematical model used to reconstruct the image corresponds with the actual experimental setup. We explore how we can incorporate uncertainties in the geometry of the experimental setup into the mathematical model to obtain higher quality reconstructions. This is done by developing a Bayesian model to sample both the reconstructed image and the geometric parameters. We apply the model to a challenging real-world tomographic data set with great results.
Original language | English |
---|
Publisher | Technical University of Denmark |
---|---|
Number of pages | 150 |
Publication status | Published - 2024 |
Fingerprint
Dive into the research topics of 'Computational methods for optimization with rank structure'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Computational methods for optimization with rank structure
Pedersen, F. H. (PhD Student), Andersen, M. S. (Main Supervisor), Dahl, J. (Supervisor), Bellavia, S. (Examiner) & Kressner, D. (Examiner)
15/03/2021 → 14/01/2025
Project: PhD