5
$\begingroup$

It's well known that linear least squares problems are convex optimization problems. Although this fact is stated in many texts explaining linear least squares I could not find any proof of it. That is, a proof showing that the optimization objective in linear least squares is convex. Any idea how can it be proved? Or any pointers that I can look at?

Thanks

|cite|improve this question
$\endgroup$
8
$\begingroup$

Another way to prove that a function is convex is by showing that the second order derivative (if it exists) is positive semi-definite.

$$ \phi: \beta \mapsto \Vert y - X \beta \Vert^2 = \Vert y \Vert^2 - 2 y^T X \beta + \Vert X \beta \Vert^2$$ $\phi$ is twice differentiable and the second derivative (i.e. the Hessian) is

$$ \dfrac {\partial \phi} {\partial \beta} = - 2y^TX + 2(X\beta)^TX =- 2y^TX + 2\beta^TX^TX $$

$$ \dfrac {\partial^2 \phi} {\partial \beta \partial \beta^T} = 2X^TX$$

which is a positive semi-definite matrix. Therefore, $\phi$ is a convex function.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How were you able to differentiate ϕ twice? $\endgroup$ – David May 4 '17 at 4:02
  • $\begingroup$ Also, is the second derivative the Hessian? $\endgroup$ – David May 4 '17 at 6:18
  • 1
    $\begingroup$ The first derivative is incorrect. You're adding a row vector to a column vector. $\endgroup$ – Rodrigo de Azevedo Sep 28 '17 at 9:16
  • $\begingroup$ can anyone explain me how do we reach the first derivative? $\endgroup$ – Bagus Trihatmaja Jan 12 '18 at 6:30
  • 1
    $\begingroup$ @BagusTrihatmaja I corrected the first derivative in my edit. It depends upon the fact that the derivative of $\Vert \mathbf{x}\Vert^2$ with respect to $\mathbf{x}$ is $2\mathbf{x}^T$. Then you can make use of the chain rule. $\endgroup$ – Christian Sykes Jan 12 '18 at 11:07
4
$\begingroup$

You want a proof that the function $$ \phi: \beta \mapsto \Vert y - X \beta \Vert^2 = \Vert y \Vert^2 - 2 y^T X \beta + \beta^T X^T X \beta $$ is convex, right? (here $\beta$ and $y$ are vectors and $X$ is a matrix). In other words, you need to prove that $$ \phi(t \beta_1 + (1-t) \beta_2) - \left[ t \phi( \beta_1) + (1-t) \phi(\beta_2) \right] \leq 0 $$ for all $\beta_1, \beta_2$ and $t \in [0,1]$. After calculation, the left-hand term becomes $$ t^2 \beta_1^T X^T X \beta_1 + (1-t)^2 \beta_2^T X^T X \beta_2 + 2 t(1-t) \beta_1^T X^T X \beta_2 - t \beta_1^T X^T X \beta_1 - (1-t) \beta_2^T X^T X \beta_2 $$ $$ = - t(1-t) \left[ (\beta_1 - \beta_2)^T X^T X (\beta_1 - \beta_2) \right] = - t(1-t) \Vert X (\beta_1 - \beta_2) \Vert^2$$ which is clearly $\leq 0$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can you expand on "after calculation"? $\endgroup$ – vega Dec 7 '17 at 15:01
  • $\begingroup$ @vega You can use the fact that $\Vert \mathbf{x}\Vert^2 = \mathbf{x}^T\mathbf{x}$. $\endgroup$ – Christian Sykes Jan 12 '18 at 11:10
0
$\begingroup$

Here's an alternative way to see the convexity of $f(\beta)\triangleq \Vert y-X\beta\Vert^2$. For $t\in [0,1]$, let $\bar t=1-t$. Then

$f(t\alpha + \bar t \beta)=\Vert t(y-X\alpha)+\bar t (y-X\beta)\Vert^2 \le \left(t\Vert y-X\alpha\Vert +\bar t\Vert y-X\beta\Vert\right)^2\le t\Vert y-X\alpha\Vert^2+\bar t \Vert y-X\beta\Vert^2=tf(\alpha)+\bar tf(\beta)$

where the first inequality is due to triangle inequality of vector norm, and the 2nd inequality follows because the square function ($x^2$) is also convex.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I just noted the copper.hat's comment above. This answer in fact just elaborated his comment. $\endgroup$ – syeh_106 Nov 26 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.