厚街网站建设报价/爱站工具包官网下载

$l_1$-norm， 作为 $l_0$-norm 的最紧凸近似，在压缩感知中非常常用。
例如求解问题：
$${\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{x}Ax=b\mathrm{s}.\mathrm{t}.|x{|}_0\le n$$
即待求解向量$x$是一个稀疏向量， 其非零元素个数不超过$n$个。
一种基于LASSO的做法是将问题改写为：
$${\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_x||Ax-b|{|}_2^2+\lambda |x{|}_1$$
其中$\lambda$是一个人工变量， 可通过改变其大小改变对稀疏条件的重视程度。 注意， 这里将不可导、非凸的零范数放松为了一范数。 也因此，改写后的问题是一个可导的问题。

最简单的情况下， $x$为实数向量。 此时， 1-范数的导数很容易由定义得到： $|x{|}_1=\sum |x_i|$, $\frac{\partial |x{|}_1}{x_i}=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}(x_i)$.

本文考虑的是通信中更常见的情形， 即$x$是一个复数向量。
此时， $|x_i|$不再是$x_i$的绝对值， 而是复数$x_i$的模，即$\sqrt{x_i{x}_i^{\ast }}$.
也就是说：(复数时求梯度为对变量的共轭求导）
$$\frac{\partial |x{|}_1}{\partial x_i^{\ast }}=\frac{\partial \sum \sqrt{x_i{x}_i^{\ast }}}{\partial x_i^{\ast }}=\frac{(x_i{)}^{\frac{1}{2}}(x_i^{\ast }{)}^{-\frac{1}{2}}}{2}.$$

进一步更复杂一些的：
设 $f=|Ax{|}_1$， 求$\frac{\partial f}{\partial x^{\ast }}$。
设$A$的第$i$行为$a_i$, 那么$[Ax{]}_i=a_{i}x$, $|[Ax{]}_i|=(x^H{a}_i^H{a}_{i}x{)}^{\frac{1}{2}}$, 因此，
$$f=\sum (x^H{a}_i^H{a}_{i}x{)}^{\frac{1}{2}}$$
对$f$求微分， 有：
$$df=d\mathrm{t}\mathrm{r}(\sum (x^H{a}_i^H{a}_{i}x{)}^{\frac{1}{2}})=\mathrm{t}\mathrm{r}(\sum d(x^H{a}_i^H{a}_{i}x{)}^{\frac{1}{2}})$$
而：
$$d(x^H{a}_i^H{a}_{i}x{)}^{\frac{1}{2}}=\frac{1}{2}(x^H{a}_i^H{a}_{i}x{)}^{-\frac{1}{2}}(d{x}^H)a_i^H{a}_{i}x$$
代回， 得：
$$df=\mathrm{t}\mathrm{r}(\sum \frac{1}{2}(x^H{a}_i^H{a}_{i}x{)}^{-\frac{1}{2}}{a}_i^H{a}_{i}x(d{x}^H))$$
因此，
$$\frac{\partial f}{\partial x^{\ast }}=\frac{1}{2}\sum (x^H{a}_i^H{a}_{i}x{)}^{-\frac{1}{2}}{a}_i^H{a}_{i}x.$$

再进一步的， 设 $f=|\mathrm{v}\mathrm{e}\mathrm{c}(A^{H}XA){|}_1$， 求$\frac{\partial f}{\partial X^{\ast }}$。
（注意， 如果$X$是一个稀疏矩阵， 那么对其0范数的近似并不是直接$X$的1范数， 而是$X$向量化后的1范数。 因为一个矩阵的1范数是每列1范数的最大值， 而不是所有元素模的和。）

设$A$的第$i$列为$a_i$, 那么 $[A^{H}XA{]}_{ij}=a_i^{H}X{a}_j$, 由于$f$代表矩阵每个元素的模的和， 因此
$$f=\sum _i\sum _j(a_j^H{X}^H{a}_i{a}_i^{H}X{a}_j{)}^{\frac{1}{2}}$$
同样地， 对$f$求微分， 有：

$$df=d\mathrm{t}\mathrm{r}(\sum _i\sum _j(a_j^H{X}^H{a}_i{a}_i^{H}X{a}_j{)}^{\frac{1}{2}})=\mathrm{t}\mathrm{r}(\sum _i\sum _{j}d(a_j^H{X}^H{a}_i{a}_i^{H}X{a}_j{)}^{\frac{1}{2}})$$

而：
$$d(a_j^H{X}^H{a}_i{a}_i^{H}X{a}_j{)}^{\frac{1}{2}}=\frac{1}{2}(a_j^H{X}^H{a}_i{a}_i^{H}X{a}_j{)}^{-\frac{1}{2}}{a}_j^H(d{X}^H)a_i{a}_i^{H}X{a}_j$$, 代回得

$$df=\mathrm{t}\mathrm{r}(\sum _i\sum _j\frac{1}{2}(a_j^H{X}^H{a}_i{a}_i^{H}X{a}_j{)}^{-\frac{1}{2}}{a}_i{a}_i^{H}X{a}_j{a}_j^H(d{X}^H))$$
因此，
$$\frac{\partial f}{\partial X^{\ast }}=\sum _i\sum _j\frac{1}{2}(a_j^H{X}^H{a}_i{a}_i^{H}X{a}_j{)}^{-\frac{1}{2}}{a}_i{a}_i^{H}X{a}_j{a}_j^H.$$