[笔记] Convex Optimization 2015.09.30

Let ∇f(x)=2ATAx−2ATb=0 , then x=(ATA)−1ATb
(ATA)−1AT is Moore-Penrose Pseudoinverse.

SVD(Singular value decomposition)
A=UΣVT,A∈Rm×n,U∈Rm×r,Σ∈Rr×r,VT∈Rr×n,r=rank(A)
U is orthogonal basis of col(A) , VT is basis of row(A)
Ainv=VΣ−1UT
Least Square Solution x=Ainvb

col(A) : subspace speened by colS of A , Ax∈col(A)
Projection: PA=UUT,U=[u1,u2,⋯,un] , ui is column vector.
Projector: P2=P (特征向量只有1和0)
uTi is a basis vector in colA .
uTi(I−PA)b=(uTi−uTiUUT)b=0
UUTb=Ax=AAinvb

min∥Ax−b∥22+r∥x∥22
- Solution: Ax^=A(ATA+λI)−1ATb=∑nj=1ujσ2jσ2j+λuTjb
- Definition: Convex cone C:x,y∈C,ax+by∈C,a,b≥0
Semidefinite cone
T: affine transform Rn→Rd , [Rd×n][Rn]=[Rd]

Dual norm: ∥z∥∗=max{zTx∣∥x∥≤1}

polar set of Q : QΔ={x∣<x,y>≤1,∀y∈Q}
(unit norm ball of ∥⋅∥ ) Δ = (unit norm ball of ∥⋅∥∗ )

Quadratic norm: ∥z∥p=(zTPz)12=∥p12z∥,p∈Sn++
Lp-norm: (∑i∣xi∣p)1p,p≥1
Dual Lp-norm: 1p+1q=1