Distributed computing of large-scale singular value decompositions
<p>Big data projects increasingly make use of networks of heterogeneous computational resources for scientific computing purposes. To meet the requirements of big data applications and harness the power of modern computing architectures, novel highly parallel algorithms for numerical linea...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
2018
|
| _version_ | 1797075187505561600 |
|---|---|
| author | Fang, S |
| author2 | Hauser, R |
| author_facet | Hauser, R Fang, S |
| author_sort | Fang, S |
| collection | OXFORD |
| description | <p>Big data projects increasingly make use of networks of heterogeneous computational resources for scientific computing purposes. To meet the requirements of big data applications and harness the power of modern computing architectures, novel highly parallel algorithms for numerical linear algebra computations are needed that rely on as little node synchronicity and data communication as possible. Distributed algorithms are particularly important in situations where the data itself is naturally distributed across several or many servers, or where the data collection is decentralised. The singular value decomposition (SVD) is one of the fundamental matrix decompositions and a cornerstone of numerical linear algebra. The computation of leading part SVDs plays an essential role in a variety of models and algorithms and dominates their computational costs.</p> <p>In this thesis, we analyse a distributed algorithm for leading part SVD computations of large-scale matrices. The algorithm is well adapted to cloud computing or computer networks, as it satisfies the loose coupling requirement (low synchronicity, low communication overhead). The algorithm was first introduced by R. Hauser and D. Goodman and was first published in the latter's DPhil thesis. We will give the geometric intuition behind the algorithm and introduce it formally, but the main part of this thesis will focus on the analysis of the distributed SVD algorithm and its experimental validation.</p> <p>Two different approaches will be proposed to investigate the convergence of the algorithm. The first approach utilizes classical matrix analysis tools, leading to an error bound. The second approach of analysis provides more geometric insights. The framework based on geometric observations gives bounds on the global aggregation of numerical approximation errors that occur in local computations. Bounds on these local errors are studied probabilistically under the assumption of random input.</p> <p>Finally, we report numerical experiments, as well as the discussion of the variants of the algorithm. Applications in matrix optimisation problems, including low-rank matrix completion and sparse principal component analysis, will also be presented, and we use these to obtain an experimental validation of the algorithm under non-random input.</p> |
| first_indexed | 2024-03-06T23:46:49Z |
| format | Thesis |
| id | oxford-uuid:71354241-7659-4de9-b905-4bb3c0a56d77 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:46:49Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | oxford-uuid:71354241-7659-4de9-b905-4bb3c0a56d772022-03-26T19:42:07ZDistributed computing of large-scale singular value decompositionsThesishttp://purl.org/coar/resource_type/c_db06uuid:71354241-7659-4de9-b905-4bb3c0a56d77ORA Deposit2018Fang, SHauser, R<p>Big data projects increasingly make use of networks of heterogeneous computational resources for scientific computing purposes. To meet the requirements of big data applications and harness the power of modern computing architectures, novel highly parallel algorithms for numerical linear algebra computations are needed that rely on as little node synchronicity and data communication as possible. Distributed algorithms are particularly important in situations where the data itself is naturally distributed across several or many servers, or where the data collection is decentralised. The singular value decomposition (SVD) is one of the fundamental matrix decompositions and a cornerstone of numerical linear algebra. The computation of leading part SVDs plays an essential role in a variety of models and algorithms and dominates their computational costs.</p> <p>In this thesis, we analyse a distributed algorithm for leading part SVD computations of large-scale matrices. The algorithm is well adapted to cloud computing or computer networks, as it satisfies the loose coupling requirement (low synchronicity, low communication overhead). The algorithm was first introduced by R. Hauser and D. Goodman and was first published in the latter's DPhil thesis. We will give the geometric intuition behind the algorithm and introduce it formally, but the main part of this thesis will focus on the analysis of the distributed SVD algorithm and its experimental validation.</p> <p>Two different approaches will be proposed to investigate the convergence of the algorithm. The first approach utilizes classical matrix analysis tools, leading to an error bound. The second approach of analysis provides more geometric insights. The framework based on geometric observations gives bounds on the global aggregation of numerical approximation errors that occur in local computations. Bounds on these local errors are studied probabilistically under the assumption of random input.</p> <p>Finally, we report numerical experiments, as well as the discussion of the variants of the algorithm. Applications in matrix optimisation problems, including low-rank matrix completion and sparse principal component analysis, will also be presented, and we use these to obtain an experimental validation of the algorithm under non-random input.</p> |
| spellingShingle | Fang, S Distributed computing of large-scale singular value decompositions |
| title | Distributed computing of large-scale singular value decompositions |
| title_full | Distributed computing of large-scale singular value decompositions |
| title_fullStr | Distributed computing of large-scale singular value decompositions |
| title_full_unstemmed | Distributed computing of large-scale singular value decompositions |
| title_short | Distributed computing of large-scale singular value decompositions |
| title_sort | distributed computing of large scale singular value decompositions |
| work_keys_str_mv | AT fangs distributedcomputingoflargescalesingularvaluedecompositions |