理论分析IRLS迭代加权最小二乘法（根据Gorodnitsky and Rao）
最近在拜读Michael Elad的《Sparse and Redundant Representations》，里面关于IRLS的讲解比较透彻（根据Gorodnitsky and Rao的理论），从理论到算法的过程，和大家分享一下。知识水平有限，望各位指出错误，不吝赐教。
一. 阅读以下内容需具备的知识基础
1. SVD分解
可以参考：https://www.cnblogs.com/xiaohuahua108/p/6137783.html?utm_source=itdadao&utm_medium=referral（此链接未经原作者允许，请见谅。若原作者看到此引用认为不妥，请告知，笔者将第一时间处理）。
2. 伪逆
可以参考：：https://blog.****.net/you1314520me/article/details/78857759。（此链接未经原作者允许，请见谅。若原作者看到此引用认为不妥，请告知，笔者将第一时间处理）。
二. IRLS是什么？
IRLS是Iterative-Reweighed-Least-Squares是缩写，由Gorodnitsky and Rao提出，是FOcal Underdetermined System
Solver (FOCUSS) algorithm家族中的方法之一，主要作用顾名思义是解决欠定系统问题，也就是众所周知的P0问题。该方法属于凸松弛（Convex Relaxation）技术，其核心思想是通过将L0-norm松弛化（relaxation），把高度不连续的问题松弛化为连续的甚至是光滑逼近（smooth approximation）。
三. IRLS详解
一种L0-norm松弛化的技术即是IRLS，该方法将代替为加权
。首先，构造对角矩阵
。在这里
是前一次迭代产生的近似解，将该解（列向量）的所有元素取绝对值的q次方，依次作为对角线元素，其余非对角线元素均为0，构造出
，例如：
假如主对角元素有0值，则
的逆不存在，则利用伪逆来代替，表示为
。为啥提到伪逆呢，因为要给
对角元素加上-q次方。对角方阵的伪逆，实际上是各个主对角元素分之一，例如：
在此，引入（符号使用不太规范，从这里开始都规范起来。。）。这时有
这里其实是范数运算和矩阵运算，不理解的话可以自己演算一下。可以看到，等式右侧是解的（2-2q）范数。特殊的，当q=1时，则。也就是说，可以利用
这个2范数来模拟（imitates）0范数。这个过程就是IRLS的核心思想。当然，剩下的过程也很重要。回到问题的最初，
，我们要求
是最稀疏的，也就是
最小，数学表示如下：
引入拉格朗日乘子，求最优解 ：
则有
因为只有对角线元素非零（当然对角线也可能有0元素），
可能不存在，但是取其伪逆，相当于是将非零对角线元素取-1次幂，那么又变为了
，因此才有上式。
此时另外一个问题出现了，此时的解中还含有未知量，需要将其消去。此时，可以将上式得到的解
代入到约束条件
中
得到了的表达式，将其代入到
中，得到
的最终表达式
此处使用伪逆代替，以防止不可逆。关于如何求伪逆，文章第一章推荐的博客有详细讲解，求伪逆需要用到SVD，因而也推荐了SVD详细讲解。
四. IRLS解
问题的策略