CUR矩阵分解

1. Intuition

SVD缺点：

1. 可解释性差。
2. 太过Dense。

SVD: $X=U\Sigma V^T$，其中$U,V$都是Big and Dense，$\Sigma$是Small But Sparse。

Aims to Get:

CUR: $X=CUR$，其中$C,R$都是Big but Sparse，$U$是Small and Dense。

Rough Intuition:

CUR选的点可能是更偏离远点的，同时坐标轴可能是多余的。

2. Proof

TL;DR.

详见CUR理论公式推导。

3. Algo

Given Input Matrix A:

1. Randam choose, C columns, R rows.
2. $C\cap U$ intersection point matrix $W$.
3. SVD Decomposition $W=X\Sigma Y^T$
4. Derive Generalized inverse matrix of $\Sigma^{+} $ via $\Sigma$, i.e. non-zero elements turn to its countdown
5. Derive $U=Y{\Sigma }^{+}{X}^T$
6. $A=C\cdot U\cdot R=C\cdot Y\cdot {\Sigma }^{+}\cdot X^T\cdot R$

4. Remarks

第一步关于如何选择C,R

• Mahoney等人提出可以里用normalized statistical leverage scores${\pi }_j=\frac{1}{k}{\sum }_{\eta =1}^k=(v_{\eta }^i{)}^2$，i.e.该列/行的二范数占所有列数二范数的比例，作为衡量其统计影响力的指标。也即square of its Frobenius norm。

• 苏剑林解读论文

  可能有读者想问“有代表的q,kq,k要怎么选？”，事实上，大多数情况下都是随机选的，这就留下了一些提升空间，比如可以聚类后选最接近聚类中心的那个，这些就看大家自由发挥了。另外要指出的是，CUR分解本身只是一种近似，它肯定有误差，所以该加速方案主要是为检索场景设计的，检索场景的特点是比较在乎topk的召回率，而不是特别要求top1的精确率，我们可以用CUR分解加速来召回若干个结果后，再用精确的s(q,k)做一次重排序来提高准确度。

第四步关于广义逆矩阵

也有文献表示QR分解更稳定。

Experiments

不放回抽样的CUR效果最好。同时保证了效率和精度。对于large sparse matrix有很不错的效果。

Reference

CUR matrix decompositions for improved data analysis

利用CUR分解加速交互式相似度模型的检索

Dimensionality_Reduction

CUR矩阵分解 (对比SVD)

Sublinear Time Approximation of Text Similarity Matrices

Semantic Representation of Documents Based on Matrix Decomposition

CUR分解算法及Python实现