压缩感知的尽头: 原子范数最小化

前言

在之前的博客中，我们介绍了包括正交匹配追踪OMP、近似消息传递GAMP 等常见的压缩感知算法。 抛开复杂度不谈，对于压缩感知问题， 哪个算法拥有最佳的性能， 无疑是让人感兴趣的话题。 那么目前可以给出答案了： 压缩感知的尽头， 就是 原子范数最小化算法。 而其能在一众算法中登顶的原因也很简单： 它既是拥有优良凸优化性质的算法， 又没有精度的限制。 简单而言， 如果说 OMP 等在有限码本上选取码字的算法为 On-grid 类型。 那么 原子范数最小化算法，就是在无穷精度的范围内进行搜索， 即 Gridless 类型。 本文参考自 Zai Yang 博士的书 Sparse Methods for Direction-of-Arrival Estimation 第六章节。 因为笔者也是初次学习这一算法， 因此这篇博客更多是对原文的翻译。 后续如有机会， 希望给出自己更深入浅出的理解。

问题建模

首先，我们考虑的是通信中常见的 DOA 问题。 当然 原子范数最小化算法显然并不局限于这一种应用。 这只是一个生动的例子。 对于 M M M 根接收天线而言， 接收数据可表示为： Y = A ( f ) S + E Y=A(f) S+E Y=A(f)S+E Y ∈ C M × L Y\in\mathbb{C}^{M\times L} Y∈CM×L， 其中 L L L 代表接收时隙数， 也可以理解为观测次数。 A ( f ) = [ a ( f 1 ) , … , a ( f K ) ] ∈ C M × K \boldsymbol{A}(\boldsymbol{f})=\left[\boldsymbol{a}\left(f_{1}\right), \ldots, a\left(f_{K}\right)\right] \in \mathbb{C}^{M \times K} A(f)=[a(f1​),…,a(fK​)]∈CM×K， 其每一列对应第 k k k 个源 (source) 的 DOA 对应的天线响应矢量， 其中 a ( f ) = [ 1 , e i 2 π f , … , e i 2 π ( M − 1 ) f ] T \boldsymbol{a}(f)=\left[1, e^{i 2 \pi f}, \ldots, e^{i 2 \pi(M-1) f}\right]^{T} a(f)=[1,ei2πf,…,ei2π(M−1)f]T, 这里 f = 1 2 cos ⁡ θ f=\frac{1}{2} \cos \theta f=21​cosθ. E E E 是噪声, S ∈ C K × L S\in\mathbb{C}^{K\times L} S∈CK×L代表了这 K K K 个源在 L L L 个时隙的发射信号。

Toeplitz 矩阵的范德蒙德分解

在介绍原子范数之前，首先介绍一个非常有用的数学工具： 范德蒙德分解。 具体如下：

对于任意秩 r ≤ N r\le N r≤N 的半正定的Toeplitz矩阵 T ( u ) ∈ C N × N T(u)\in\mathbb{C}^{N\times N} T(u)∈CN×N， 有如下的 r r r-原子范德蒙德分解： T = ∑ k = 1 r p k a ( f k ) a H ( f k ) = A ( f ) diag ⁡ ( p ) A H ( f ) , T=\sum_{k=1}^{r} p_{k} a\left(f_{k}\right) a^{H}\left(f_{k}\right)=A(f) \operatorname{diag}(p) A^{H}(f), T=k=1∑r​pk​a(fk​)aH(fk​)=A(f)diag(p)AH(f), 当 r < N r0\right\} \\ &=\inf _{f_{k}, s_{k}}\left\{\mathcal{K}: z=\sum_{k=1}^{\mathcal{K}} a\left(f_{k}\right) s_{k}, f_{k} \in \mathbb{T}\right\} \end{aligned} ∥z∥A,0​​=ck​,fk​,ϕk​inf​{K:z=k=1∑K​a(fk​,ϕk​)ck​,fk​∈T,∣ϕk​∣=1,ck​>0}=fk​,sk​inf​{K:z=k=1∑K​a(fk​)sk​,fk​∈T}​ 因为我们的目的就是为了恢复出 A ( f ) A(f) A(f)， 而 z z z可以写成无数种 A \mathcal{A} A 中原子线性组合的形式。 但只有对应所用原子数最少即对应最小 ℓ 0 \ell_0 ℓ0​-原子范数 时， 此时组成 z z z 的原子才恰好对应待恢复的 A ( f ) A(f) A(f)。

因此， DOA估计旨在恢复 A ( f ) A(f) A(f)， 而这等价于最小化 z z z 的 ℓ 0 \ell_0 ℓ0​-原子范数， 写作 ∥ z ∥ A , 0 \|z\|_{\mathcal{A}, 0} ∥z∥A,0​.

ℓ 0 \ell_0 ℓ0​-原子范数 与 范德蒙德分解

