许多机器学习问题的目标都是要寻找具有低秩结构的矩阵,例如矩阵恢复、协同过滤、多任务学习等。这类问题可以通过核范数正则的优化问题来求解,它的优化目标是核范数与某损失函数之和。然而,核范数本身的非平滑性质、以及其昂贵的求梯度运算给核范数正则相关算法的实现带来一系列挑战。在此背景下,本文针对高维数据下的核范数正则极小化问题,进行了如下几方面的研究。当矩阵的维度(记作m×n)变得很高时,现有的基于梯度的算法就不再高效。因为这些算法在求解时需要计算矩阵的奇异值分解,其时间复杂度为矩阵维数的三次方O(m2n)。为了降低计算开销,本文利用核范数的变分性质,将原优化问题重新表达成极大极小问题,并设计了一个基于次梯度的免奇异值分解的算法。由于该算法在每步迭代时只需计算最大的奇异向量,故其时间复杂度降低到矩阵维度的平方O(mn)。据我们所知,对于无平滑假设的核范数优化问题而言,这是首个避免求解完全奇异值分解的算法。本文对这个算法的收敛性进行了理论分析,并且证明了该算法的收敛速率为O(1/(?)),其中T是算法迭代的次数。除此之外,本文在原有算法的基础上进行了改进和拓展,使其可以适用于随机情形和稀疏情形。其中随机情形是指仅能得到目标函数的随机次梯度值,稀疏情形是目标函数包含诸如l1范数的非平滑正则项。在这两种扩展之下,本文证明了各自算法的计算复杂度和收敛速率保持不变。最后,在鲁棒低秩矩阵近似和连接预测问题中,本文通过实验验证了算法的有效性。