原子范数

区别于$l_1$范数只能用来处理稀疏向量和核范数只能处理稀疏矩阵，原子范数通过选取不同的基向量，可以有处理不同的问题。

一、定义

1.1 原子范数

$$||x||_A = \inf \{ t > 0|x \in tconv(A)\}$$

简单的说，这是一个由A中的向量构成的一个凸包$conv(A)$通过整体的尺度变换使得$x$恰好落入$tconv(A)$中，把最后的尺度变换$t$作为$||x||_A$的值。

1.2 对偶范数

$$||z||_A^* = \sup \limits_{||x||_A \le 1} \left\langle {x,z} \right\rangle$$

显然，

$$\left\langle {x,z} \right\rangle \le ||x||_A||z||_A^*$$

二、凸优化问题

2.1 优化问题

$$\min \limits_x {1 \over 2}||x - y||_2^2 + \tau ||x||{_A}$$

其中，$y=x^*+w,x^*$ 是真实值，$x$是估计值

2.2 对偶问题

原问题等价于

$$\min \limits_x {1 \over 2}||x - y||_2^2 + \tau ||u||_A,s.t. u=x$$

对应的Lagrange函数为

$$L(x,u,z)= {1 \over 2} ||x-y||_2^2 +\tau ||u||_A +z^T(u-x)$$

那么，Lagrange对偶函数为

$$g(z)=\inf \limits_x L(x,u,z)={1 \over 2} (||y||_2^2 - ||y-z||_2^2 ) + \inf \limits_x (\tau ||u||_A +z^Tu)$$

所以，对偶问题为

$$\max \limits_z {1 \over 2} (||y||_2^2 - ||y-z||_2^2 ), s.t. ||z||_A^* \le \tau$$

其中，

$$y = \hat x + \hat z,\left\langle {\hat x,\hat z} \right\rangle = \tau || \hat x ||_A$$

2.3 均方误差上限

$$E||\hat x - x^*||_2^2 \le \tau ||x^*||_A$$

三、线谱估计

给定原信号的奈奎斯特抽样结果为

$$x_m^*: = {x^*}({m \over {2W}}) = \sum \limits_{l = 1}^k {c_l^*{e^{i2\pi m f_l^*}}} ,m = 0, \ldots ,n - 1$$
其中，$f_l^={w_l^* \over 2W}$ 为数字频率。

$x_m^*$是下面这个集合中k个元素的线性组合。

$$A=\{e^{i2\pi \phi}[1,e^{2 \pi f},\ldots e^{2\pi (n-1)f}],f \in [0,1], \phi \in [0,1]\}$$

可以认为$A$是一个无穷字典。

记

$$a_{f,\phi}=e^{i2\pi \phi}[1,e^{2 \pi f},\ldots e^{2\pi (n-1)f}]$$

显然，

$$x=\sum \limits_{k}c_k a_{f_k,\phi_k}$$

另外，记

$$u=\sum \limits_{k}c_k a_{f_k,0}$$

那么，对偶范数可以写成

$$||v||_A^*=\sup \limits_{f,\phi} \left\langle {v,a_{f, \phi}}\right\rangle=\sup \limits_{f \in [0,1]}\sup \limits_{\phi \in [0,1]} e^{i2\pi \phi }\sum \limits_{l=0}^{n-1} v_l e^{-i 2 \pi l f} = \sup \limits_{|z| \le 1} \left|\sum \limits_{l=0}^{n-1} v_l z^l \right|$$

记

$$V(f)=\sum \limits_{l=0}^{n-1} v_l e^{-i 2 \pi l f}$$

所以，

$$||v||_A^* \le \tau \Leftrightarrow \left|V(f)\right|^2 \le \tau^2, \forall f \in [0,1]$$

而且，有定理保证，

$$\left|V(f)\right|^2 \le \tau^2 \Leftrightarrow \left\{ \matrix{ {T^*}(Q) = {\tau ^2}{e_1} \cr \left[ {\matrix{ Q & v \cr {{v^*}} & 1 \cr } } \right] \ge 0 \cr} \right .$$

进一步，根据原子范数定义及上述结论，有：
对于$x \in C^n$

$$\eqalign{ & ||x|{|_A} = \mathop {\min }\limits_{t,u} {1 \over 2}t + {1 \over {2n}}tr(T(u)) \cr & s.t.\left[ {\matrix{ T(u) & x \cr {x^*} & t \cr } } \right] \ge 0 \cr}$$

那么原优化问题等价于

$$\eqalign{ & \mathop {\min }\limits_{t,u,x} {1 \over 2}\left\| {x - y} \right\|_2^2 + {\tau \over 2}(t + {1 \over n}T(u)) \cr & s.t.\left[ {\matrix{ T(u) & x \cr {x^*} & t \cr } } \right]\underline \succ 0 \cr}$$

其中，$T(u) = \sum\limits_k {{c_k}} {a_{{f_k},0}}a_{{f_k},0}^* = \sum\limits_k {{c_k}} {a_{{f_k},{\phi _k}}}a_{{f_k},{\phi _k}}^*$

通过求解上述半正定问题，可以得到原优化问题的解。可以使用SeDuMi 或者 SDPT3 工具箱进行求解。

参考文献

• 1.Bhaskar B N, Tang G, Recht B. Atomic norm denoising with applications to line spectral estimation[J]. Signal Processing IEEE Transactions on, 2012, 61(23):261 - 268.
• 2.Tang G, Bhaskar B N, Shah P, et al. Compressed Sensing Off the Grid[J]. Information Theory IEEE Transactions on, 2013, 59(11):7465-7490.