13-03 Dual norms
임의의 norm \(\| x \|\)를 살펴보자
\[l_p \text{ norm: } \lVert x \rVert_p = (\sum^n_{i=1} \rVert x_i \rVert_p)^{1/p}, \text{ for } p ≥ 1\] \[\text{Trace norm: } \lVert X \rVert_{tr} = \sum^r_{i=1} σ_i(X)\]
norm \(\lVert x \rVert\)의 dual norm은 \(\lVert x \rVert_{∗}\)와 같이 나타내며 다음과 같다.
\[\lVert x \rVert_{∗} = \max_{\lVert z \rVert ≤1} z^Tx\]
여기서 어떤 임의의 \(y\)가 있다고 가정해보자. 그려면 \(\frac{y}{\rVert y \rVert}\)를 \(z\)라고 할때 \(\rVert z \rVert = 1\)이 된다. 또한 \(\rVert z^Tx \rVert \le \rVert x \rVert_{*}\)이 되며, 그러므로 Cauchy-Schwartz inequality와 유사한 형태의 \(\rVert y^Tx \rVert \le \rVert y \rVert \rVert x \rVert_{*}\)가 성립한다.
특정 조건에서의 Dual Norm의 예제를 살펴보자.
\[l_p \text{ norm dual: } (\lVert x \rVert_p)_{*} = \lVert x \rVert_{q}, \text{ where } 1/p + 1/q = 1\] \[\text{Trace norm dual: } (\lVert X \rVert_{tr})_{*} = \lVert X \rVert_{op}) = σ_1(X)\]
[Proof]
\(l_p\) norm dual에서 다음이 성립함을 증명해보자
\[(\lVert x \rVert_p)_{*} = \lVert x \rVert_{q}, \text{ where } 1/p + 1/q = 1 \qquad \text{(1)}\]Proof
\[(\lVert x \rVert_p)_{*} = \sup \{ z^Tx : x \in \mathbb{R}^n, \rVert x \rVert_q \le 1 \} \qquad \text{(2)}\]한편, Holder inequality에 의해서, 다음이 성립한다
\[z^T x ≤ \rVert z^tx \rVert 1 ≤ \rVert z \rVert_p \rVert x \rVert_q (\text{ where }, 1/p + 1/q = 1)\qquad \text{(3)}\]위 (1)은 아래와 같은 관계가 성립한다.
\[(\rVert z \rVert_q)_∗ ≤ \rVert z \rVert_p\qquad \text{(4)}\]따라서, \(\rVert x \rVert_q ≤ 1\) 이면서, \(z^Tx\)가 \(\rVert z \rVert_p\) 을 만족시키는 \(x\)를 찾으면 \((\rVert z \rVert_q)_∗ = \rVert z \rVert\rVert_p\) 가 성립함을 알 수 있다.
한편, \(y := sign(z) \rVert z\rVert^{p−1} \left( y_i = sign(z_i)\rVert z_i\rVert^{p−1} \right)\)로 놓고, \(x = y\) 로 놓으면, \(\rVert y \rVert_q\) \(\rVert x \rVert_q =1\)을 만족하고, \(z^Tx = \rVert z \rVert_p\) 임을확인할수있다.
따라서,다음이성립된다.
\[( \rVert z \rVert_ q)_∗ = \rVert z \rVert_p, (1/p+1/q=1)\qquad \text{(5)}\]
Dual norm의 dual norm은 다시 original norm이 된다.
\[\lVert x \rVert_{**} = \lVert x \rVert\]
다음 문제를 살펴보자.
\[\min_y \lVert y \rVert \qquad \text{ subject to } y = x\]
Optimal value가 \(\rVert x \rVert\) 라고 할때, 라그랑지안은 다음과 같이 표현 된다.
\[L(y,u) = \rVert y \rVert+ u^T(x−y) = \rVert y \rVert − y^Tu + x^Tu\]
Dual norm \((\lVert · \rVert_{∗})\)으로 나타내면, 다음과 같다.
\[\text{If } \rVert u \rVert_{∗} ≤ 1,\text{ then} \qquad \min_y \{ \rVert y \rVert − y^Tu \} = 0\] \[\text{If } \rVert u \rVert_{∗} > 1, \text{ then} \qquad \min_y \{ \rVert y \rVert − y^Tu \} = −∞\]
[Note]
\[\text{If } \rVert u \rVert_{∗} ≤ 1, \text{ then} \qquad \min_y \{ \rVert y \rVert − y^Tu \} = 0\] \[\max_y (y^Tu - \rVert y \rVert ) = 0\] \[y^Tu \le \rVert y \rVert \rVert u \rVert_* \le \rVert y \rVert\] \[\text{If } \rVert u \rVert_{∗} > 1, \text{ then} \qquad \min_y \{ \rVert y \rVert − y^Tu \} = −∞\]\(\text{Can always find} \qquad\) \(z\) with \(\rVert z \rVert = 1 \qquad \text{ subject to }\qquad z^Tu = \rVert u \rVert_{*} \qquad ( argmax_{\rVert z \rVert \le 1} z^Tu )\)
\(\text{take}\) \(y = t \cdot z, \qquad t > 0\)
\[y^Tu = t \cdot \rVert u \rVert_{*}\] \[\text{ for this } y, \qquad y^Tu - \rVert y \rVert = t \cdot \rVert u \rVert_{*} - t \rightarrow ∞ \text{ as } t \rightarrow ∞\] \[\text{ so therefore } g(u) = \min_y L(y, u) = x^Tu - I(\rVert u \rVert_{*} \le 1)\]dual problem
\[\max_u g(u) \iff \max_{\rVert u \rVert_{*} \le 1} x^Tu\]
그러므로 Lagrange dual 문제는 다음과 같다.
\[\max_u u^Tx \qquad \text{ subject to }\qquad \rVert u \rVert_{∗} ≤ 1\]
Inequality constraint 가 존재하지 않기 때문에, Slater’s condition을 만족하며, Strong duality에 따라서 \(f^{\star} = g^{\star}\)가 된다. 즉, \(\rVert x \rVert = \rVert x \rVert_{∗∗}\) 이다.
