CAREER: A Framework for Mining Multimode, Non-Homogeneous Tensor Data Sets With Linear and Non-Linear Degrees of Freedom

【摘要】0545538 drineas， PetrosRensselaer理工学院。海量数据集无处不在，有效利用这些数据集对于当今科学、工程和商业世界的进步至关重要。本提案涉及开发和分析用于构造和询问由多模阵列（张量）建模的多模异构数据集的新算法，这些算法在许多应用中出现。所提出的算法使用随机抽样从数据集中提取有代表性的数据元素，然后对样本进行操作。为了对异质性和非均匀性问题得到更好的结果，采用了重要抽样和其他复杂的抽样技术。本计划书包含三个具体的研究方向（前三年）和早期的职业规划（后两年）。首先，提出从抽样的角度来解决研究良好且广泛适用的1和2回归问题，以证明一个小的，明智选择的样本包含了近似解决问题所需的信息。其次，将上述结果推广到推导简单、直观的矩阵分解，形式为CUR，其中C包含矩阵的几列，R包含矩阵的几行，U是一个精心选择的矩阵。从数据解释的角度来看，cur类型的分解提供了非常吸引人的数据摘要，因为它们将a的所有列表示为直接来自数据的少量基列（C中的列）的线性组合，对于行也是如此。第三，将cur型分解扩展到张量，并为处理具有多线性结构的复杂、多模态、异构张量数据集奠定基础。在过去的两年里，人们提出将重点放在减轻张量数据集的各种模式的线性自由度假设上，并寻求提取非线性自由度的采样技术。该建议将以重要的方式扩展PI先前在快速蒙特卡罗算法上的工作，以执行大矩阵的计算。更广泛的影响。这项工作将在社会科学、生物信息学和计算机科学等不同领域产生更广泛的影响。PI已经开始与三个实验室合作，并将在它们的数据上应用拟议的技术。PI与Alter教授及其在德克萨斯大学奥斯汀分校的实验室合作，将应用和解释细胞周期基因表达数据上的cur型分解，以确定在细胞周期不同阶段活跃的生理途径。PI还将与耶鲁大学遗传学系的Kidds教授实验室合作，对来自世界各地42个种群的样本进行基因分型数据的应用和解释cur型分解。最后，PI将与耶鲁大学数学系的M. Maggioni和耶鲁大学医学院的教师合作，将提出的张量分解应用于结肠癌数据集。这三个合作将作为这些技术实际适用性的概念证明，并将引导PI朝着更广泛的目标发展一个张量分析工具箱，供多模数据自然出现的领域的众多研究人员使用。最后，pi的工作将对有广泛兴趣的本科生感兴趣。我们建议将这些知识传播给本科生，继续我们之前证明的承诺，让本科生参与到前沿研究中来，即使是在他们大二的时候。将与上述实验室合作，作出额外努力，让代表性不足的群体参与进来。

Abstract0545538Drineas, PetrosRensselaer Polytech InstIntellectual Merit. Massive data sets are ubiquitous and making effective use of such data sets is essential for the advancement of todays science, engineering, and business worlds. This proposal concerns the development and analysis of novel algorithms for structuring and interrogating multimode, heterogeneous data sets modelled by multimode arrays (tensors), which arise in many applications. The proposed algorithms use random sampling to extract representative data elements from the data sets and, subsequently, they operateon the sample. In order to yield improved results for problems with heterogeneities and non-uniformities, importance sampling and other sophisticated sampling techniques are employed. This proposal contains three specific research directions (the first three years) and an early career plan (the last two years). First, it is proposed to address the wellstudied and broadly applicable 1 and 2 regression problems from a sampling perspective in order to prove that a small, judiciously chosen sample contains the information necessary to approximately solve the problem. Second, the above results will be extended to derivesimple, intuitive matrix decompositions, of the form CUR, where C contains a few columns of the matrix, R contains a few rows of the matrix, and U is a carefully chosen matrix. CUR-type decompositions provide summaries of the data that are very appealing from a data interpretation perspective, since they express all columns of A as linear combinations of a small number of basis columns (the columns in C), which come directly from the data, and similarly for the rows. Third, CUR-type decompositions will be extended totensors and a basis for dealing with complex, multimode, heterogeneous, tensor data sets exhibiting multilinear structure will be developed. In the last two years, it is proposed to focus on alleviating the assumption of linear degrees of freedom across the various modes of tensor data sets, and seek sampling techniques that extract non-linear degrees of freedom. This proposal will extend in significant ways the previous work of the PI on fast Monte Carlo algorithms for performing computations on large matrices.Broader impact. This work will have broader impact in fields as diverse as the Social Sciences, Bioinformatics and Computer Science. The PI has initiated collaborations with three labs and will apply the proposed techniques on their data. The PI in collaboration with Prof. Alter and her lab at UT Austin will apply and interpret CUR-type decompositions on cell-cycle gene expression data in an effort to identify physiological pathways that are active during the different phases of the cell cycle. The PI will also collaborate with Prof. Kidds lab at the Genetics Department of Yale University to apply and interpretCUR-type decompositions on genotyping data from samples from 42 populations from around the world. Finally, the PI will collaborate with M. Maggioni at the Yale Math Department and faculty at the Yale Medical School to apply the proposed tensor decompositions on colon cancer datacubes. These three collaborations will serve as proofs of concept for the practical applicability of these techniques, and will lead the PI towards the broader goal of developing a toolbox for tensor analysis for use by the multitude of researchers infields where multimode data naturally arise. Finally, the PIs work will be of interest to motivated undergraduates with a wide range of interests. It is proposed to disseminate this knowledge to undergraduates by continuing our previously proven commitment to involving undergraduates, even in their sophomore year, in cutting edge research. Extra effort will be made to involve underrepresented groups, in collaboration with the aforementioned labs.