然而 如何对于 ∥ z ∥ A , 0 \|z\|_{\mathcal{A}, 0} ∥z∥A,0​ 进行最小化，可以说是完全摸不着头脑。 这似乎比 ℓ 0 \ell_0 ℓ0​ 范数最小化更为抽象。 此时就是见证数学魅力的时刻。 我们考虑如下式子： [ x z H z T ( u ) ] ≥ 0 \left[\begin{array}{cc} x & z^{H} \\ z & T(u) \end{array}\right] \geq 0 [xz​zHT(u)​]≥0 T ( u ) T(u) T(u) 的定义一如之前， 是一个由 u u u 得到的Teoplitz 矩阵。 x x x 则是一个待优化的变量。 这个约束隐含了如下的结论：

• T ( u ) ≥ 0 T(u)\ge 0 T(u)≥0， 否则无法保证对于任何向量 y y y， 都有 y H [ y x z H z T ( u ) ] y ≥ 0 y^H\left[\begin{array}{cc}y x & z^{H} \\ z & T(u) \end{array}\right]y \ge 0 yH[yxz​zHT(u)​]y≥0。
• z z z 一定位于 T ( u ) T(u) T(u) 的列空间中。 这个证明也在后面的证明章节中给出了。

由于 T ( u ) ≥ 0 T(u)\ge 0 T(u)≥0， 因此 T ( u ) T(u) T(u) 是一个半正定矩阵， 即存在 范德蒙德分解 T = ∑ k = 1 r p k a ( f k ) a H ( f k ) = A ( f ) diag ⁡ ( p ) A H ( f ) , T=\sum_{k=1}^{r} p_{k} a\left(f_{k}\right) a^{H}\left(f_{k}\right)=A(f) \operatorname{diag}(p) A^{H}(f), T=k=1∑r​pk​a(fk​)aH(fk​)=A(f)diag(p)AH(f), 其中 r = r a n k ( T ( u ) ) r=rank(T(u)) r=rank(T(u))。 而由于 z z z 一定位于 T ( u ) T(u) T(u) 的列空间中， 那么 z z z 必能写为 a ( f k ) a\left(f_{k}\right) a(fk​) 的线性组合！ 这一点至关重要。 因为这引出了如下的结论：

最小化 ℓ 0 \ell_0 ℓ0​-原子范数等价于求解如下问题: min ⁡ x , u rank ⁡ ( T ( u ) ) ,  subject to  [ x z H z T ( u ) ] ≥ 0. \min _{x, u} \operatorname{rank}(\boldsymbol{T}(\boldsymbol{u})), \text { subject to }\left[\begin{array}{cc} x & z^{H} \\ z & T(u) \end{array}\right] \geq 0. x,umin​rank(T(u)), subject to [xz​zHT(u)​]≥0.

由于 z z z 是 T ( u ) T(u) T(u) 范德蒙德分解所得的 r r r个原子的线性组合。 当我们找到秩最小的 r r r 时，也就找到了组成 z z z 所需的最少原子数。 也就对应 z z z 的 ℓ 0 \ell_0 ℓ0​-原子范数最小化。 而对于这个转化后的问题， 如果 u u u 被解出， 那么 T ( u ) T(u) T(u) 也能得到， 那么对 T ( u ) T(u) T(u) 进行范德蒙德分解， 也就获得了 A ( f ) A(f) A(f)。 然而美中不足的是， 这个目标函数并非凸函数， 也无法轻易求解。

原子范数

将 ℓ 0 \ell_0 ℓ0​-原子范数进行凸松弛， 得到的就是原子范数。 其定义如下： ∥ z ∥ A = inf ⁡ f k , s k { ∑ k ∣ s k ∣ : z = ∑ k a ( f k ) s k , f k ∈ T } . \begin{aligned} \|z\|_{\mathcal{A}} =\inf _{f_{k}, s_{k}}\left\{\sum_{k}\left|s_{k}\right|: z=\sum_{k} a\left(f_{k}\right) s_{k}, f_{k} \in \mathbb{T}\right\} . \end{aligned} ∥z∥A​=fk​,sk​inf​{k∑​∣sk​∣:z=k∑​a(fk​)sk​,fk​∈T}.​ 与 ℓ 0 \ell_0 ℓ0​-原子范数 的定义进行比较， 发现这和将传统的 ℓ 0 \ell_0 ℓ0​-范数 放缩为 ℓ 1 \ell_1 ℓ1​-范数 如出一辙。 然而， 如何最小化 ∥ z ∥ A \|z\|_{\mathcal{A}} ∥z∥A​ 看上去也非常困难。 此时， 再度利用 范德蒙德分解， 我们有如下精彩的结论：

最小化原子范数等价于求解如下问题: min ⁡ x , u 1 2 x + 1 2 u 1 ,  subject to  [ x z H z T ( u ) ] ≥ 0. \min _{x, u} \frac{1}{2} x+\frac{1}{2} u_{1}, \text { subject to }\left[\begin{array}{cc} x & z^{H} \\ z & T(u) \end{array}\right] \geq 0. x,umin​21​x+21​u1​, subject to [xz​zHT(u)​]≥0.

