矩阵保序低秩近似（by 李奥迪 & 姚命宏）
背景
首先简单交代一下要研究的具体矩阵分析问题是怎样抽象出来的。对称(半)正定矩阵是我们的研究对象，它会在非常多的应用场景中出现。在推荐系统这种工业场景中，通常会组织许多人力来标注偏序数据集（用户-物品；用户-用户；物品-物品）。这种偏序数据集存在两个关键特征：
- 第一，因为人类只能够相对准确地判断相似性之间的相对大小，所以任意两个概念之间的具体相似性得分不重要，但是两个相似性得分之间的相对大小关系很重要；
- 第二，如果用具体的打分数据来量化任意两个概念之间的相似性，那么所有的打分数据构成的矩阵是一个对称矩阵，但是以概率1不是（半）正定或负定矩阵，而只是不定矩阵。也就是这个对称矩阵的所有特征值都是实数，且几乎一定有一些特征值是正的，有一些是负的。
N个版本之前的研究热点是对比学习。对比学习在如何学习偏序矩阵这个问题上的解决思路是利用各种局部性地、概率性地方式从偏序矩阵中采样得到所谓正负样本对，然后以随机梯度下降的方式调整表征，使得表征之间的向量相似性基本符合偏序矩阵中刻画的相似性排序。最后，在召回和精排阶段复用学习得到的相似性排序结果。
站在一个更高的角度来总结形形色色对比学习算法做的事情，可以发现它们都是尝试用一个对称半正定矩阵（即所有表征之间的内积矩阵，后面称为gram矩阵）来近似人工标注的偏序矩阵，并且一定要做到：保持gram矩阵中元素的相对大小排序同人工标注的偏序矩阵中元素的相对大小排序一致（后面简称这种性质为保序）；保持gram矩阵是一个低秩矩阵，即每个表征的向量维度要远小于被表征对象的集合大小。综上所述，我们抽象出了下面这个矩阵分析问题：
如果上面这个矩阵分析问题有解，并且存在高效地求解算法，那么就可以直接对矩阵B做特征值分解，从而获得d维的表征。这种做法的优点是直观的：元素间的相对大小关系完全得到保留，而不是近似保留。
先不考虑秩约束
定理1. 若矩阵A满足原问题中的条件，那么至少存在满秩正定矩阵B完全保序。
证明1. 采用构造性的证明。不失一般性地假设矩阵A的对角线元素单调递增:
对于不符合这个假设的矩阵，我们总是可以同时交换行和列使得该条件成立。记录交换过程后，构造结束后反交换过来即可。
结合条件中的，不难发现。