生活在大数据时代，而大数据给计算带来了巨大的挑战。许多经典的矩阵计算和机器学习方法由于时间复杂度、空间复杂度过高，故不适用于大数据问题。近年来矩阵数据的快速近似方法受到了广泛关注，多种快速近似方法被提出并被成功应用于加速矩阵计算和机器学习。矩阵快速近似方法采取用精度换时间、空间的策略，损失少量精度从而大大降低时间复杂度和空间复杂度。矩阵快速近似方法已经广泛用于加速特征分解、奇异值分解、矩阵求逆等矩阵计算操作，也广泛用于最小二乘法、矩阵恢复、高斯过程、核PCA、谱聚类、流形学习等机器学习方法。目前的研究热点及尚未解决的问题主要在于设计近似方法的模型和算法，从而使得近似造成的精度损失更小，以及使得近似本身能被更快速地求出。　　本文关注矩阵近似的模型、算法、以及快速矩阵近似在机器学习上的应用这三个方面。本文提出了多种快速矩阵近似的模型和算法，并在理论上证明模型和算法的优越性，并用大量实验予以验证。本文将矩阵近似的方法应用于加速子空间聚类和行列式点过程等机器学习问题，在理论和实验两方面都取得很大进步。本文的贡献概括如下:　　Nystr(o)m方法从2001年开始被用于机器学习领域，现在是加速核方法(kernel methods)最有效和最广泛使用的方法。本文证明出Nystr(o)m方法的理论误差下界，表明Nystr(o)m方法的误差有时会随矩阵大小线性增长;这是学术界的首次理论证明。　　本文提出对Nystr(o)m方法的一种有效改进，改进的方法的理论误差上界比以往方法优一个量级。此外，本文证明出该方法多种好的理论性质，并给出两种快速求解的算法。　　CUR矩阵分解是一种高效的非负矩阵分解。本文提出一种新的算法求解CUR，误差界和时间复杂度均比已有算法优一个量级。　　子空间聚类是一种广泛使用的无监督学习方法，但已有算法时间复杂度全都是平方或立方，而且只有少数有理论保证。本文提出一种基于数据选择的随机算法加速子空间聚类，算法时间复杂度仅为线性，是目前最快的算法。通过结合一种高效的去噪方法，本文的算法不仅速度最快，而且理论误差界大大优于现有所有算法。　　行列式点过程(DPP)是统计学、人工智能领域一种重要的随机过程，但其采样算法时间复杂度过高。本文提出一种快速近似算法，在保证速度的同时，该算法的误差界优于已有近似算法。