• 注意到，这是一个凸问题。 首先目标函数显然是变量的仿射函数， 因此为凸（既凸且凹）。 限制条件也可以写为 变量的仿射函数形式。 因此也满足凸问题的限制条件（ f ( x ) ≤ 0 f(x)\le 0 f(x)≤0, f ( x ) f(x) f(x)为凸函数）。 （ X ≥ 0 X\ge 0 X≥0 可以等价为 y H X y ≥ 0 , ∀ y y^HXy\ge 0, \forall y yHXy≥0,∀y， 而对于每个 y y y， 都是关于 X X X 的仿射变换。）
• T ( u ) T(u) T(u) 的对角元素都是 u 1 u_1 u1​， 那么事实上 u 1 u_1 u1​ 就是 t r ( T ( u ) ) \mathrm{tr}(T(u)) tr(T(u))! 而后者又被称为核函数， 也是 r a n k ( T ( u ) ) rank(T(u)) rank(T(u))的经典凸松弛。 这从另一个角度解释了 原子范数最小化 是 ℓ 0 \ell_0 ℓ0​原子范数最小化的凸松弛。

至此， 压缩感知问题被转化为了一个可以由CVX进行直接求解的凸问题！ 还剩的最后一块拼图：即为何原子范数可以等效为这个凸问题， 仍照例，放在下面的证明章节中。

多维原子范数

将原子范数拓展到多维是十分必要的， 因为通信中DOA估计大多是多次观测。 然而其结论大体相似。 此时，变量变为二维矩阵 Z Z Z， 而其 ℓ 0 \ell_0 ℓ0​-原子范数被定义为： ∥ Z ∥ A , 0 = inf ⁡ c k , f k , ϕ k { K : Z = ∑ k = 1 K a ( f k , ϕ k ) c k , f k ∈ T , ∥ ϕ k ∥ 2 = 1 , c k > 0 } = inf ⁡ f k , s k { K : Z = ∑ k = 1 K a ( f k ) s k , f k ∈ T } \begin{aligned} \|Z\|_{\mathcal{A}, 0} &=\inf _{c_{k}, f_{k}, \phi_{k}}\left\{\mathcal{K}: Z=\sum_{k=1}^{\mathcal{K}} a\left(f_{k}, \phi_{k}\right) c_{k}, f_{k} \in \mathbb{T},\left\|\phi_{k}\right\|_{2}=1, c_{k}>0\right\} \\ &=\inf _{f_{k}, s_{k}}\left\{\mathcal{K}: Z=\sum_{k=1}^{\mathcal{K}} a\left(f_{k}\right) s_{k}, f_{k} \in \mathbb{T}\right\} \end{aligned} ∥Z∥A,0​​=ck​,fk​,ϕk​inf​{K:Z=k=1∑K​a(fk​,ϕk​)ck​,fk​∈T,∥ϕk​∥2​=1,ck​>0}=fk​,sk​inf​{K:Z=k=1∑K​a(fk​)sk​,fk​∈T}​ 其中， a ( f k , ϕ k ) = a ( f k ) ϕ k : f k ∈ T , ϕ k ∈ C 1 × L , ∥ ϕ k ∥ 2 = 1 a\left(f_{k}, \phi_{k}\right)=a\left(f_{k}\right) \phi_{k}: f_{k} \in \mathbb{T}, \phi_{k} \in \mathbb{C}^{1 \times L},\left\|\phi_{k}\right\|_{2}=1 a(fk​,ϕk​)=a(fk​)ϕk​:fk​∈T,ϕk​∈C1×L,∥ϕk​∥2​=1 注意到， 这和向量 z z z 的 原子范数的最大区别在于标量 ϕ k \phi_k ϕk​ ( s k s_k sk​)变为了行向量。 类似的， 对其的凸松弛的原子范数，定义为： ∥ Z ∥ A = inf ⁡ { t > 0 : Z ∈ tconv ⁡ ( A ) } = inf ⁡ c k , f k , ϕ k { ∑ k c k : Z = ∑ k a ( f k , ϕ k ) c k , f k ∈ T , ∥ ϕ k ∥ 2 = 1 , c k > 0 } = inf ⁡ f k , s k { ∑ k ∥ s k ∥ 2 : Z = ∑ k a ( f k ) s k , f k ∈ T } \begin{aligned} \|Z\|_{\mathcal{A}} &=\inf \{t>0: Z \in \operatorname{tconv}(\mathcal{A})\} \\ &=\inf _{c_{k}, f_{k}, \phi_{k}}\left\{\sum_{k} c_{k}: Z=\sum_{k} a\left(f_{k}, \phi_{k}\right) c_{k}, f_{k} \in \mathbb{T},\left\|\phi_{k}\right\|_{2}=1, c_{k}>0\right\} \\ &=\inf _{f_{k}, s_{k}}\left\{\sum_{k}\left\|s_{k}\right\|_{2}: Z=\sum_{k} a\left(f_{k}\right) s_{k}, f_{k} \in \mathbb{T}\right\} \end{aligned} ∥Z∥A​​=inf{t>0:Z∈tconv(A)}=ck​,fk​,ϕk​inf​{k∑​ck​:Z=k∑​a(fk​,ϕk​)ck​,fk​∈T,∥ϕk​∥2​=1,ck​>0}=fk​,sk​inf​{k∑​∥sk​∥2​:Z=k∑​a(fk​)sk​,fk​∈T}​ 而对其的最小化， 仍可以等价为如下SDP问题： min ⁡ X , u 1 2 N [ Tr ⁡ ( X ) + Tr ⁡ ( T ( u ) ) ] ,  subject to  [ X Z H Z T ( u ) ] ≥ 0 \min _{X, u} \frac{1}{2 \sqrt{N}}[\operatorname{Tr}(\boldsymbol{X})+\operatorname{Tr}(\boldsymbol{T}(\boldsymbol{u}))], \text { subject to }\left[\begin{array}{cc} X & Z^{H} \\ Z & T(u) \end{array}\right] \geq 0 X,umin​2N ​1​[Tr(X)+Tr(T(u))], subject to [XZ​ZHT(u)​]≥0 照例， 其证明放在后续证明章节。

