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