Statistical Problems Through a New Perturbation Theory

One of the main goals of statistics and data science is to deduce information from a large set of data, usually given in the form of a large matrix. For instance, in most recommendation systems, the rows of the matrix represent customers, and the columns represent products, the entries are the (potential) rating of a customer for the corresponding product. Since data comes with noise, it is important to measure the impact of noise on the information we would like to deduce (in most cases, in terms of some matrix parameters). Given the popularity of the spectral method in data science, the problem has been studied by scientists across many fields for a century. However, in modern data science, it has been observed that very often, the data matrix has some structure, such as being low rank. The PI aims to develop a new theory with this restriction, which would improve many classical mathematical results, and at the same time, would lead to better estimates and faster algorithms for many real-life problems. The project also provides research training opportunities for graduate students. Consider a matrix (which represents data). In practice, we often have access to a noise version of it, where each entry is added with some noise (or the whole matrix is added to a noise matrix). Classical perturbation theorems, such as Weyl or Davis-Kahan, provide us with estimates for the difference between key parameters of the original matrix (such as leading eigenvalues and eigenvectors) and their noisy counterparts. These results are sharp in worst cases analysis. However, in modern data science, data often has a low-rank structure, and noise is random. Under these assumptions, the PI has observed that one can provide much better bounds. Under this project, the PI will obtain optimal bounds under the above assumption, in various norms. The PI and his students will also attack several well-known algorithmic problems, such as matrix completion and Gaussian mixtures, using the spectral method combined with these new tools. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.