在本文我们将探讨两种适合大规模计算的框架——矩阵的低秩近似和在线学习——来解决机器学习中的两个重要问题:非监督学习与监督学习。对大规模矩阵进行特征值分解是在非监督学习中最经常遇到的问题,例如核主成分分析,谱聚类。但是其三次方的算法复杂度阻碍了其在大规模数据集上的应用。另一方面,支持向量机是在监督学习中是最常用的方法。在大规模数据集中,稀疏性规约通常用来保证模型不会过拟合。然而,稀疏性规约的加入则使得优化算法异常复杂。Nystr?m方法是一个有效的对大规模核矩阵进行特征值分解的手段。但是,为了保证足够的的近似精度,Nystr?m方法需要从核矩阵中采样足够多的列。而在大数据集上,作用在采样的子矩阵上的SVD算法会很快凸显出耗时的缺点,以致于严重到影响Nystr?m方法的效率。在这篇文章里,我们通过使用一个近似的奇异值分解算法来对Nystr?m方法进行改进,使其可以被高效地应用在超大规模的数据集上。理论分析表明该改进后的算法和标准的Nystr?m方法一样精确。一系列在大规模数据集上的测试验证了该算法的以上特性。此外,我们还将其从在CPU上运行扩展到了在GPU上运行,从而使得8百万8百万的核矩阵可以在1分钟之内被很好的近似。Nystr?m方法的一个重要应用是在谱聚类上。然而,当数据量足够大时,谱聚类处理和存储采样列的代价仍然非常昂贵。在这篇文章里,我们提出了一个在时间和空间上同时高效的算法,使得谱聚类可以被应用在超大规模数据集上。同时被提出的还有一个一般化的正交化方法,该方法用于正交化近似得到的特征向量。我们对大量的规模从数万到数百万的数据集,进行了谱聚类实验,来测试并验证了该算法的准确和高效。更进一步,我们将其应用到图片分割上。该算法可以在1台机器上,于1分钟之内,处理千万像素的图片。多样例学习是一个最近提出的监督学习框架,与传统的监督学习相比,前者能处理模糊的标号。一般来说,多样例学习被应用在离线的学习框架下。但是,诸如物体跟踪等应用并不能作用于离线框架下。因此,在基于已有成功应用的离线多样例学习算法MILES上,我们提出了一个在线的多样例学习算法。其通过在线的方法来对一个有稀疏性规约的支持向量机求解。该算法有的(累计)后悔量上界,即,能很快收敛,且该算法性能达到了最佳解法;这里表示迭代次数。算法的有效性在多样例分类和物体跟踪实验中被证明。