LASSO问题
推导
问题定义：\(\underset{x}{\min}||y-X\beta||_2^2+\tau||\beta||_\mathcal{A}\
0、上述问题是典型的无约束问题，可以通过变量替换的思想进行处理。
2、可以观察到\(g(u\中关于\(\beta\和\(z\的元素项不存在耦合关系，因此可进步将\(g(u\问题拆解为独立的最小项\(g(\beta\和\(g(z\，其中\(g(\beta=\min_\beta~\lambda\Vert\beta\Vert_1-u^TX\beta\, \(g(z=\min_\beta~\frac{1}{2} \Vert y-z\Vert_2^2+u^Tz\
4、对\(g(z\求极值，可以得到\(-(y-z+u=0\，即\(z=y-u\。
\(g(z=\frac{1}{2}\Vert u\Vert^2_2+u^T(y-u=u^Ty-\frac{1}{2}\Vert u\Vert_2^2=-\frac{1}{2}[\Vert y\Vert_2^2+\Vert u\Vert_2^2-2u^Ty]+\frac{1}{2}\Vert y\Vert_2^2=-\frac{1}{2}\Vert y-u\Vert_2^2+\frac{1}{2} \Vert y\Vert_2^2\
\(\max_u -\frac{1}{2}\Vert y-u\Vert_2^2+\frac{1}{2} \Vert y\Vert_2^2 ~s.t.X^Tu\leq\lambda\
代码
原子范数对偶问题
推导
对偶函数可以写为\(g(x,u\在\(C\上的下确界，即\(g(\mathbf{c},\xi=\inf~L(x,\mathbf{c},\xi\
1、原问题的增广拉格朗日目标函数可以表示为：\(L(x,\mathbf{c},\xi=\|x\|_{\mathcal{A}}+\mathrm{Re}\left[\mathbf{c}^{H}\left(\mathbf{y}-\mathcal{F}_{M}x-\mathbf{n}\right\right]+\xi\left(\mathbf{n}^{H}\mathbf{n}-\epsilon^{2}\right\
2、下确界的求解是关于\(x\的最小化，因此对原拉格朗日增广函数的最小化可以转换为对\([\Vert x\Vert_A-\mathrm{Re}[\lambda^HF_Mx]]\求下确界。在求这项下确界时，需要对式中的噪声功率参数\(n\和对偶变量\(\xi\求偏导寻找极值点。
目的是为了使噪声功率最小化]，有\(\frac{\partial g(\mathbf{c},\xi}{\partial c}=-c+2\xi n=0\，可以得到最佳极值点\(n_o=\frac{c}{2\xi}\，此时对应的对偶函数为\(\begin{array}{c}g(\mathbf{c},\xi|_{\mathbf{n_\circ}}=\mathrm{Re}\left[\mathbf{c}^{H}\mathbf{y}\right]-\dfrac{\mathbf{c}^{H}\mathbf{c}}{2\xi}+\xi\left(\dfrac{\mathbf{c}^{H}\mathbf{c}}{4\xi^{2}}-\epsilon^{2}\right+\+\inf_{x}\left(\|x\|_{\mathcal{A}}-\mathrm{Re}\left[\mathbf{c}^{H}\mathcal{F}_{M}x\right]\right.\end{array}\
最后，基于最优极值点对偶函数可以表示为\(g(c|_{n_o,\xi_o}=\mathrm{Re}[c^Hy-\epsilon\Vert c\Vert_2+\inf_x(\Vert x\Vert_A-\mathrm{Re}[c^H\mathcal{F}_{M}]x]\。
当\(|\mathcal{F}_{M}^Hc|\leq1\时下确界项为0；当\(|x_i|\left[1-|\left(\mathcal{F}_M^H\mathbf{c}\right_i|\right]<0\时下确界可以达到\(-\infty\。
\(g(\mathbf{c}=\left\{\begin{array}{lcl}\operatorname{Re}\left[\mathbf{c}^H\mathbf{y}-\epsilon\Vert c\Vert_2\right],&\|\mathcal{F}_M^H\mathbf{c}\|_{\infty}\leq1\\ -\infty,&\quad\mathrm{otherwise.}\end{array}\right.\
4、为了进一步抽象\(g(\mathbf{c}\，我们可以作以下表示：
对于非负三角多项式，可以有Hermitian矩阵\(R(\omega=|H(\omega|^2=H(\omegaH(\omega^H=a(\omega^Hhh^Ha(\omega=\sum_{k=-(L-1}^{L-1}r_k e^{-j\omega k}\,其中\(r_k=\sum_{l=0}^{L-1-k}h_l h_{l+k}^*\，\(k\geq0\并且\(r_{-k}=r_k^*\，稀疏\(r_k\可以通过自相关矩阵\(Q_{L\times L}=hh^H\的第\(k\条对角线元素进行计算\(r_k=\sum_{i=1}^{L-k}Q_{i,i+k}\。
这意味着\(|H(\omega|^2\leq|B(\omega|^2,\forall\omega\in[-\pi,\pi]\,定义\(R_H(\omega=|H(\omega|^2\和\(R_B(\omega=|B(\omega|^2\，那么有\(R_H(\omega\leq R_B(\omega\，即\(Q_H \leq Q_B\，其中\(Q_H=hh^H\和\(Q_B=bb^H\为自相关向量\(\mathbf{h}=[h_{0},\cdots,h_{L-1}]^{T}\和\(\mathbf{b}=[b_{0},\cdots,b_{L-1}]^{T}\的自相关矩阵。
根据Schur补条件有\(Q_B-hh^H\geq0\，即\(\begin{bmatrix}\mathbf{Q}_B&\mathbf{h}_{L\times1}\\ \mathbf{h}_{1\times L}^{H}&1\end{bmatrix}\succeq0.\
\(\begin{bmatrix}\mathbf{Q}_{L\times L}&\mathbf{h}_{L\times1}\\ \mathbf{h}_{1\times L}&1\end{bmatrix}\succeq0,\\ \sum_{i=1}^{L-j}Q_{i,i+j}=\left\{\begin{array}{c}\gamma^2,&j=0\\ 0,&j=1,\cdots,L-1.\end{array}\right.\
有界三角多项式的结果可以用于\(\infty\范数，因为多项式的最大振幅设置上界意味着多项式对所有\(\omega\in[-\pi,\pi]\具有一致有界的振幅,即\(\begin{array}{l}\|H\|_{\infty}=\max\limits_{\omega\in[-\pi,\pi]}|H(\omega|\leq\gamma,\\ |H(\omega|\leq\gamma,\forall\omega\in[-\pi,\pi].\end{array}\
对偶问题可以表征为以下凸优化问题：
代码
% 本处仅给出上述凸优化问题的核心代码[完整代码联系博主]
if noise_flag == 0 % 无噪声版本
cvx_begin sdp quiet
cvx_solver sdpt3
variable S(M+1,M+1 hermitian
subject to
S >= 0;
S(M+1,M+1 == 1;
trace(S == 2; % 主对角元素迹为2
for j = 1 : M-1
sum(diag(S,j == S(M+1-j,M+1; % 非主对角线元素求和为0.
end
maximize (real(S(1:M,M+1'* Y % - 0.5 * norm(c
cvx_end
else % noise version
regular_param = 0.2; % 有噪声需要引入正则化参数
cvx_begin sdp quiet
cvx_solver sdpt3
variable S(M+1,M+1 hermitian
subject to
S >= 0;
S(M+1,M+1 == 1;
trace(S == 2;
for j = 1 : M - 1
sum(diag(S,j == S(M+1-j,M+1;
end
maximize (real(S(1:M,M+1'* Y - regular_param * norm(c;
cvx_end
end
原子范数软阈值问题的推导
推导
原子集合由各个正弦曲线的样本组成，\(a_{f,\phi}\in C^n\，表示为\(a_{f,\phi}=e^{i2\pi\phi}\left[1~e^{i2\pi f}~\cdots e^{i2\pi(n-1f}\right]^T\
相应的对偶范数采用直观的形式：\(\|v\|_\mathcal{A}^*=\sup\limits_{f,\phi}\langle v,a_{f,\phi}\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^{-2\pi i l f}=\sup\limits_{|z|\le1}\left|\sum\limits_{l=0}^{n-1}v_l z^l\right|\，\(\|v\|_\mathcal{A}^*\可以理解为在单位圆上获得的最大绝对值\(\zeta\mapsto\sum_{l=0}^{n-1}v_l{\zeta^l}\,\({\cal A}=\{a_{f,\phi}|f\in[0,1],\phi\in[0,1]\}\为与线谱原子集相关的原子范数的半正定规划。
定义映射\(T：\mathbb{C}^{n}\to\mathbb{C}^{n\times n}\,从输入创建一个Hermitian Toeplitz 矩阵，即\(T(x=\begin{bmatrix}x_1&&x_2&&...&&x_n\\ x_2^*&&x_1&&...&&x_{n-1}\\ \vdots&&\vdots&&\ddots&&\vdots\\ x_n^*&&x_{n-1}^*&&...&&x_1\end{bmatrix}\。
重写原子范数\(\Vert x \Vert_A=\sup_{\|v\|_\mathcal{A}^*\leq1}<x,v>\为下列形式：[\(T^*\表示伴随矩阵]
下面对上述问题进行对偶推导：
$L(Q,v,u,\Gamma=\langle x,v\rangle +u^* T^* (Q-u^He_1-\Gamma \begin{bmatrix}Q&v ;\ v^*&1\end{bmatrix} $
3、对变量\(Q\求解极值前，先将\(u^H T^*(Q\进步抽象为\(Tr(T(u\cdot Q\,那么关于\(Q\的偏导可表示为\(T(u-\Gamma\begin{bmatrix}I&0\\ 0&0\end{bmatrix}=0\，那么则有\(\Gamma_{11}=T(u\,其中\(F_{22}=t\，用于半正定约束\(\Gamma=\begin{bmatrix}T(u&x/2\\ x^*/2&t\end{bmatrix}\geq0\。
\(L=Re(v^*x+Tr(T(u\cdot Q-u^*e_1-Tr(\begin{bmatrix}T(uQ+Re(v^*x/2&x/2+T(uv\\ tv^*+Re(Qx^*/2&Re(x^*v/2+t\end{bmatrix} =-u^*e_1-t=-u_1-t\。
这等价于将对应目标函数缩放为\(-u_1/2-t/2\，那么原问题的对偶形式可以表示如下:
那么对应有噪声版本下的原问题对偶函数可以表示如下：[\(\tau\表示正则参数]
上述问题可以通过凸优化中的SDP解释器求解，但是计算复杂度较高，可以通过交替方向投影算子加速求解.
代码
交替方向投影算子
原子范数软阈值AST推导