Collaborative Research: Randomized Algorithms in Linear Algebra and Numerical Evaluations on Massive Datasets

数据矩阵的结构特性给数值线性代数(NLA)社区和算法理论(TOA)社区带来了挑战和机遇。矩阵分解，如特征分解、显阶QR分解、奇异值分解等，在信息检索中得到了广泛的应用。在历史上，矩阵分解一直是NLA的核心兴趣，因为人们可以使用它们来表示问题，从而使问题更容易解决。另一方面，TOA最近从抽样的角度讨论了这种分解的计算。这两种方法是相辅相成的。然而，到目前为止，这两个社区还没有密切合作，将他们融合在一起。通常情况下，每个社区都只是粗略地了解另一个社区的发展。定义两个社区都可以研究的重要研究方向，并将得到的线性代数算法应用于数据分析问题(以及其他)，将导致重要的突破。这项提议的主要目标是弥合现有的差距，并将NLA和TOA的研究人员聚集在一起，促进可能对数据分析产生直接和长期影响的想法的交流。为此，PIS将致力于一组原型研究问题，这些问题可以从NLA和TOA的想法和研究中显著受益。这些问题包括通过元素采样逼近矩阵的奇异值和向量，基于随机投影的最小二乘算法，以及广泛使用的非负矩阵分解的随机化算法的设计。该建议试图探索数值线性代数和算法理论(TOA)社区给线性代数和矩阵计算带来的互补视角。这是一个及时的探索，受到过去20年来允许自动生成大型数据集的技术发展的推动。这样的数据集通常被建模为矩阵。拟议的工作将作为一个示范项目，展示全国解放军和托阿社区在共同感兴趣的问题上进行合作的成果。预计拟议的研究将证明这两种方法的共同点，并突出双重视角的优势。通过外展活动，PIS希望激励更多的研究人员对相关主题进行类似的调查。所提出的算法将在过去几年中PI一直在研究的应用领域的一组矩阵上进行数值评估，以便更好地了解它们的性质，并展示它们在处理现代海量数据集方面的潜力。更具体地说，PIS将测试拟议的群体遗传学数据策略，以推断个人的祖先，以及基因表达数据，以调查基因与疾病相关的假说。因此，我们预计开发的算法将影响线性代数、随机算法、信息检索和数据挖掘以及生物信息学领域。最后，为了传播拟议的研究，私人投资机构打算组织研讨会(效仿2006年、2008年和2010年的现代海量数据集算法研讨会；私人投资机构是这些研讨会的共同组织者)和工作组会议，并将通过博客和面向更广泛受众的文章传播其研究成果。

Data matrices have structural properties that present challenges and opportunities for both the Numerical Linear Algebra (NLA) community and the Theory of Algorithms (ToA) community. Matrix factorizations, such as the eigendecomposition, the rank-revealing QR factorization, and the Singular Value Decomposition, have been widely used for information retrieval. Historically, matrix factorizations have been of central interest in NLA since one can use them to express a problem in such a way that it can be solved more easily. ToA, on the other hand, has recently addressed the computation of such decompositions from a sampling perspective. The two approaches are complementary. However, thus far, the two communities have not worked closely together to integrate them. More often than not, each community is only cursorily aware of developments in the other community. Defining significant research directions that both communities can work on, and applying the resulting linear algebraic algorithms to data analysis problems (among others) will lead to important breakthroughs. The main objective for this proposal is to bridge the existing gap and bring together NLA and ToA researchers to promote cross-fertilization of ideas that could have immediate and long-term impact on data analysis. Towards that end, the PIs will work on set of prototypical research problems that can significantly benefit from ideas and research in both NLA and ToA. These problems range from approximating the singular values and vectors of a matrix by element-wise sampling to random-projection-based algorithms for least-squares problems and the design of randomized algorithms for the widely used non-negative matrix factorization.This proposal seeks to explore the complementary perspectives that the Numerical Linear Algebra and the Theory of Algorithms (ToA) communities bring to linear algebra and matrix computations. This is a timely quest, motivated by technological developments over the last two decades that permit the automatic generation of large datasets. Such datasets are often modeled as matrices. The proposed work will serve as a demonstration project on the fruitfulness of collaboration between the NLA and the ToA communities on problems that are of common interest. It is expected that the proposed research will demonstrate commonality in the two approaches, as well as highlight the advantages of the dual perspective. Through outreach activities, the PIs hope to motivate even more researchers to undertake similar investigations on related topics. The proposed algorithms will be numerically evaluated on a suite of matrices from application domains that the PIs have been working on over the past few years, in order to understand better their properties and to demonstrate their potential in dealing with the modern, massive datasets. More specifically, the PIs will test the proposed strategies on population genetics data in order to infer ancestry of individuals, as well as gene expression data in order to investigate hypotheses that correlate genes and diseases. As such, we expect that the developed algorithms will impact the areas of linear algebra, randomized algorithms, information retrieval and data mining, as well as bioinformatics. Finally, in order to disseminate the proposed research, the PIs intend to organize workshops (following the example of the Workshops on Algorithms for Modern Massive Datasets in 2006, 2008, and 2010; the PIs were co-organizers of these workshops) and working group meetings, and will disseminate their research via blogs and articles intended for broader audiences.