证明 范德蒙德分解的证明

由于 T ⪰ 0 T\succeq0 T⪰0 (半正定的要求)， 因此有 T = V V H T=VV^H T=VVH (可以通过特征分解得到)， 其中 V ∈ C N × r V\in\mathbb{C}^{N\times r} V∈CN×r。 然后，根据Toeplitz矩阵的结构。 如果我们用 V − N V_{-N} V−N​ 和 V − 1 V_{-1} V−1​ 分别代表 V V V 矩阵去掉最后一行和第一行的结果， 根据简单的块矩阵乘法， 我们可以发现， V − N V − N H = V − 1 V − 1 H \boldsymbol{V}_{-N} \boldsymbol{V}_{-N}^{H}=\boldsymbol{V}_{-1} \boldsymbol{V}_{-1}^{H} V−N​V−NH​=V−1​V−1H​。 那么，当 N − 1 ≥ r N-1\ge r N−1≥r 时， 必存在正交矩阵 Q Q Q， 使得 V − 1 = V − N Q \boldsymbol{V}_{-1}=\boldsymbol{V}_{-N} \boldsymbol{Q} V−1​=V−N​Q。 这一结论的证明可见下节， 为不影响思路的进展我们先继续。 令 V j V_j Vj​ 代表 V V V 的第 j j j 行， 可知： V j = V 1 Q j − 1 , j = 2 , … , N \boldsymbol{V}_{j}=\boldsymbol{V}_{1} Q^{j-1}, j=2, \ldots, N Vj​=V1​Qj−1,j=2,…,N 因此有： u j = V 1 Q 1 − j V 1 H , j = 1 , … , N (1) u_{j}=\boldsymbol{V}_{1} Q^{1-j} \boldsymbol{V}_{1}^{H}, \quad j=1, \ldots, N \tag{1} uj​=V1​Q1−jV1H​,j=1,…,N(1) 其中 u j u_j uj​ 是 u u u 的 第 j j j 个 元素。 对 Q Q Q 进行特征分解， 有： Q = Q ~ diag ⁡ ( z 1 , … , z r ) Q ~ H Q=\widetilde{Q} \operatorname{diag}\left(z_{1}, \ldots, z_{r}\right) \widetilde{Q}^{H} Q=Q ​diag(z1​,…,zr​)Q ​H 注意到， 由于 Q Q Q 是正交矩阵， 其特征值 z k z_k zk​ 必满足 z k ∗ z k = 1 z_k^*z_k=1 zk∗​zk​=1。 可以显然地由 Q Q H = I QQ^H=I QQH=I得证。 因此， 我们可以把 z k z_k zk​ 写为 z k = e i 2 π f k z_{k}=e^{i 2 \pi f_{k}} zk​=ei2πfk​， 因为它必定是一个恒模的复数， 所以一定存在这样的 f k f_k fk​。 再注意到： Q N = Q ~ diag ⁡ ( z 1 , … , z r ) N Q ~ H Q^N=\widetilde{Q} \operatorname{diag}\left(z_{1}, \ldots, z_{r}\right)^N \widetilde{Q}^{H} QN=Q ​diag(z1​,…,zr​)NQ ​H 对于任意正整数 N N N， 因为 Q ~ \widetilde{Q} Q ​ 也是正交阵。 我们令 p k = ∣ V 1 Q ~ : k ∣ 2 p_{k}=\left|\boldsymbol{V}_{1} \widetilde{\boldsymbol{Q}}_{: k}\right|^{2} pk​=∣∣∣​V1​Q ​:k​∣∣∣​2， 代入 (1) 中， 得到: u j = ∑ k = 1 r p k e − i 2 π ( j − 1 ) f k u_{j}=\sum_{k=1}^{r} p_{k} e^{-i 2 \pi(j-1) f_{k}} uj​=k=1∑r​pk​e−i2π(j−1)fk​ 而这， 就对应了范德蒙德分解。 证毕。 至此，还可以发现， f k f_k fk​ 必须是不同的， 否则 A ( f ) A(f) A(f) 中将有相同的列， 那么也无法满足 r a n k ( T ) = r rank(T)=r rank(T)=r的条件了。 我们现已证明了 r ≤ N − 1 r\le N-1 r≤N−1 场景下的范德蒙德分解的可行性。 我们再证明其分解的唯一性。 通过反证法， 若存在 另一组分解 T = A ( f ′ ) P ′ A H ( f ′ ) T=A\left(f^{\prime}\right) P^{\prime} A^{H}\left(f^{\prime}\right) T=A(f′)P′AH(f′)， 即： A ( f ′ ) P ′ A H ( f ′ ) = A ( f ) P A H ( f ) \boldsymbol{A}\left(\boldsymbol{f}^{\prime}\right) \boldsymbol{P}^{\prime} \boldsymbol{A}^{H}\left(\boldsymbol{f}^{\prime}\right)=\boldsymbol{A}(\boldsymbol{f}) \boldsymbol{P A}^{H}(\boldsymbol{f}) A(f′)P′AH(f′)=A(f)PAH(f) 类似地可证明， 存在 A ( f ′ ) P ′ 1 2 = A ( f ) P 1 2 Q ′ A\left(f^{\prime}\right) P^{\prime \frac{1}{2}}=A(f) P^{\frac{1}{2}} Q^{\prime} A(f′)P′21​=A(f)P21​Q′， 其中 Q ′ Q^\prime Q′ 为正交矩阵。 因此 A ( f ′ ) = A ( f ) P 1 2 Q ′ P ′ − 1 2 \boldsymbol{A}\left(\boldsymbol{f}^{\prime}\right)=\boldsymbol{A}(\boldsymbol{f}) \boldsymbol{P}^{\frac{1}{2}} Q^{\prime} \boldsymbol{P}^{\prime-\frac{1}{2}} A(f′)=A(f)P21​Q′P′−21​ 也就是说， a ( f j ′ ) a\left(f_{j}^{\prime}\right) a(fj′​) 是 a ( f j ) a\left(f_{j}\right) a(fj​)的线性组合。 此时，注意到一个性质： 任意 N N N个 a ( f k ) a\left(f_{k}\right) a(fk​)之间线性独立。 也就是说， 因为 r ≤ N − 1 r\le N-1 r≤N−1, 因此 a ( f j ′ ) a(f_j^\prime) a(fj′​) 可以和 r r r 个 a ( f j ) a(f_j) a(fj​) 组成不超过 N N N个 a a a，那么他们之间必定相互线性独立， 即前者不可能写为后者的线性组合。 因此矛盾。

