The present thesis focuses on the design and analysis of randomized algorithms for accelerating several linear algebraic tasks. In particular, we develop simple, efficient, randomized algorithms for a plethora of fundamental linear algebraic tasks and we also demonstrate their usefulness and applicability to matrix computations and graph theoretic problems. The thesis can be divided into three parts. The first part concentrates on the development of randomized linear algebraic primitives, the second part demonstrates the application of such primitives to matrix computations, and the last part discusses the application of such primitives to graph problems.
First, we present randomized approximation algorithms for the problems of matrix multiplication, orthogonal projection, vector orthonormalization and principal angles computation (a.k.a. canonical correlation analysis).
Second, utilizing the tools developed in the first part, we present randomized and provable accurate approximation algorithms for the problems of linear regression and element-wise matrix sparsification. Moreover, we present an efficient deterministic algorithm for selecting a small subset of vectors that are in isotropic position.
Finally, we exploit well-known interactions between linear algebra and spectral graph theory to develop and analyze graph algorithms. In particular, we present a near-optimal time deterministic construction of expanding Cayley graphs, an efficient deterministic algorithm for graph sparsification and a randomized distributed Laplacian solver that operates under the gossip model of computation.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/36082 |
| Date | 13 August 2013 |
| Creators | Zouzias, Anastasios |
| Contributors | Mark, Braverman |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.002 seconds