l 1 l_1 l1-norm， 作为 l 0 l_0 l0-norm 的最紧凸近似，在压缩感知中非常常用。 例如求解问题： a r g m i n x A x = b s . t . ∣ x ∣ 0 ≤ n \mathrm{argmin}_x Ax = b \quad \mathrm{s.t.} |x|_0\le n argminxAx=bs.t.∣x∣0≤n 即待求解向量 x x x是一个稀疏向量， 其非零元素个数不超过 n n n个。 一种基于LASSO的做法是将问题改写为： a r g m i n x ∣ ∣ A x − b ∣ ∣ 2 2 + λ ∣ x ∣ 1 \mathrm{argmin}_x ||Ax-b||_2^2 + \lambda |x|_1 argminx∣∣Ax−b∣∣22+λ∣x∣1 其中 λ \lambda λ是一个人工变量， 可通过改变其大小改变对稀疏条件的重视程度。 注意， 这里将不可导、非凸的零范数放松为了一范数。 也因此，改写后的问题是一个可导的问题。
最简单的情况下， x x x为实数向量。 此时， 1-范数的导数很容易由定义得到： ∣ x ∣ 1 = ∑ ∣ x i ∣ |x|_1=\sum |x_i| ∣x∣1=∑∣xi∣, ∂ ∣ x ∣ 1 x i = s i g n ( x i ) \frac{\partial |x|_1}{x_i} = \mathrm{sign}(x_i) xi∂∣x∣1=sign(xi).
本文考虑的是通信中更常见的情形， 即 x x x是一个复数向量。 此时， ∣ x i ∣ |x_i| ∣xi∣不再是 x i x_i xi的绝对值， 而是复数 x i x_i xi的模，即 x i x i ∗ \sqrt{x_ix_i^*} xixi∗ . 也就是说：(复数时求梯度为对变量的共轭求导） ∂ ∣ x ∣ 1 ∂ x i ∗ = ∂ ∑ x i x i ∗ ∂ x i ∗ = ( x i ) 1 2 ( x i ∗ ) − 1 2 2 . \frac{\partial |x|_1}{\partial x_i^*}=\frac{\partial \sum \sqrt{x_ix_i^*}}{\partial x_i^*} = \frac{(x_i)^\frac{1}{2}(x^*_i)^{-\frac{1}{2}}}{2}. ∂xi∗∂∣x∣1=∂xi∗∂∑xixi∗ =2(xi)21(xi∗)−21.
进一步更复杂一些的： 设 f = ∣ A x ∣ 1 f = |Ax|_1 f=∣Ax∣1， 求 ∂ f ∂ x ∗ \frac{\partial f}{\partial x^*} ∂x∗∂f。 设 A A A的第 i i i行为 a i a_i ai, 那么 [ A x ] i = a i x [Ax]_i=a_ix [Ax]i=aix, ∣ [ A x ] i ∣ = ( x H a i H a i x ) 1 2 |[Ax]_i|=(x^Ha_i^Ha_ix)^{\frac{1}{2}} ∣[Ax]i∣=(xHaiHaix)21, 因此， f = ∑ ( x H a i H a i x ) 1 2 f = \sum (x^Ha_i^Ha_ix)^{\frac{1}{2}} f=∑(xHaiHaix)21 对 f f f求微分， 有： d f = d t r ( ∑ ( x H a i H a i x ) 1 2 ) = t r ( ∑ d ( x H a i H a i x ) 1 2 ) df=d\mathrm{tr}(\sum (x^Ha_i^Ha_ix)^{\frac{1}{2}})=\mathrm{tr}(\sum d(x^Ha_i^Ha_ix)^{\frac{1}{2}}) df=dtr(∑(xHaiHaix)21)=tr(∑d(xHaiHaix)21) 而： d ( x H a i H a i x ) 1 2 = 1 2 ( x H a i H a i x ) − 1 2 ( d x H ) a i H a i x d(x^Ha_i^Ha_ix)^{\frac{1}{2}} = \frac{1}{2}(x^Ha_i^Ha_ix)^{-\frac{1}{2}}(d x^H) a_i^Ha_ix d(xHaiHaix)21=21(xHaiHaix)−21(dxH)aiHaix 代回， 得： d f = t r ( ∑ 1 2 ( x H a i H a i x ) − 1 2 a i H a i x ( d x H ) ) df =\mathrm{tr}(\sum \frac{1}{2}(x^Ha_i^Ha_ix)^{-\frac{1}{2}}a_i^Ha_ix(d x^H) ) df=tr(∑21(xHaiHaix)−21aiHaix(dxH)) 因此， ∂ f ∂ x ∗ = 1 2 ∑ ( x H a i H a i x ) − 1 2 a i H a i x . \frac{\partial f}{\partial x^*} =\frac{1}{2} \sum (x^Ha_i^Ha_ix)^{-\frac{1}{2}}a_i^Ha_ix. ∂x∗∂f=21∑(xHaiHaix)−21aiHaix.
再进一步的， 设 f = ∣ v e c ( A H X A ) ∣ 1 f = |\mathrm{vec}(A^HXA)|_1 f=∣vec(AHXA)∣1， 求 ∂ f ∂ X ∗ \frac{\partial f}{\partial X^*} ∂X∗∂f。 （注意， 如果 X X X是一个稀疏矩阵， 那么对其0范数的近似并不是直接 X X X的1范数， 而是 X X X向量化后的1范数。 因为一个矩阵的1范数是每列1范数的最大值， 而不是所有元素模的和。）
设 A A A的第 i i i列为 a i a_i ai, 那么 [ A H X A ] i j = a i H X a j [A^HXA]_{ij} = a_i^HXa_j [AHXA]ij=aiHXaj, 由于 f f f代表矩阵每个元素的模的和， 因此 f = ∑ i ∑ j ( a j H X H a i a i H X a j ) 1 2 f = \sum_i\sum_j(a_j^HX^Ha_ia_i^HXa_j)^{\frac{1}{2}} f=i∑j∑(ajHXHaiaiHXaj)21 同样地， 对 f f f求微分， 有：
d f = d t r ( ∑ i ∑ j ( a j H X H a i a i H X a j ) 1 2 ) = t r ( ∑ i ∑ j d ( a j H X H a i a i H X a j ) 1 2 ) df =d\mathrm{tr}(\sum_i\sum_j(a_j^HX^Ha_ia_i^HXa_j)^{\frac{1}{2}})=\mathrm{tr}(\sum_i\sum_j d(a_j^HX^Ha_ia_i^HXa_j)^{\frac{1} {2}}) df=dtr(i∑j∑(ajHXHaiaiHXaj)21)=tr(i∑j∑d(ajHXHaiaiHXaj)21)
而： d ( a j H X H a i a i H X a j ) 1 2 = 1 2 ( a j H X H a i a i H X a j ) − 1 2 a j H ( d X H ) a i a i H X a j d(a_j^HX^Ha_ia_i^HXa_j)^{\frac{1}{2}} = \frac{1}{2}(a_j^HX^Ha_ia_i^HXa_j)^{-\frac{1}{2}}a_j^H(dX^H)a_ia_i^HXa_j d(ajHXHaiaiHXaj)21=21(ajHXHaiaiHXaj)−21ajH(dXH)aiaiHXaj, 代回得
d f = t r ( ∑ i ∑ j 1 2 ( a j H X H a i a i H X a j ) − 1 2 a i a i H X a j a j H ( d X H ) ) df = \mathrm{tr}(\sum_i\sum_j \frac{1}{2}(a_j^HX^Ha_ia_i^HXa_j)^{-\frac{1}{2}}a_ia_i^HXa_ja_j^H(dX^H)) df=tr(i∑j∑21(ajHXHaiaiHXaj)−21aiaiHXajajH(dXH)) 因此， ∂ f ∂ X ∗ = ∑ i ∑ j 1 2 ( a j H X H a i a i H X a j ) − 1 2 a i a i H X a j a j H . \frac{\partial f}{\partial X^*} = \sum_i\sum_j \frac{1}{2}(a_j^HX^Ha_ia_i^HXa_j)^{-\frac{1}{2}}a_ia_i^HXa_ja_j^H. ∂X∗∂f=i∑j∑21(ajHXHaiaiHXaj)−21aiaiHXajajH.
