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

Drineas，PetrosRensselaer Polytech Inst.海量数据集无处不在，有效利用这些数据集对于当今科学，工程和商业世界的进步至关重要。 该建议涉及的开发和分析的新算法的结构化和询问多模，异构数据集建模的多模阵列（张量），出现在许多应用中。所提出的算法使用随机抽样从数据集中提取有代表性的数据元素，然后对样本进行操作。为了提高结果的不均匀性和非均匀性的问题，重要性抽样和其他复杂的抽样技术。该计划包含三个具体的研究方向（前三年）和一个早期职业计划（后两年）。首先，建议从抽样的角度来解决研究充分和广泛适用的1和2回归问题，以证明一个小的，明智地选择的样本包含必要的信息，近似解决问题。其次，上述结果将被推广到导出简单，直观的矩阵分解，形式CUR，其中C包含矩阵的几列，R包含矩阵的几行，和U是一个精心选择的矩阵。 CUR-type分解提供了从数据解释的角度来看非常有吸引力的数据摘要，因为它们将A的所有列表示为少量基列（C中的列）的线性组合，这些基列直接来自数据，对于行也是如此。第三，CUR-type分解将扩展到totensors和处理复杂的，多模，异构，张量数据集表现出多线性结构的基础将开发。最近两年，有人提出要重点缓解张量数据集的各种模式中线性自由度的假设，并寻求提取非线性自由度的采样技术。 这一建议将在很大程度上扩展PI以前在快速蒙特卡罗算法上的工作，用于在大型矩阵上执行计算。这项工作将在社会科学、生物信息学和计算机科学等不同领域产生更广泛的影响。PI已与三个实验室开展合作，并将在其数据上应用所提出的技术。PI与Alter教授及其在UT Austin的实验室合作，将在细胞周期基因表达数据上应用和解释CUR-type分解，以确定在细胞周期不同阶段活跃的生理途径。PI还将与耶鲁大学遗传学系的Kidds教授实验室合作，对来自世界各地42个人群的样本的基因分型数据应用和解释CUR-type分解。最后，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.