[笔记] Convex Optimization 2015.10.14

Existen of SVD
For any A∈Rm×n of rank r there exists U∈Rm×r,D∈diag(r×r),V∈Rn×r
s.t. A=UDVT and VTV=Ir,UTU=Ir
⎡⎣⎢A⎤⎦⎥=⎡⎣⎢U⎤⎦⎥[D][VT]
- Proof: ATA∈Rn×n is positive seidefinite, so there exists D∈Rr×r , V∈Rn×r , V′∈Rn×(n−r) , [VV′]∈Rn×n
such that [VV′][D2000][VV′]T=ATA
where [VV′]T[VV′]=In
so [D2000]=[VTV′T]ATA[VV′]
so D2=VTATAV
Let U=AVD−1 then UTU=D−1VTATAVD−1=D−1D2D−1=Ir×r

• Dual norm: ∥z∥∗=max{xTz:∥x∥≤1}
• Fact: ∥⋅∥∗∗=∥⋅∥
• Proof: Sufficient to show for x s.t. ∥x∥=1 .
  ∥x∥∗∗=max{zTx:∥z∥∗≤1}≤1
  Still need to show that ∥x∥∗∗≥1
• Claim: There exists a z0 , ∥z0∥∗=1 , such that ∥z0∥∗=xTz0

• Proof of claim: Let C={x} , D={u:∥u∥<1}
  Then C and D are convex, disjoint.
  So there exists a∈Rn∖{0},b∈R,s.t.aTx≥b,aTu≤b∀u∈D ( ⟹∥a∥∗=b )
  Let z0=a∥a∥∗=ab ,
  then ∥z0∥∗=zT0x=∥a∥∗b=1 .

• Example: Let A∈Sn++ , then ∥x∥A=(xTAx)1/2 is the quadratic norm associated to A .
  Have ∥x∥A=∥A1/2x∥2 .
  If A=PDPT then A1/2=PD1/2PT∈Sn++
  ∥w∥A∗=max{xTw:∥x∣A≤1}
  =max{xTw:xTAx≤1}
  =max{xTw:xTPDPTx≤1}
  ⟹u=D1/2PTxx=PD−1/2umax{(PD−1/2u)Tw:∥u∥2≤1}
  =max{uTD−1/2PTw:∥u∥2≤1}
  =∥D−1/2PTw∥2∗
  =∥D−1/2PTw∥2
  =∥PTw∥D−1
  =((PTw)TD−1PTw)1/2
  =(wTPTD−1Pw)1/2

min∥Ax−b∥2⟹ATAx=ATb
x=Ainvb,Ainv=VΣ−1UT (pseudo-inverse)

point-set topology
A∈Sn+⟹⟨A,Sn+⟩≥0
⟹⟨A,TS⟩≥0
∀B∈Sn+⟹tr(ATB)≥0
A=CTC=∑ni=1cicTi
⟨xxT,B⟩=xTBx