最后，对于 r = N r=N r=N的情况下， 范德蒙德分解成立但不唯一。 证明思路类似，这里略去。

正交矩阵结论的证明

上一节的证明中， 用有这个结论: X X H = Y Y H \boldsymbol{X} \boldsymbol{X}^{H}=\boldsymbol{Y} \boldsymbol{Y}^{H} XXH=YYH 其中 X , Y ∈ C m , n X,Y\in\mathbb{C}^{m,n} X,Y∈Cm,n, m ≥ n m\ge n m≥n。 那么， 必存在正交矩阵 Q Q Q， 使得 X = Y Q \boldsymbol{X}=\boldsymbol{Y} \boldsymbol{Q} X=YQ。

首先我们有： X = Y Y H X ( X H X ) − 1 X = YY^HX(X^HX)^{-1} X=YYHX(XHX)−1 记 Q = Y H X ( X H X ) − 1 Q=Y^HX(X^HX)^{-1} Q=YHX(XHX)−1， 即 X = Y Q X=YQ X=YQ。 则有： Y Q Q H Y H = Y Y H ⇒ Y Q Q H = Y ⇒ Q Q H = I YQQ^HY^H=YY^H\Rightarrow YQQ^H=Y\Rightarrow QQ^H=I YQQHYH=YYH⇒YQQH=Y⇒QQH=I 因此 Q Q Q 为正交矩阵.

z z z存在于列空间的证明

当 [ x z H z T ( u ) ] ≥ 0 \left[\begin{array}{cc} x & z^{H} \\ z & T(u) \end{array}\right] \geq 0 [xz​zHT(u)​]≥0成立时， z z z 位于 T ( u ) T(u) T(u)的列空间中。

当 T ( u ) T(u) T(u) 满秩时， 直接成立。 当 T ( u ) T(u) T(u) 不满秩时，

注意到： [ x z H z T ( u ) ] ≥ 0    ⟺    [ t y ] H [ x z H z T ( u ) ] [ t y ] ≥ 0 , ∀ t , y ⇒ t H x t + y H z t + t H z H y + y H T ( u ) y ≥ 0 \left[\begin{array}{cc} x & z^{H} \\ z & T(u) \end{array}\right] \geq 0\iff [t \quad y]^H\left[\begin{array}{cc} x & z^{H} \\ z & T(u) \end{array}\right]\left[\begin{array}{l} t \\ y \end{array}\right]\ge 0,\quad\forall t,y\\ \Rightarrow t^Hxt + y^Hzt+t^Hz^Hy+y^HT(u)y\ge 0 [xz​zHT(u)​]≥0⟺[ty]H[xz​zHT(u)​][ty​]≥0,∀t,y⇒tHxt+yHzt+tHzHy+yHT(u)y≥0

