AI Institutes Seminar - Prof. Mark Rudelson

Dear all, We are delighted to have a special talk by Prof. Mark Rudelson, who has made great foundational contributions to the fields of probability theory and geometric analysis. The talk details are as follows. Speaker: Prof. Mark Rudelson Affiliation: Department of Mathematics, University of Michigan Host: Prof. Aryeh Kontorovich Title: Low Complexity Smoothed Analysis Abstract: Perturbing a deterministic n-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms. The idea of adding the noise to a given deterministic matrix was introduced by Spielman and Teng in 2004. This noise reduces the condition number of the input matrix to O(n), and with it the complexity of many matrix algorithms. Moreover, it is oblivious to the input as it does not require any prior knowledge of the matrix besides a crude bound on its norm. However, when deployed algorithmically, this method is expensive due to the cost of generating and storing n^2 Gaussian random variables. We will describe a random matrix construction which requires generating O(n) independent random variables and reduces the condition number of any deterministic matrix to O(n), thus matching Gaussian perturbations. Using so few independent variables requires generating a random matrix with dependent entries thus making the condition number analysis more involved. Joint work with Shabarish Cenakkod, Michal Derezinski, and Xiaoyu Dong.