Použití randomizovaných metod nejmenších čtverců
Thesis title in Czech: | Použití randomizovaných metod nejmenších čtverců |
---|---|
Thesis title in English: | Randomized Least Squares Methods |
Key words: | metoda nejmenších čtverců|randomizované metody|numerické metody|lineární algebry |
English key words: | randomized methods|least squares|numerical methods|numerical linear algebra|scientific computing|numerical mathematics|data science |
Academic year of topic announcement: | 2023/2024 |
Thesis type: | Bachelor's thesis |
Thesis language: | |
Department: | Department of Numerical Mathematics (32-KNM) |
Supervisor: | Erin Claire Carson, Ph.D. |
Author: |
Guidelines |
The project will involve writing a background on methods for solving least squares problems, both using randomized and deterministic algorithms. It will also involve writing implementations of randomized least squares routines, performing tuning of parameters, and comparing randomized and non-randomized approaches within a particular data analysis application. Broader questions include:
1. How is the accuracy of the final answer affected by the use of a randomized method? 2. Can the performance of a particular data analysis application area be improved by replacing the standard least squares solution with a randomized method? |
References |
* Michael W. Mahoney. Randomized Algorithms for Matrices and Data. Foundation and Trends in Machine Learning, vol. 3, no. 2, pp. 123-224, 2010. http://dx.doi.org/10.1561/2200000035
* Petros Drineas and Michael W. Mahoney. Lectures on Randomized Numerical Linear Algebra. https://arxiv.org/pdf/1712.08880.pdf * Ravindran Kannan and Santosh Vempala. Randomized algorithms in numerical linear algebra. Acta Numerica, pp. 95-135, 2017. https://www.cc.gatech.edu/~vempala/papers/acta_survey.pdf |
Preliminary scope of work in English |
Least squares problems arise when we have a linear system with more equations than unknowns. Such problems frequently arise in the context of optimization and data science applications. A recent hot topic is randomized numerical linear algebra methods. In particular, there now exist randomized methods for computing least squares solutions. This project will involve investigating randomized methods for solving least squares problems and evaluating their performance, usability, and applicability in practice. |