Georgia Institute of Technology College of Sciences

In this talk we construct a net around the unit sphere with strong properties. We show that with exponentially high probability, the value of |Ax| on the sphere can be approximated well using this net, where A is a random matrix with independent columns. We apply it to study the smallest singular value of random matrices under very mild assumptions, and obtain sharp small ball behavior. As a partial case, we estimate (essentially optimally) the smallest singular value for matrices of arbitrary aspect ratio with i.i.d. mean zero variance one entries. Further, in the square case we show an estimate that holds only under simply the assumptions of independent entries with bounded concentration functions, and with appropriately bounded expected Hilbert-Schmidt norm. A key aspect of our results is the absence of structural requirements such as mean zero and equal variance of the entries.