III: Small: Structural Matrix Completion for Data Mining Applications

在科学和工程中出现的一个常见问题是数据集可能只能部分测量。 通常，完整的数据集自然地表示为矩阵-例如，城市中的交通流量，一组治疗中的基因表达，或用户对电影的评级。 最近，出现了一种新的解决策略，用于推断此类数据集中的缺失条目的问题，但这种新的“结构化”方法的能力和局限性尚未完全理解。 本项目将更好地理解这种结构方法，并将这种理解应用于一些重要问题。 此外，该项目还将为数据科学教育开发新的课程材料，并对研究生和本科生进行培训。矩阵补全问题旨在在低秩假设下推断矩阵的缺失项。 到目前为止，大多数矩阵补全方法实际上并不检查已知条目是否包含足够的信息来完成矩阵。 然而，最近出现了一种新的和非常不同的“结构”方法，它分析可见矩阵项的信息内容，因此可以确定是否可以精确完成。 从数据挖掘的角度来看，结构矩阵完成方法的影响在很大程度上是未开发的。 该项目将研究如何利用结构矩阵完成方法来解决大量的数据分析问题，包括开发主动矩阵完成的新方法，交叉验证矩阵完成结果的新方法，以及通用矩阵完成的新策略。

A common problem arising in science and engineering is that a dataset may only be partially measured. Often the complete dataset is naturally expressed as a matrix - for example, traffic flows in a city, gene expression across a set of treatments, or ratings of movies for users. Recently, a new solution strategy has emerged for the problem of inferring the missing entries in such datasets, but the power and limits of this new "structural" approach are not fully understood as yet. This project will develop a better understanding of this structural approach and apply that understanding to a number of important problems. In addition, the project will develop new course materials for data science education, and train both graduate and undergraduate students.The matrix completion problem seeks to infer the missing entries of a matrix, under a low-rank assumption. To date, most matrix completion methods do not actually check whether the known entries contain sufficient information to complete the matrix. Recently, however, a new and very different class of "structural" methods have emerged, which analyze the information content of the visible matrix entries, and so can determine whether accurate completion is possible. From a data mining standpoint, the implications of structural matrix completion methods are largely unexplored. This project will investigate how to leverage structural matrix completion methods to attack a host of data analysis problems, including developing new methods for active matrix completion, new approaches to cross-validating matrix completion results, and new strategies for general matrix completion.