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

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

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.