这篇论文主要贡献点在于应用稀疏表示理论来构建图，并提供了一种比较常用的优化算法，相关论文和代码见http://www.escience.cn/people/fpnie/papers.html（尤其是优化算法的代码，很多地方都能用到）

Abstract

1

图理论是数学的一个重要分支，基于图理论产生了很多算法及应用（聚类算法、半监督学习等），本文仅将讨论范围约束在可以转化成相似度矩阵的数据集；
目前针对拉普拉斯图的构造存在的问题，有些方法解决了一部分的问题，如：Self-tuning spectral clustering 解决了如何确定分析的规模及如何处理多尺度的数据，但是尚无方法解决所有的问题；
后文将先做铺垫，然后介绍 Simplex Sparse Representation (SSR)方法，并介绍一种新的加速算法。

这一部分介绍稀疏表示的形式，假设数据点为 $d\times n$ 的矩阵， $d$ 为特征， $n$ 为数据点个数。给出一个新的稀疏表示 $y$ 和表示向量 $\beta$ ，为了得到稀疏解，加上零范数的约束，得到目标函数： $\min_{\beta} \left \| X\beta -y\right \|_{2}^{2}+\lambda _0\left \| \beta \right \|_0$
$L_0$ 范数可以近似转化成 $L_1$ 范数的形式，这样可以更容易进行优化求解（可以参考这篇博客https://blog.csdn.net/zouxy09/article/details/24971995）： $\min_{\beta} \left \|\beta\right \|_{1}, s.t. X\beta=y$ 或者是： $\min_{\beta} \left \| X\beta -y\right \|_{2}^{2}+\lambda _1\left \| \beta \right \|_1$
稀疏表示具有鲁棒性，且对数据的规模一致性没有限制，这样可以解决引言中提出的问题。

普遍使用的高斯核函数在构建相似度矩阵时，对于参数十分敏感且难以调参。
可以应用稀疏表示来计算相似度矩阵 $S$ ，第 $i$ 个特征和其他特征之间的相似度 $\alpha_i\in \mathbb{R}^{n-1}$ 表示为：（此处论文是这么写的，但我感觉是笔误吧？应该是第 $i$ 个数据点和其他数据点之间的相似度吧） $\min_{\alpha_i} \left \| X_{-i}\alpha_i -x_i\right \|_{2}^{2}+\lambda _1\left \| \alpha_i \right \|_1$ 其中 $X_{-i}$ 表示不含点 $x_i$ 的数据矩阵。
加入非负约束 $\alpha_i\geq 0$ ，同时考虑到，数据点均等的发生变换的时候，相似度应该是不变的，因此应该再加上约束 $\alpha_i^T\mathbf {1}=1$ ，这样就有： $\min_{\alpha_i} \left \| X_{-i}\alpha_i -x_i\right \|_{2}^{2}+\lambda _1\left \| \alpha_i \right \|_1\\s.t. \alpha_i\geq 0,\alpha_i^T\mathbf {1}=1$ 这其中的约束可以让第二项保持固定，因此变为： $\min_{\alpha_i} \left \| X_{-i}\alpha_i -x_i\right \|_{2}^{2}\\s.t. \alpha_i\geq 0,\alpha_i^T\mathbf {1}=1$
上述目标函数引入了稀疏解，可以用加速投影梯度法来进行优化求解，下一节将对这种方法进行介绍。