Convex Optimization 2015.09.30

Let \(\nabla f(x) = 2A^TAx - 2A^Tb = 0\), then \(x = (A^TA)^{-1}A^Tb\)

\((A^TA)^{-1}A^T\) is Moore-Penrose Pseudoinverse.

SVD(Singular value decomposition)

\(A = U \Sigma V^T, A \in \mathbb{R}^{m \times n}, U \in \mathbb{R}^{m \times r}, \Sigma \in \mathbb{R}^{r \times r}, V^T \in \mathbb{R}^{r \times n}, r = rank(A)\)

\(U\) is orthogonal basis of \(col(A)\), \(V^T\) is basis of \(row(A)\)

\(A^{inv} = V \Sigma ^{-1} U^T\)

Least Square Solution \(x = A^{inv} b\)

\(col(A)\): subspace speened by \(col S\) of \(A\), \(Ax \in col(A)\)

Projection: \(P_A = UU^T, U = [u_1, u_2, \cdots, u_n]\), \(u_i\) is column vector.

Projector: \(P^2 = P\) (特征向量只有1和0)

\(u_i^T\) is a basis vector in \(col A\).

\(u_i^T(I - P_A)b = (u_i^T - u_i^T UU^T)b = 0\)

\(UU^T b = Ax = AA^{inv}b\)

\(\min \lVert Ax - b \rVert _2^2 + r \lVert x \rVert _2^2\)

  • Solution: \(A \hat{x} = A(A^TA + \lambda I)^{-1} A^T b = \sum _{j = 1}^n u_j \frac{\sigma _j^2}{\sigma _j^2 + \lambda} u_j^T b\)

  • Definition: Convex cone \(C: x, y \in C, ax + by \in C, a, b \ge 0\)

    Semidefinite cone

    T: affine transform \(\mathbb{R}^n \to \mathbb{R}^d\), \([\mathbb{R}^{d \times n}][\mathbb{R}^n] = [\mathbb{R}^d]\)

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

    polar set of \(Q\): \(Q^{\Delta} = \{x \mid < x, y > \le 1, \forall y \in Q\}\)

    (unit norm ball of \(\lVert \cdot \rVert\))\(^{\Delta}\) = (unit norm ball of \(\lVert \cdot \rVert _{*}\))

    Quadratic norm: \(\lVert z \rVert _p = (z^T P z)^{\frac{1}{2}} = \lVert p^{\frac{1}{2}} z \rVert, p \in S_{++}^n\)

    Lp-norm: \((\sum _i \lvert x_i \rvert ^p)^{\frac{1}{p}}, p \ge 1\)

    Dual Lp-norm: \(\frac{1}{p} + \frac{1}{q} = 1\)