Matrix Completion with Non-uniform Missing Patterns, a New Measure of Conditional Dependence, and Applications to Feature Selection

This project aims to study three classes of problems in mathematical statistics. The first class of problems is about matrix completion. Suppose that we have an array of numbers with missing entries, such as a database of ratings from users of a product.

Matrix completion is the problem of predicting the missing values. Much work has been done on this problem in the last ten years, but the vast majority of it is under the assumption that the matrix entries are missing uniformly at random. In practice, however, that is not usually the case.

This project will implement a method where the matrix completion problem can be solved under more realistic assumptions. This will impact all areas of science and technology where matrix completion algorithms have applications, such as recommender systems, collaborative filtering, computer vision, and genetics, to name a few. The second class of problems concerns the development of an approach for measuring conditional dependence.

Measuring conditional dependence is important in many applications of statistics, such as in the analysis of graphical and causal models, which are widely used in the social sciences. The third class of problems is about developing a new approach for selecting the right variables for performing regression analysis when presented with a large number of variables.

This part of the project will impact all areas of science and technology where regression problems with many predictors are commonplace, such as biology, medicine, and genomics.

The project on matrix completion aims to solve the low rank matrix completion problem when the pattern of missing entries is deterministic. The PI has recently published an asymptotic solution of the problem. The project will yield a non-asymptotic version of the theory, and an algorithm for matrix completion when the probability of an entry to be missing is a function of the entry itself.

The project on a new measure of conditional dependence will analyze the asymptotic properties of a coefficient proposed recently by the PI and one of his students. The results of the analysis may help in devising new tests for conditional independence. The project on feature selection will analyze the properties of a non-parametric feature selection algorithm proposed recently by the PI and one of his students.

The results of the analysis may guide better implementation of the algorithm, as well as yield new and better selection algorithms.

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.