The power of randomized algorithms : from numerical linear algebra to biological systems
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/120424 |
| _version_ | 1811091757457211392 |
|---|---|
| author | Musco, Cameron N. (Cameron Nicholas) |
| author2 | Nancy A. Lynch. |
| author_facet | Nancy A. Lynch. Musco, Cameron N. (Cameron Nicholas) |
| author_sort | Musco, Cameron N. (Cameron Nicholas) |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. |
| first_indexed | 2024-09-23T15:07:36Z |
| format | Thesis |
| id | mit-1721.1/120424 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:07:36Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1204242019-04-11T04:26:33Z The power of randomized algorithms : from numerical linear algebra to biological systems From numerical linear algebra to biological systems Musco, Cameron N. (Cameron Nicholas) Nancy A. Lynch. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. Cataloged from PDF version of thesis. Includes bibliographical references (pages 323-347). In this thesis we study simple, randomized algorithms from a dual perspective. The first part of the work considers how randomized methods can be used to accelerate the solution of core problems in numerical linear algebra. In particular, we give a randomized low-rank approximation algorithm for positive semidefinite matrices that runs in sublinear time, significantly improving upon what is possible with traditional deterministic methods. We also discuss lower bounds on low-rank approximation and spectral summarization problems that attempt to explain the importance of randomization and approximation in accelerating linear algebraic computation. The second part of the work considers how the theory of randomized algorithms can be used more generally as a tool to understand how complexity emerges from low-level stochastic behavior in biological systems. We study population density- estimation in ant colonies, which is a key primitive in social decision-making and task allocation. We define a basic computational model and show how agents in this model can estimate their density using a simple random-walk-based algorithm. We also consider simple randomized algorithms for computational primitives in spiking neural networks, focusing on fast winner-take-all networks. by Cameron Nicholas Musco. Ph. D. 2019-02-14T15:50:19Z 2019-02-14T15:50:19Z 2018 2018 Thesis http://hdl.handle.net/1721.1/120424 1084478765 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 347 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Musco, Cameron N. (Cameron Nicholas) The power of randomized algorithms : from numerical linear algebra to biological systems |
| title | The power of randomized algorithms : from numerical linear algebra to biological systems |
| title_full | The power of randomized algorithms : from numerical linear algebra to biological systems |
| title_fullStr | The power of randomized algorithms : from numerical linear algebra to biological systems |
| title_full_unstemmed | The power of randomized algorithms : from numerical linear algebra to biological systems |
| title_short | The power of randomized algorithms : from numerical linear algebra to biological systems |
| title_sort | power of randomized algorithms from numerical linear algebra to biological systems |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/120424 |
| work_keys_str_mv | AT muscocameronncameronnicholas thepowerofrandomizedalgorithmsfromnumericallinearalgebratobiologicalsystems AT muscocameronncameronnicholas fromnumericallinearalgebratobiologicalsystems AT muscocameronncameronnicholas powerofrandomizedalgorithmsfromnumericallinearalgebratobiologicalsystems |