Question

Prove that the sum of squared error is a convex function

Answer 1

Answer:

You want proof that the function

ϕ:β↦∥y−Xβ∥2=∥y∥2−2yTXβ+βTXTXβϕ:β↦‖y−Xβ‖2=‖y‖2−2yTXβ+βTXTXβ

is convex, right? (here ββ and yy are vectors and XX is a matrix). In other words, you need to prove that

ϕ(tβ1+(1−t)β2)−[tϕ(β1)+(1−t)ϕ(β2)]≤0ϕ(tβ1+(1−t)β2)−[tϕ(β1)+(1−t)ϕ(β2)]≤0

for all β1,β2β1,β2 and t∈[0,1]t∈[0,1]. After calculation, the left-hand term becomes

t2βT1XTXβ1+(1−t)2βT2XTXβ2+2t(1−t)βT1XTXβ2−tβT1XTXβ1−(1−t)βT2XTXβ2t2β1TXTXβ1+(1−t)2β2TXTXβ2+2t(1−t)β1TXTXβ2−tβ1TXTXβ1−(1−t)β2TXTXβ2

=−t(1−t)[(β1−β2)TXTX(β1−β2)]=−t(1−t)∥X(β1−β2)∥2=−t(1−t)[(β1−β2)TXTX(β1−β2)]=−t(1−t)‖X(β1−β2)‖2

which is clearly ≤0≤0.