Quantitative invertibility of random matrices : a combinatorial perspective
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, May, 2020
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/128637 |
| _version_ | 1826201162651533312 |
|---|---|
| author | Jain, Vishesh. |
| author2 | Elchanan Mossel. |
| author_facet | Elchanan Mossel. Jain, Vishesh. |
| author_sort | Jain, Vishesh. |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, May, 2020 |
| first_indexed | 2024-09-23T11:47:12Z |
| format | Thesis |
| id | mit-1721.1/128637 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:47:12Z |
| publishDate | 2020 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1286372020-11-25T03:20:40Z Quantitative invertibility of random matrices : a combinatorial perspective Jain, Vishesh. Elchanan Mossel. Massachusetts Institute of Technology. Department of Mathematics. Massachusetts Institute of Technology. Department of Mathematics Mathematics. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, May, 2020 Cataloged from the official PDF of thesis. Includes bibliographical references (pages 101-106). In this thesis, we develop a novel framework for investigating the lower tail behavior of the least singular value of random matrices - a subject which has been intensely studied in the past two decades. Our focus is on obtaining high probability bounds, rather than on estimating the least singular value of a 'typical' realisation of the random matrix. In our main application, we consider random matrices of the form Mn := M + Nn, where M is a fixed complex matrix with operator norm at most exp(Nc), and Nn is a random matrix, each of whose entries is an independent copy of a complex random variable with mean 0 and variance 1. This setting, with some additional restrictions, has been previously considered in a series of influential works by Tao and Vu, most notably in connection with the strong circular law, and the smoothed analysis of the condition number, and our results extend and improve upon theirs in a couple of ways. As opposed to all previous works obtaining such bounds with error rate better than n-1, our proof makes no use either of the inverse Littlewood-Offord theorems, or of any sophisticated net constructions. Instead, we show how to reduce the optimization problem characterizing the smallest singular value from the (complex) sphere to (Gaussian) integer vectors, where it is solved using direct combinatorial arguments. by Vishesh Jain. Ph. D. Ph.D. Massachusetts Institute of Technology, Department of Mathematics 2020-11-24T17:32:22Z 2020-11-24T17:32:22Z 2020 2020 Thesis https://hdl.handle.net/1721.1/128637 1222908915 eng MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided. http://dspace.mit.edu/handle/1721.1/7582 106 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Jain, Vishesh. Quantitative invertibility of random matrices : a combinatorial perspective |
| title | Quantitative invertibility of random matrices : a combinatorial perspective |
| title_full | Quantitative invertibility of random matrices : a combinatorial perspective |
| title_fullStr | Quantitative invertibility of random matrices : a combinatorial perspective |
| title_full_unstemmed | Quantitative invertibility of random matrices : a combinatorial perspective |
| title_short | Quantitative invertibility of random matrices : a combinatorial perspective |
| title_sort | quantitative invertibility of random matrices a combinatorial perspective |
| topic | Mathematics. |
| url | https://hdl.handle.net/1721.1/128637 |
| work_keys_str_mv | AT jainvishesh quantitativeinvertibilityofrandommatricesacombinatorialperspective |