Convex Optimization 2015.10.14

Existen of SVD

For any \(A \in \mathbb{R}^{m \times n}\) of rank \(r\) there exists \(U \in \mathbb{R}^{m \times r}, D \in diag(r \times r), V \in \mathbb{R}^{n \times r}\)

s.t. \(A = UDV^T\) and \(V^T V = I_r, U^T U = I_r\)

\(\begin{bmatrix} & \\ & A \\ & \\ \end{bmatrix} = \begin{bmatrix} \\ U \\ \\ \end{bmatrix} \begin{bmatrix} D \\ \end{bmatrix} \begin{bmatrix} V^T & \\ \end{bmatrix}\)

  • Proof: \(A^TA \in \mathbb{R}^{n \times n}\) is positive seidefinite, so there exists \(D \in \mathbb{R}^{r \times r}\), \(V \in \mathbb{R}^{n \times r}\), \(V' \in \mathbb{R}^{n \times (n - r)}\), \([V V'] \in \mathbb{R}^{n \times n}\)

    such that \([V V'] \begin{bmatrix} D^2 & 0 \\ 0 & 0 \end{bmatrix} [V V']^T = A^T A\)

    where \([V V']^T [V V'] = I_n\)

    so \(\begin{bmatrix} D^2 & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} V^T \\ V'^T \end{bmatrix} A^T A [V V']\)

    so \(D^2 = V^T A^T A V\)

    Let \(U = AVD^{-1}\) then \(U^T U = D^{-1} V^T A^T A V D^{-1} = D^{-1} D^2 D^{-1} = I_{r \times r}\)

  • Dual norm: \(\lVert z \rVert _* = \max \{ x^T z : \lVert x \rVert \le 1 \}\)

  • Fact: \(\lVert \cdot \rVert _{**} = \lVert \cdot \rVert\)

  • Proof: Sufficient to show for \(x\) s.t. \(\lVert x \rVert = 1\).

    \(\lVert x \rVert _{**} = \max \{ z^Tx : \lVert z \rVert _* \le 1 \} \le 1\)

    Still need to show that \(\lVert x \rVert _{**} \ge 1\)

  • Claim: There exists a \(z_0\), \(\lVert z_0 \rVert _* = 1\), such that \(\lVert z_0 \rVert _* = x^T z_0\)

  • Proof of claim: Let \(C = \{ x \}\), \(D = \{ u : \lVert u \rVert \lt 1 \}\)

    Then \(C\) and \(D\) are convex, disjoint.

    So there exists \(a \in \mathbb{R}^n \backslash \{0\}, b \in \mathbb{R}, s.t. a^T x \ge b, a^T u \le b \forall u \in D\) (\(\implies \lVert a \rVert _* = b\))

    Let \(z_0 = \frac{a}{\lVert a \rVert _*} = \frac{a}{b}\),

    then \(\lVert z_0 \rVert _* = z_0^T x = \frac{\lVert a \rVert _*}{b} = 1\).

  • Example: Let \(A \in S_{++}^n\), then \(\lVert x \rVert _A = (x^T A x)^{1/2}\) is the quadratic norm associated to \(A\).

    Have \(\lVert x \rVert _A = \lVert A^{1/2} x \rVert _2\).

    If \(A = PDP^T\) then \(A^{1/2} = PD^{1/2}P^T \in S_{++}^n\)

    \(\lVert w \rVert _{A*} = \max \{ x^T w : \lVert x \rvert _A \le 1 \}\)

    \(= \max \{ x^T w : x^T A x \le 1 \}\)

    \(= \max \{ x^T w : x^T PDP^T x \le 1 \}\)

    \(\underset{x = PD^{-1/2} u}{\overset{u = D^{1/2}P^Tx}{\implies}} \max \{ (PD^{-1/2} u)^T w : \lVert u \rVert _2 \le 1 \}\)

    \(= \max \{ u^T D^{-1/2} P^T w : \lVert u \rVert _2 \le 1 \}\)

    \(= \lVert D^{-1/2} P^T w \rVert _{2*}\)

    \(= \lVert D^{-1/2} P^T w \rVert _2\)

    \(= \lVert P^T w \rVert _{D^{-1}}\)

    \(= ((P^T w)^T D^{-1} P^T w)^{1/2}\)

    \(= (w^T P^T D^{-1} P w)^{1/2}\)

    \(\min \lVert Ax - b \rVert _2 \implies A^T Ax = A^T b\)

    \(x = A^{inv} b, A^{inv} = V \Sigma ^{-1} U^T\) (pseudo-inverse)

    point-set topology

    \(A \in S_+^n \implies \left \langle A, S_+^n \right \rangle \ge 0\)

    \(\implies \left \langle A, TS \right \rangle \ge 0\)

    \(\forall B \in S_+^n \implies tr(A^T B) \ge 0\)

    \(A = C^T C = \sum_{i = 1}^n c_i c_i^T\)

    \(\left \langle xx^T, B \right \rangle = x^T B x\)