III: Small: Fast and Efficient Algorithms for Matrix Decompositions and Applications to Human Genetics

线性代数算法，特别是矩阵分解，已经证明在矩阵形式的数据集的分析中非常成功。奇异值分解（SVD）和相关的主成分分析（PCA）等工具在从网络搜索引擎到物理科学的各个领域都产生了深远的影响。在过去的十年中，随机化的引入为此类算法的设计和分析提供了新的范例。另一方面，人类遗传学研究人员现在正在发现我们彼此之间的真正差异。描述人类遗传变异的常见模式的大型数据集可以很容易地被认为是矩阵，行代表个体，列代表基因组中与常见多态性相对应的基因座。这些数据集的更广泛的影响怎么强调都不过分：它们有望成为研究人员的关键资源，用于寻找影响健康、疾病以及对药物和环境因素的反应的基因，以及了解我们物种的进化和生物学历史。本提案的主要目标是弥合理论计算机科学和应用数学界开发的最先进的数据分析算法与将此类算法应用于分析人类遗传学界日益庞大的数据集之间的差距。我们的建议的特别重点是，从算法的角度来看，设计和分析（监督和无监督）的随机算法，所谓的CX矩阵因子分解，并从人口遗传学的角度来看，选择祖先信息和疾病相关的标记，以及祖先和情感状态预测。这项工作将对群体遗传学数据的分析产生直接影响。研究结果将被广泛传播给应用数学家、理论计算机科学家和人口遗传学家

Linear algebraic algorithms, and in particular matrix decompositions, have proven extremely successful in the analysis of datasets in the form of matrices. Tools such as the Singular Value Decomposition (SVD) and the related Principal Components Analysis (PCA) have had a profound impact in diverse areas, ranging from web search engines to the physical sciences. Over the last decade, the introduction of randomization provided a new paradigm for the design and analysis of such algorithms. On the other hand, human genetics researchers are now finding out how truly different we are from one another. Large datasets describing the common patterns of human genetic variation may be easily thought of as matrices, with the rows representing individuals and the columns representing loci in the genome that correspond to common polymorphisms. The broader impact of such datasets can not be overemphasized: they are expected to be a key resource for researchers to use to find genes affecting health, disease, and responses to drugs and environmental factors, as well as understanding the evolutionary and biological history of our species. The main objective of this proposal is to bridge the gap between state-of-the-art algorithms for data analysis developed in the theoretical computer science and applied mathematics communities and the application of such algorithms to the analysis of the increasingly larger volume of datasets in the human genetics community. The particular focus of our proposal is, from an algorithmic perspective, the design and analysis of (supervised and unsupervised) randomized algorithms for the so-called CX matrix factorization, and, from a population genetics perspective, the selection of ancestry informative and disorder associated markers, as well as ancestry and affection status prediction. This work will have immediate impact in the analysis of population genetics data. The results will be disseminated to a broad community of applied mathematicians, theoretical computer scientists, and population geneticists