限 时 特 惠： 本站每日持续更新海量各大内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： muyang-0410
1向量范数
1.1定义
1.2计算方法
向量的范数可以理解为向量的长度，或者向量到零点的距离。P范数的计算公式如下：
下图展示了p取不同值时，单位球（unitball，到原点距离（范数）为1 的点的集合）。
下图是不同范数的变化曲线：
从图中可以看出p
1.3常用的范数
首先我们定义一个向量 v = [-5,7,8,-6]
L0范数：指向量中非0元素的个数，是一种度量向量稀疏性的方法，则v的L0范数是0。
L1范数：是向量中各个元素的绝对值之和，对应的是曼哈顿距离，则v的L1范数是26.
L2范数：是向量中每个元素的平方，求和，后开方，对应的是欧式距离。则v的L2范数是sqrt(25+49+64+36)=13.2
L♾范数：向量中元素的最大值，对应着切比雪夫距离。V的L♾范数是♾。
Lp范数对应着闵式距离。
1.4模型空间的限制（正则化）
最简单的线性模型是用范数进行规范化，减小过拟合，那范数到底是怎么对模型进行这个规范化得呢？
线性模型使用最小二乘来进行学习，就是最小化：
模型发生过拟合时矩阵范数的定义，我们最常用的是L2正则化，也就是岭回归，在损失函数中添加一个正则化项，如下所示：
添加的正则化项使得模型偏向选择范数较小的W。从凸优化的角度，最小化的上述的损失函数等价于：
其中C是和λ对应的常数。通过限制W的范数的大小实现了对模型空间的限制，从而在一定程度上（取决于λ的大小）避免了过拟合。岭回归并不具有产生稀疏解的能力，得到的系数W仍然需要数据中的所有特征才能计算预测结果，从计算量上来说并没有得到改观。
若想产生稀疏解，应使用L1范数替代L2范数，得到的损失函数如下：
这就是LASSO (least absolute shrinkage and selection operator)回归。LASSO 仍然是一个凸优化问题，但不具有解析解。它的优良性质是能产生稀疏性，导致 W中许多项变成0。上面的也可写成：
我们将模型空间限制在 W的一个 L1-ball 中。考虑两维的情况，在（w1,w2
平面上可以画出损失函数的等高线，而约束条件则成为平面上半径为 C的一个 norm ball 。等高线与 norm ball 首次相交的地方就是最优解。如下图所示：
L1-ball 与L2 -ball的不同就在于他在和每个坐标轴相交的地方都有“角”出现，除非损失函数的测地线位置摆得非常好，否则都会在角的地方相交。注意到在角的位置为产生稀疏性，例如图中的相交点就有w1=0，而更高维的时候（想象一下三维的L1 -ball是什么样的？）除了角点以外，还有很多边的轮廓也是既有很大的概率成为第一次相交的地方，又会产生稀疏性。
相比之下，L2-ball 就没有这样的性质，因为没有角，所以第一次相交的地方出现在具有稀疏性的位置的概率就变得非常小了。这就从直观上来解释了为什么L1正则化能产生稀疏性，而L2正则化不行的原因了。
我们再看下Lasso回归的损失函数：
要求损失函数的最优解，只要导数等于0就可以了，但是L1范数在0点处是连续不可导的，没有梯度，那我们退而求其次，用次梯度（sub-gradient）,它的定义是：
注意：次梯度和次微分都是对凸函数而言的。例如我们有函数f(x)=|x|,则在x=0处的次微分（subdifferential）就是[-1,1]。如下图，在x0点处的不同的红线表示次梯度的大小，有无穷多个。而在梯度存在的位置，次微分是由次梯度构成的单点集合。
次梯度的性质：
很好理解，如果x0不是全局最小值，那么次微分中不包含0。我们将0带入到前面的定义1中，则有f(x)>f(x0)，所以如果某点的次微分中包含0，则函数在该点取得最小值。
为了方便说明，我们假设数据X的列向量是正交的，并且满足：
这样线性回归的最优解可以写作：
我们假设：
是lasso回归的全局最优解，考虑其中的第j个变量，则有两种情况：
1、gradient 存在，此时
2、gradient 不存在，此时
可以推导得出：
其中：
对于岭回归来说，因为正则化项是可导的，可以推导其结果为：
两种正则化方式对线性回归的预测结果的影响如下图所示：
从图中可以看出 ridge regression 只是做了一个全局缩放，而 LASSO 则是做了一个 soft thresholding ：将绝对值小于λ/2的那些系数直接变成0了，这也就解释了 LASSO 为何能够产生稀疏解了。
参考：#67364f6b44ff80f9f952d5a46f2307425d2ee9ac
2矩阵范数2.1定义
注意：矩阵范数最好是参考相关论文中的规定
2.2常用范数
1、矩阵的L0范数：指矩阵的非0元素的个数，通常用来表示矩阵稀疏性
2、矩阵的L1范数：矩阵中的每个元素绝对值之和，它是L0范数的最优凸近似，可近似表示稀疏性
3、矩阵的F范数（L2范数）：矩阵的各个元素平方之和再开平方根，是凸函数，可微分，易于计算
最小化F范数，会使矩阵中的每个元素都很小。
应用：可用||A-B||的F范数度量A，B矩阵之间的差异，最小化可使两者尽可能相等
4、矩阵的核范数：矩阵的奇异值之和，最小化核范数可导致矩阵低秩。
奇异值是SVD分解后的结果
5、矩阵的L2,1范数：矩阵先以每一列为单位，求每一列的F范数（向量的L2范数），然后再将得到的结果求L1范数（向量的L1范数），它是介于L1和L2之间的一种范数
最小化L2,1范数可使矩阵行内元素互斥，可用于特征选择时不同的类别选择互斥的特征
2.3核范数的应用
矩阵的秩是矩阵的行列相关性的度量。若矩阵的行或列之间没有线性关系，则矩阵是满秩的，即秩等于行数或列数。
低秩矩阵:如果矩阵X是一个m行n列的数值矩阵，rank(X)是X的秩,假如rank(X)远小于m和n，我们称X是低秩矩阵。低秩矩阵的每行每列都可以使用其他的列或行表示出来，包含大量的冗余信息，利用这些冗余信息可以对缺失的数据进行恢复，也可以对数据进行特征提取。
如下图所示：通过初等变换将左侧的矩阵转化为阶梯形矩阵，若该阶梯形矩阵有r个非零行，那A的秩就等于r。
但是矩阵的秩是非凸的，在优化问题里很难求解，需要找到的它的凸近似，也就是核范数。核范数的应用如下所示：
1 矩阵填充
矩阵填充的两个应用是图像修复和基于协同过滤的推荐系统中。
图像修复就是通过矩阵填充的方式将打码或损坏的图像修复成原来的图片，如下所示：
基于协同过滤的推荐算法：该方法是通过分析用户的历史记录来给用户做推荐。比方说我们拿电影推荐来说，我们构建一个用户-电影的评分矩阵，来记录用户看过哪些电影，并给电影进行了评分，我们有很多用户，也有很多的电影，用户不可能看过所有的电影，也不是所有的电影都能得到用户的评分。那构建的矩阵就会有很多空白的地方，如下图所示：
一般情况下，我们在分析前会将该矩阵进行填充，那怎么做呢？我们利用低秩重构的方法，比如一个用户对某部电影的评分是其他用户对这部电影评分的线性组合，所以通过低秩重构可以预测用户对其未评价过的电影的喜好程度，从而对矩阵进行填充。
3 鲁棒PCA
与经典PCA一样，Robust PCA（鲁棒主成分分析）本质上也是寻找数据在低维空间上的最佳投影问题。当观测数据较大时，PCA无法给出理想的结果，而Robust PCA能够从较大的且稀疏噪声污染的观测数据中恢复出本质上低秩的数据。Robust PCA考虑的是这样一个问题：一般的数据矩阵D包含结构信息，也包含噪声。那么可以将这个矩阵分解为两个矩阵相加:D = A + E，A是低秩的（由于内部有一定的结构信息造成各行或列间是线性相关的），E是稀疏的（含有噪声，则是稀疏的），则Robust PCA可以写成以下的优化问题：
由于rank和L0范数在优化上存在非凸和非光滑特性，所以一般将这个NP问题转换成求解一个松弛的凸优化问题：
对于低秩数据观测矩阵D，假如D受到随机（稀疏）噪声的影响，则D的低秩性就会破坏，使D变成满秩的。所以就需要将D分解成包含其真实结构的低秩矩阵A和稀疏噪声矩阵E之和。找到了低秩矩阵，实际上就找到了数据的本质低维空间，那么Robust PCA的Robust在哪呢？因为PCA前提假设的数据的噪声是高斯的矩阵范数的定义，对于大的噪声或者严重的离群点，PCA会被它影响，导致其无法正常工作。而Robust PCA则不存在这个假设（Robust PCA假设噪声是稀疏的，而不管噪声的强弱）。
4 背景建模
背景建模的最简单情形是从固定摄相机拍摄的视频中分离背景和前景。我们将视频图像序列的每一帧图像像素值拉成一个列向量，那么多个帧也就是多个列向量就组成了一个观测矩阵。由于背景比较稳定，图像序列帧与帧之间具有极大的相似性，所以仅由背景像素组成的矩阵具有低秩特性；同时由于前景是移动的物体，占据像素比例较低，故前景像素组成的矩阵具有稀疏特性。视频观测矩阵就是这两种特性矩阵的叠加，因此，可以说视频背景建模实现的过程就是低秩矩阵恢复的过程。
5 变换不变低秩纹理
低秩纹理映射算法(TransformInvariant Low-rank Textures，TILT)是一种用低秩性与噪声的稀疏性进行低秩纹理恢复的算法。它的思想是通过几何变换τ把D所代表的图像区域校正成正则的区域，如具有横平竖直、对称等特性，这些特性可以通过低秩性来进行刻画。
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： muyang-0410
