本文將主要圍繞範數的經典問題進行推導、分析。
問題定義：\(\underset{x}{\min}||y-X\beta||_2^2+\tau||\beta||_\mathcal{A}\)
問題推導：
0、上述問題是典型的無約束問題，可以通過變數替換的思想進行處理。
1、令\(z=X\beta\)，上述問題更新為\(g(u)=\min_{\beta,z}=\frac{1}{2}\Vert y-z\Vert_2^2+\lambda\Vert\beta\Vert_1+u^T(z-X\beta)\).
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\)
3、\(g(\beta)=\min_\beta~\lambda\Vert\beta\Vert_1-u^TX\beta=-\max_\beta~\lambda(-\Vert\beta\Vert_1+\frac{u^TX\beta}{\lambda})=-\lambda~g^*(\frac{X^Tu}{\lambda})=-\lambda I_{\{v_i|\Vert v\Vert_\infty \leq1\}}(\frac{X^Tu}{\lambda})\),這個最小項可以表徵為示性函數形式，示性函數\(f^*(y)=\begin{cases}0&||y||_*\leq1\\ \infty&\text{otherwise}\end{cases}=I_{\{z:||z||_*\leq1\}}(y)\).
4、對\(g(z)\)求極值，可以得到\(-(y-z)+u=0\)，即\(z=y-u\).
5、將上述約束代入\(g(z)\)，可以得到下式：
\(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\)
有噪聲情況下，原子範數的原問題可以抽象為：\(\operatorname*{min}_{x}\|x\|_{\mathcal{A}}\mathrm{subject~to}\left\{\begin{array}{l}{{\mathbf{y}={\mathcal{F}}_{M}x+\mathbf{n},}}\\ {{\|\mathbf{n}\|_{2}\leq\epsilon.}}\end{array}\right.\)
對偶函數可以寫為\(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)\)
將拉格朗日方程進行重寫，\(\inf~L(x,\mathbf{c},\xi)=\mathrm{Re}[c^Hy-c^Hn]+\xi[n^Hn-\epsilon^2]+\inf[\Vert x\Vert_A-\mathrm{Re}[\lambda^HF_Mx]]\\\)
2、下确界的求解是關於\(x\)的最小化，因此對原拉格朗日增廣函數的最小化可以轉換為對\([\Vert x\Vert_A-\mathrm{Re}[\lambda^HF_Mx]]\)求下确界。在求這項下确界時，需要對式中的噪聲功率引數\(n\)和對偶變數\(\xi\)求偏導尋找極值點。
當對噪聲功率引數\(n\)求偏導時[目的是為了使噪聲功率最小化]，有\(\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}\)
當對對偶變數\(\xi\)求偏導時，有\(\frac{\partial g(\mathbf{c},\xi)_{n_o}}{\partial \xi}=\frac{c^Hc}{4\xi^2}-\epsilon^2=0\),可以得到最佳極值點\(\xi_0=\frac{\Vert c\Vert}{2\epsilon}\).
最後，基於最優極值點對偶函數可以表示為\(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)]\).
對於下确界項，對每個\(x_i\)，有\(\mathrm{Re}[(c^H\mathcal{F}_{M})_ix_i]=\mathrm{Re}[(\mathcal{F}_{M}^Hc)^H_ix_i]=|(\mathcal{F}_{M}^Hc)_i||x_i|\cos\phi_i\)，\(\phi_i\)表示\(x_i\)和\({F}_{M}^Hc\)間的角度，基於此可以得到以下結論：\(\begin{array}{c}|x_i|-\mathrm{Re}\left[\left(\mathcal{F}_M^H\mathbf{c}\right)_i^Hx_i\right]=|x_i|\left[1-|\left(\mathcal{F}_M^H\mathbf{c}\right)_i|\cos\phi_i\right]\geq|x_i|\left[1-|\left(\mathcal{F}_M^H\mathbf{c}\right)_i|\right].\end{array}\)
當\(|\mathcal{F}_{M}^Hc|\leq1\)時下确界項為0；當\(|x_i|\left[1-|\left(\mathcal{F}_M^H\mathbf{c}\right)_i|\right]<0\)時下确界可以達到\(-\infty\)。
3、整理上述討論，有噪聲下的原子範數的對偶問題可以表徵為:
\(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.\)
在上式中，\(\mathcal{F}_M^H\mathbf{c}\)中\(\mathcal{F}_M^H\)表示逆FFT運算元，對偶多項式可以表示為\(H(z)=\mathcal{F}_M^H\mathbf{c}=\sum\limits_{m=0}^{M-1}c_m z^m=\sum\limits_{m=0}^{M-1}c_m e^{-j\left(2\pi\frac{d}{\lambda}t\right)m}\)，其中\(z(t)=e^{-j\left(2\pi\frac{d}{\lambda}t\right)}\).
4、為了進一步抽象\(g(\mathbf{c})\)，我們可以作以下表示：
令\(a(\omega)=[1,e^{j\omega},...,e^{j\omega(L-1)}]^T\)為\(L-1\)次的三角多項式向量，那麼因果三角多項式可以表徵為：\(H(\omega)=\sum_{l=0}^{L-1}h_l e^{-j\omega l}=\mathbf{a}(\omega)^H\mathbf{h}\),其中\(\textbf{h}=\left[h_0,\cdots,h_{L-1}\right]^T\in\mathbb{C}^L\)表示多項式係數向量.
對於非負三角多項式，可以有Hermitian矩陣\(R(\omega)=|H(\omega)|^2=H(\omega)H(\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)\)和\(B(\omega)\)滿足以下不等關係：\(|H(\omega)|\leq|B(\omega)|,\forall\omega\in[-\pi,\pi]\)
這意味著\(|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.\)
令多項式\(H(\omega)\)的振幅均勻有界(對所有\(\omega\in[-\pi,\pi]\)有\(H(\omega)\leq\gamma\),其中\(\gamma \in R_+\)為給定正實數.作為有界三角多項式的特例，令\(|B(\omega)|=\gamma\)，那麼\(H(\omega)\leq\gamma\)可以用兩個線性不等式抽象，如下：(其中\(R_B(\omega)=\gamma^2\))
\(\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}\)
回到本節開始處，基於振幅一致有界條件和Schur補條件,對偶問題可以表徵為以下凸優化問題：
\(\begin{array}{c}\max\operatorname{Re}\left(\mathbf{c}^{H}\mathbf{y}-\epsilon\Vert c\Vert_2\right)~~\operatorname{subject to}\left[\begin{array}{cc}\mathbf{Q}_{M\times M}&\mathbf{c}_{M\times1}\\ \mathbf{c}_{1\times M}&1\end{array}\right]\succeq0,\\ \sum_{i=1}^{M-j}\mathbf{Q}_{i,i+j}=\left\{\begin{array}{cc}1,&j=0\\ 0,&j=1,\cdots,M-1.\end{array}\right.\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-1)f}\right]^T\)
無限原子集\(\mathcal{A}=\{a_{f,\phi}:f\in[0,1],\phi\in[0,1]\}\)組成了\(x^*\)適當的原子集合，\(x^*\)在對偶問題中可以寫成一個稀疏的非負的原子組合。\(x^\star=\sum_{l=1}^k c_l^\star a_{f_l^\star,0}=\sum_{l=1}^k|c_l^\star|a_{f_l^\star,\phi_l}\)，\(c_{l}^{\star}=|c_{l}^{\star}|e^{i2\pi\phi_{l}}\).
相應的對偶範數採用直觀的形式：\(\|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]\}\)為與線譜原子集相關的原子範數的半正定規劃.
根據上式可知向量\(v\in C^n\)的對偶原子範數是複數三角多項式\(V(f)=\sum_{l=0}^{n-1}v_l e^{j2\pi lf}\)的最大絕對值；因此，對對偶原子範數的約束等價於對\(V(f)\)大小的限制：\(||v||_A^\text{t}\leq\tau\Leftrightarrow|V(f)|^2\leq\tau^2,\forall f\in[0,1]\).函數\(q(f)=\tau^{2}-|V(f)|^{2}\)是一個三角多項式，\(q(f)\)非負的充要條件是可以寫成三角多項式的平方和.
定義對映\(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}\).
對於給定的因果三角多項式\(V(f)=\sum_{l=0}^{n-1}v_{l}e^{-2\pi i l f},\)如果有且僅有復Hermitian矩陣\(Q\)存在時有\(|V(f)|\leq\tau\)，這與原子範數對偶問題中第4節證明類似，即有\(T^*(Q)=\tau^2e_1~\mathrm{and}~\begin{bmatrix}Q&v\\ v^*&1\end{bmatrix}\succeq0.\)其中\(e_1=[1,0,0,....,0]^T\)，\(v^*\)表示\(v\)的Hermitian轉置.
重寫原子範數\(\Vert x \Vert_A=\sup_{\|v\|_\mathcal{A}^*\leq1}<x,v>\)為下列形式：[\(T^*\)表示伴隨矩陣]
\(\begin{array}{ll}\text{maximize}_{v,Q}&\langle x,v\rangle\\ \text{subject to}&T^*(Q)=e_1\\ &\begin{bmatrix}Q&v\\ v^*&1\end{bmatrix}\succeq0.\end{array}\)
下面對上述問題進行對偶推導：
1、首先需要將上述問題轉化為無約束的拉格朗日方程形式，可以表示如下：
$L(Q,v,u,\Gamma)=\langle x,v\rangle +u^* T^* (Q)-u^He_1-\Gamma \begin{bmatrix}Q&v ;\ v^*&1\end{bmatrix} $
2、對變數\(v\)求解極值，則有\(x- Tr(\Gamma\begin{bmatrix}0&I\\ I^*&0\end{bmatrix})=x- Tr(\Gamma\begin{bmatrix}\Gamma_{12}I^*&\Gamma_{11}I\\ \Gamma_{22}I^*&\Gamma_{21}I\end{bmatrix})=x-2\Gamma_{12}=0\)，那麼可以得到\(\Gamma_{12}=\frac{x}{2};\)\(\Gamma_{21}=\frac{x^*}{2}\)
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\).
4、將\(\Gamma\)結果代入到\(L\)中，那麼有如下證明：
\(L=Re(v^*x)+Tr(T(u)\cdot Q)-u^*e_1-Tr(\begin{bmatrix}T(u)Q+Re(v^*x)/2&x/2+T(u)v\\ tv^*+Re(Qx^*)/2&Re(x^*v)/2+t\end{bmatrix} ) =-u^*e_1-t=-u_1-t\).
根據半正定約束條件\(T(u)t-xx^*/4\geq0\)，通過對\(u\)和\(t\)縮放則有\(2t\cdot T(2u)-xx^*\geq0\)
這等價於將對應目標函數縮放為\(-u_1/2-t/2\)，那麼原問題的對偶形式可以表示如下:
\(\begin{array}{l l}{{\mathrm{minimize}_{t,u}}}&{{\frac{1}{2}(t+u_{1})}}\\ {{\mathrm{subject~to}}}&{{\begin{bmatrix}{T(u)}&{x}\\ {x^{*}}&{t}\end{bmatrix}\succeq0.}}\end{array}\)
那麼對應有噪聲版本下的原問題對偶函數可以表示如下：[\(\tau\)表示正則引數]
\(\begin{array}{ll}\text{minimize}_{t,u,x}&\frac{1}{2}\|x-y\|_2^2+\frac{\tau}{2}(t+u_1)\\ \text{subject to}&\begin{bmatrix}T(u)&x\\ x^*&t\end{bmatrix}\succeq0.\end{array}\)
上述問題可以通過凸優化中的SDP直譯器求解，但是計算複雜度較高，可以通過交替方向投影運算元加速求解.