此时， 取 y y y 位于 T ( u ) T(u) T(u) 的零空间中。 则上式进一步变为： t ∗ x t + y H z t + t ∗ z H y ≥ 0 t^*xt + y^Hzt+t^*z^Hy\ge 0 t∗xt+yHzt+t∗zHy≥0 若 z z z不位于 T ( u ) T(u) T(u)的列空间中， 即 a = y H z ≠ 0 a=y^Hz\neq 0 a=yHz​=0, 则： t ∗ x t + a t + t H a ∗ ≥ 0 t^*xt + at+t^Ha^*\ge 0 t∗xt+at+tHa∗≥0 取 t = − a ∗ x t=-\frac{a^*}{x} t=−xa∗​，有： a a ∗ x ∗ − a a ∗ x ∗ − a a ∗ x ∗ ≥ 0 \frac{aa^*}{x^*} - \frac{aa^*}{x^*} -\frac{aa^*}{x^*} \ge0 x∗aa∗​−x∗aa∗​−x∗aa∗​≥0 由于 x x x必为非负实数（取 t = 1 , y = 0 t=1, y=0 t=1,y=0）， 所以上式显然不成立， 矛盾。 得证。

原子范数最小化的等价性证明

记 等价凸问题的目标函数 F = 1 2 x + 1 2 u 1 F=\frac{1}{2} x+\frac{1}{2} u_{1} F=21​x+21​u1​, 先证明： F ≤ ∥ z ∥ A F \leq\|z\|_{\mathcal{A}} F≤∥z∥A​。 取 z = ∑ k c k a ( f k , ϕ k ) = ∑ k a ( f k ) s k z=\sum_{k} c_{k} a\left(f_{k}, \phi_{k}\right)=\sum_{k} a\left(f_{k}\right) s_{k} z=∑k​ck​a(fk​,ϕk​)=∑k​a(fk​)sk​， 令 T ( u ) = ∑ k c k a ( f k ) a H ( f k ) \boldsymbol{T}(\boldsymbol{u})=\sum_{k} c_{k} \boldsymbol{a}\left(f_{k}\right) \boldsymbol{a}^{H}\left(f_{k}\right) T(u)=∑k​ck​a(fk​)aH(fk​) 和 x = ∑ k c k x=\sum_{k} c_{k} x=∑k​ck​，有： [ x z H z T ] = ∑ k c k [ ϕ k ∗ a ( f k ) ] [ ϕ k ∗ a ( f k ) ] H ≥ 0 \left[\begin{array}{cc} x & z^{H} \\ z & T \end{array}\right]=\sum_{k} c_{k}\left[\begin{array}{c} \phi_{k}^{*} \\ a\left(f_{k}\right) \end{array}\right]\left[\begin{array}{c} \phi_{k}^{*} \\ a\left(f_{k}\right) \end{array}\right]^{H} \geq 0 [xz​zHT​]=k∑​ck​[ϕk∗​a(fk​)​][ϕk∗​a(fk​)​]H≥0 因此 T T T 和 x x x 是一组可行解。 那么其必然不小于最优解。而这组可行解对应的目标函数为： 1 2 x + 1 2 u 1 = ∑ k c k \frac{1}{2} x+\frac{1}{2} u_{1}=\sum_{k} c_{k} 21​x+21​u1​=k∑​ck​ 因此， F ⋆ ≤ ∥ z ∥ A F^\star \leq\|z\|_{\mathcal{A}} F⋆≤∥z∥A​。 再证明 F ⋆ ≥ ∥ z ∥ A F^\star \geq\|z\|_{\mathcal{A}} F⋆≥∥z∥A​。 设凸问题的最优解为 ( x ^ , u ^ ) (\widehat{x}, \widehat{u}) (x ,u )， 对 T ( u ^ ) T(\widehat{u}) T(u ) 进行范德蒙德分解， 得到参数 ( r ^ , p ^ k , f ^ k ) \left(\widehat{r}, \widehat{p}_{k}, \widehat{f}_{k}\right) (r ,p ​k​,f ​k​)。 根据之前的分析， z z z 必然在 T ( u ^ ) T(\widehat{u}) T(u ) 的列空间中， 即： z = ∑ k = 1 r ^ c ^ k a ( f ^ k , ϕ ^ k ) = ∑ k = 1 r ^ a ( f ^ k ) s ^ k z=\sum_{k=1}^{\widehat{r}} \widehat{c}_{k} a\left(\widehat{f}_{k}, \widehat{\phi}_{k}\right)=\sum_{k=1}^{\widehat{r}} a\left(\widehat{f}_{k}\right) \widehat{s}_{k} z=k=1∑r ​c k​a(f ​k​,ϕ ​k​)=k=1∑r ​a(f ​k​)s k​ 进一步地， 根据Schur补条件 https://zhuyulab.blog.csdn.net/article/details/121942523， [ x z H z T ( u ) ] ≥ 0 \left[\begin{array}{cc} x & z^{H} \\ z & T(u) \end{array}\right] \geq 0 [xz​zHT(u)​]≥0 等价于： x ^ ≥ z H [ T ( u ^ ) ] † z = ∑ k = 1 r ^ c ^ k 2 p ^ k \widehat{x} \geq z^{H}[\boldsymbol{T}(\widehat{\boldsymbol{u}})]^{\dagger} \boldsymbol{z}=\sum_{k=1}^{\widehat{r}} \frac{\widehat{c}_{k}^{2}}{\widehat{p}_{k}} x ≥zH[T(u )]†z=k=1∑r ​p ​k​c k2​​ 而 u ^ 1 = ∑ k = 1 r ^ p ^ k \widehat{u}_{1}=\sum_{k=1}^{\widehat{r}} \widehat{p}_{k} u 1​=∑k=1r ​p ​k​， 因此 F = 1 2 x ^ + 1 2 u ^ 1 ≥ 1 2 ∑ k c ^ k 2 p ^ k + 1 2 ∑ k p ^ k ≥ ∑ k c ^ k ≥ ∥ z ∥ A . \begin{aligned} F &=\frac{1}{2} \widehat{x}+\frac{1}{2} \widehat{u}_{1} \\ & \geq \frac{1}{2} \sum_{k} \frac{\widehat{c}_{k}^{2}}{\widehat{p}_{k}}+\frac{1}{2} \sum_{k} \widehat{p}_{k} \\ & \geq \sum_{k} \widehat{c}_{k} \\ & \geq\|z\|_{\mathcal{A}} . \end{aligned} F​=21​x +21​u 1​≥21​k∑​p ​k​c k2​​+21​k∑​p ​k​≥k∑​c k​≥∥z∥A​.​ 第一个不等号来自于Schur补条件。 第二个不等号来自于 1 x + x \frac{1}{x}+x x1​+x的最大化问题。第三个不等式来自于 ∥ z ∥ A \|z\|_{\mathcal{A}} ∥z∥A​的定义， 即所有线性分解中， ∑ k c k \sum_{k} {c}_{k} ∑k​ck​的最小值。 至此， 得证， F ⋆ = ∥ z ∥ A F^\star=\|z\|_{\mathcal{A}} F⋆=∥z∥A​.

