{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/128637"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/128637","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Quantitative invertibility of random matrices : a combinatorial perspective","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Jain, Vishesh."],"institution":"Massachusetts Institute of Technology","degree_name":"Doctoral","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Mathematics","school":null,"contributors":[],"advisors":["Elchanan Mossel."],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020","date_published":"2020","updated_at":"2026-07-22T22:21:30Z","subjects":["Mathematics."],"languages":["eng"],"rights":["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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/128637","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Elchanan Mossel."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Mathematics","Math"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Mathematics."]},{"key":"dc:creator","label":"Author","values":["Jain, Vishesh."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2020-11-24T17:32:22Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2020-11-24T17:32:22Z"]},{"key":"dc:date.issued","label":"Date","values":["2020"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctoral"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/128637"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Quantitative invertibility of random matrices : a combinatorial perspective"]}]}],"canonical_facts":{"dc:contributor.advisor":["Elchanan Mossel."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Mathematics","Math"],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Mathematics."],"dc:creator":["Jain, Vishesh."],"dc:date.accessioned":["2020-11-24T17:32:22Z"],"dc:date.available":["2020-11-24T17:32:22Z"],"dc:date.issued":["2020"],"dc:description":["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)."],"dc:description.abstract":["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."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/128637"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Mathematics."],"dc:title":["Quantitative invertibility of random matrices : a combinatorial perspective"],"dc:type":["Thesis"],"thesis:degree_name":["Doctoral"]},"updated_at":"2026-07-22T22:21:30Z"}