理论分析IRLS迭代加权最小二乘法（根据Gorodnitsky and Rao）一. 阅读以下内容需具备的知识基础二. IRLS是什么？三. IRLS详解四. IRLS解问题的策略

       最近在拜读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.csdn.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解

问题的策略