多维原子范数最小化的等价性证明

记 等价凸问题的目标函数 F = 1 2 N [ Tr ⁡ ( X ) + Tr ⁡ ( T ( u ) ) ] F=\frac{1}{2 \sqrt{N}}[\operatorname{Tr}(\boldsymbol{X})+\operatorname{Tr}(\boldsymbol{T}(\boldsymbol{u}))] F=2N ​1​[Tr(X)+Tr(T(u))]。 取 z = ∑ k c k a ( f k , ϕ k ) = ∑ k a ( f k ) s k z=\sum_{k} c_{k} a\left(f_{k}, \phi_{k}\right)=\sum_{k} a\left(f_{k}\right) s_{k} z=∑k​ck​a(fk​,ϕk​)=∑k​a(fk​)sk​， 令 T ( u ) = 1 N ∑ k c k a ( f k ) a H ( f k ) \boldsymbol{T}(\boldsymbol{u})=\frac{1}{\sqrt{N}}\sum_{k} c_{k} \boldsymbol{a}\left(f_{k}\right) \boldsymbol{a}^{H}\left(f_{k}\right) T(u)=N ​1​∑k​ck​a(fk​)aH(fk​) 和 X = N ∑ k c k ϕ k H ϕ k X=\sqrt{N}\sum_{k} c_{k}\phi_k^H\phi_k X=N ​∑k​ck​ϕkH​ϕk​，有： [ x z H z T ] = ∑ k c k [ N 1 4 ϕ k H N − 1 4 a ( f k ) ] [ N 1 4 ϕ k H N − 1 4 a ( f k ) ] H ≥ 0 \left[\begin{array}{cc} x & z^{H} \\ z & T \end{array}\right]=\sum_{k} c_{k}\left[\begin{array}{c} N^{\frac{1}{4}}\phi_{k}^{H} \\ N^{-\frac{1}{4}}a\left(f_{k}\right) \end{array}\right]\left[\begin{array}{c} N^{\frac{1}{4}}\phi_{k}^{H} \\ N^{-\frac{1}{4}}a\left(f_{k}\right) \end{array}\right]^{H} \geq 0 [xz​zHT​]=k∑​ck​[N41​ϕkH​N−41​a(fk​)​][N41​ϕkH​N−41​a(fk​)​]H≥0 因此 T T T 和 X X X 是一组可行解。 那么其必然不小于最优解。根据定义， 有 ϕ k ϕ k H = 1 \phi_k\phi_k^H=1 ϕk​ϕkH​=1， 那么， 这组可行解对应的目标函数为： F = 1 2 N [ Tr ⁡ ( X ) + Tr ⁡ ( T ( u ) ) ] = ∑ k c k = ∥ z ∥ A F=\frac{1}{2 \sqrt{N}}[\operatorname{Tr}(\boldsymbol{X})+\operatorname{Tr}(\boldsymbol{T}(\boldsymbol{u}))]=\sum_k c_k=\|z\|_{\mathcal{A}} F=2N ​1​[Tr(X)+Tr(T(u))]=k∑​ck​=∥z∥A​ 因此， F ⋆ ≤ ∥ z ∥ A F^\star \leq\|z\|_{\mathcal{A}} F⋆≤∥z∥A​。 再证明 F ⋆ ≥ ∥ z ∥ A F^\star \geq\|z\|_{\mathcal{A}} F⋆≥∥z∥A​。 设凸问题的最优解为 ( X ^ , T ^ ) (\widehat{X}, \widehat{T}) (X ,T )， 对 T ^ \widehat{T} T 进行范德蒙德分解， 得到参数 ( r ^ , p ^ k , f ^ k ) \left(\widehat{r}, \widehat{p}_{k}, \widehat{f}_{k}\right) (r ,p ​k​,f ​k​)。 根据之前的分析， Z Z Z 必然在 T ^ \widehat{T} T 的列空间中， 即： Z = ∑ k = 1 r ^ c ^ k a ( f ^ k , ϕ ^ k ) = ∑ k = 1 r ^ a ( f ^ k ) s ^ k Z=\sum_{k=1}^{\widehat{r}} \widehat{c}_{k} a\left(\widehat{f}_{k}, \widehat{\phi}_{k}\right)=\sum_{k=1}^{\widehat{r}} a\left(\widehat{f}_{k}\right) \widehat{s}_{k} Z=k=1∑r ​c k​a(f ​k​,ϕ ​k​)=k=1∑r ​a(f ​k​)s k​ 进一步地， 根据Schur补条件 https://zhuyulab.blog.csdn.net/article/details/121942523， [ X Z H Z T ] ≥ 0 \left[\begin{array}{cc} X & Z^{H} \\ Z & T \end{array}\right] \geq 0 [XZ​ZHT​]≥0 等价于： X ^ − Z H T ^ † Z ≥ 0 \widehat{X}- Z^{H}\widehat{T}^{\dagger} \boldsymbol{Z}\ge 0\\ X −ZHT †Z≥0 而根据半正定矩阵的定义， 其特征值均非负。 因此一定有： t r ( X ^ − Z H T ^ † Z ) ≥ 0 ⇒ t r ( X ^ ) ≥ t r ( Z H T ^ † Z ) = ∑ k = 1 r ^ c ^ k 2 p ^ k \mathrm{tr}(\widehat{X}- Z^{H}\widehat{T}^{\dagger} \boldsymbol{Z}) \ge 0\Rightarrow\mathrm{tr}(\widehat{X})\ge \mathrm{tr}(Z^{H}\widehat{T}^{\dagger} \boldsymbol{Z})=\sum_{k=1}^{\widehat{r}} \frac{\widehat{c}_{k}^{2}}{\widehat{p}_{k}} tr(X −ZHT †Z)≥0⇒tr(X )≥tr(ZHT †Z)=k=1∑r ​p ​k​c k2​​ 而 t r ( T ^ ) = N ∑ k = 1 r ^ p ^ k \mathrm{tr}(\widehat{T})=N\sum_{k=1}^{\widehat{r}} \widehat{p}_{k} tr(T )=N∑k=1r ​p ​k​， 因此 F = 1 2 N [ Tr ⁡ ( X ) + Tr ⁡ ( T ( u ) ) ] ≥ 1 2 N [ ∑ k c ^ k 2 p ^ k + N ∑ k p ^ k ] ≥ ∑ k c ^ k ≥ ∥ Z ∥ A . \begin{aligned} F &=\frac{1}{2 \sqrt{N}}[\operatorname{Tr}(\boldsymbol{X})+\operatorname{Tr}(\boldsymbol{T}(\boldsymbol{u}))] \\ & \geq \frac{1}{2 \sqrt{N}}[\sum_{k} \frac{\widehat{c}_{k}^{2}}{\widehat{p}_{k}}+N \sum_{k} \widehat{p}_{k}] \\ & \geq \sum_{k} \widehat{c}_{k} \\ & \geq\|Z\|_{\mathcal{A}} . \end{aligned} F​=2N ​1​[Tr(X)+Tr(T(u))]≥2N ​1​[k∑​p ​k​c k2​​+Nk∑​p ​k​]≥k∑​c k​≥∥Z∥A​.​ 第一个不等号来自于Schur补条件。 第二个不等号来自于 1 x + x \frac{1}{x}+x x1​+x的最大化问题。第三个不等式来自于 ∥ z ∥ A \|z\|_{\mathcal{A}} ∥z∥A​的定义， 即所有线性分解中， ∑ k c k \sum_{k} {c}_{k} ∑k​ck​的最小值。 至此， 得证， F ⋆ = ∥ Z ∥ A F^\star=\|Z\|_{\mathcal{A}} F⋆=∥Z∥A​.

结语

本文旨在先介绍原子范数的中心思想， 对其的具体使用和相关代码， 留待后续的博客进行介绍。