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