核（迹）范数

核范数是对一个矩阵奇异值最简单的概括：把它们全部加起来。||A||_* = sigma_1 + sigma_2 + ... + sigma_r。谱范数取最大值，弗罗贝尼乌斯范数取平方和的根，而核范数取朴素的和。这三者正是 Schatten 无穷、2、1 范数——把同一个 lp 思想用在奇异值向量上。

它的主角戏份是充当秩的凸替代。直接最小化秩是组合性的、NP 困难的；秩计的是有多少个奇异值非零，这是个不连续、非凸的东西。核范数是逼近秩的最紧凸函数（它在谱范数单位球上的凸包络），正如 l1 范数是统计向量中非零元素个数的凸替代。

这正是矩阵补全的动力。给定一个大部分元素缺失的矩阵（想想一张你要填补的评分表），你寻找既匹配已观测元素、又具有最小核范数的矩阵。由于最小化核范数会推向低秩，你便恢复出一个有结构的低秩补全——而且了不起的是，在温和条件下你能精确恢复真实矩阵。这正是 Netflix 式推荐突破背后的引擎。

实用上的吸引力在于：核范数最小化是一个凸优化问题，因而有可由可靠求解器达到的全局最优，不像无从下手的直接秩最小化。你以精确性上的小小代价，换来可解性上的巨大收益。