在例如推荐系统,图像／视频分析等许多机器学习问题中,数据往往是以矩阵的形式进行表达。在这些问题中,矩阵的低秩性质在学习原始数据隐藏结构的过程中有着非常重要的作用。因此,近来针对低秩矩阵算法成为机器学习和相关领域的一个研究热点。低秩近似算法大致上可以被分为两类：(1)恢复数据(很可能是不完整的)中的低秩结构；(2)利用低秩信息提升其他机器学习模型的学习效果。虽然在这两类算法中目前已经有很多相关工作,但是不管从准确性还是效率来看,已有的算法都并不能达到让人满意的效果。在本论文中,我们从算法理论分析到具体的应用对低秩近似算法进行了一个系统的研究,研究内容包括矩阵补全问题,主动学习和基于低秩矩阵正则化的大规模图像分类问题。总的来说,本文的创新点如下：1.为了加速针对大规模矩阵补全问题的奇异值截断式算法(Singular Value Thresholding, SVT),在本论文中我们提出了一种奇异值截断式加速算法(Accelerated Singular Value Thresholding, ASVT)将传统的SVT算法的收敛速度从O(1/N)提升至O(1/N2),其中N是优化过程中的迭代次数。具体而言,通过理论分析我们证明了原始优化问题的最优解可以通过其对偶问题的最优解直接得到。我们在人工数据集,真实距离矩阵数据集和电影推荐数据集上进行一系列的验证,实验结果证明了我们所提出算法的效率和有效性。2.为了更好地解决基于截断式核范数的矩阵补全问题,本论文首先对原始截断式核范数优化问题进行重构。原始优化问题中的多个限制条件会减缓基于乘子的交替方向理论(Alternating Direction Method of Multipliers, ADMM)的收敛速度,并会对解的准确性造成一定的影响。随后,我们对重构后的问题提出了一个带自适应惩罚项的ADMM算法(Alternating Direction Method of Multipliers with Adaptive Penalty, ADMMAP)。在每一次迭代中,我们根据一个迭代机制调整目标函数中的惩罚项大小,从而加速算法收敛速度。我们在人工数据集和真实数据集的实验分析证明了,同已有的矩阵补全算法相比,我们提出的算法具有更好的效果。3.为了更好地在数据集中选择最具代表性的样本(我们称之为锚点),本论文提出在锚点的选择过程中充分考虑数据的局部信息,并设计了一种基于近邻重建的主动学习方法(Active Learning via Neighborhood Reconstruction, ALNR)。传统基于重建的主动学习理论利用所有的锚点对目标数据进行重建。然而,离目标数据越近的锚点对数据重建的作用越大,而离目标数据较远的点对数据重建的作用较小甚至有负面的作用。因此,在我们提出的ALNR算法中,我们仅仅只使用目标数据的近邻锚点对目标数据进行重建。为更好地求解最终的优化问题,我们提出了一种高效的两步迭代机制。我们在人工和真实数据集上的实验效果证明了我们算法比已有的主动学习算法更加准确高效。4.为了更好地在图像分类问题中利用矩阵的低秩信息,本论文考虑当分类器系数空间存在低维结构时的图像分类问题。当前已有的算法往往利用矩阵的核范数来刻画分类器系数矩阵的低秩结构。然而,考虑核范数并不能对矩阵秩算子进行很好地近似,我们提出了一种基于截断式核范数的大规模图像分类算法。为了求解最终非凸非光滑的优化问题,我们设计了一个高效的算法将原始问题首先分解为多个非光滑凸子问题,并进行迭代优化求解。在每一次迭代中,我们将每一个子问题转化为一个无线维空间下的l1范数正则化问题,并使用一种简单高效的加速坐标梯度下降算法进行求解。我们在若干大规模数据图像数据集上进行了测试,实验结果显示同已有的大规模图像分类算法相比,我们提出的算法有效地提升了大规模图像分类系统的准确性。