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
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.
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$.
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.
I decided to make my comment an answer since I think that a few of these are a little complicated due to the careful bookkeeping for derivatives. We say a function $f$ is convex if for any $0 \le \gamma \le 1$ and $x, y \in \mathbb{R}^n$ we have that $$ f(\gamma x + (1-\gamma)y) \le \gamma f(x) + (1-\gamma)f(y). $$
We can now prove it in three (simple!) steps, which I will prove here for the sake of convenience, but these are extraordinarily standard one-line-proofs.
First, it's clear that the function $f(x) = x^2$ is convex (prove this in your favorite way).
Now, for any two convex functions $f, g: \mathbb{R}^n \to \mathbb{R}$, their sum is convex since, simply applying the definitions, $$ f(\gamma x + (1-\gamma)y) + g(\gamma x + (1-\gamma)y) \le \gamma (f(x) + g(x)) + (1-\gamma) (f(y) + g(y)). $$
Affine precomposition preserves convexity, since if $f$ is convex, then $$ f(A(\gamma x + (1-\gamma)y) + b) =f(\gamma Ax + (1-\gamma)Ay + (\gamma + (1-\gamma)) b) \le \gamma f(Ax + b) + (1-\gamma)f(Ay+b), $$
so, since the function $$ f(x) = \|Ax - b\|_2^2 = \sum_i (a_i^Tx - b_i)^2, $$ is the sum of a bunch of convex functions precomposed with affine functions, then $f$ is convex.
I just want to elucidate a bit on proofs provided by @roger and @acharuva.
Two popular ways to prove that a function $f$ is convex are to prove that:
\begin{equation} f(tx_1+(1-t)x_2)-tf(x_1)-(1-t)f(x_2) \leq 0 \end{equation}
for $t \in [0,1]$ and to prove that the second derivative is non-negative for the entire support (domain of $f$). The first is the definition of convexity and the second is a well-known theorem (Proof here http://www.princeton.edu/~aaa/Public/Teaching/ORF523/S16/ORF523_S16_Lec7_gh.pdf) . For multivariate functions this means proving that the Hessian is PSD (A matrix A is PSD if A is symmetric and $u^TAu\geq0$ irrespective of $u$).
In case of OLS or the linear regression cost function we have: \begin{equation} J(\theta) = \frac 1 2 {(X \theta -Y)}^2 = \frac12( \theta^TX^TX\theta -2Y^TX\theta + Y^TY) \end{equation}
\begin{equation} \frac {\partial J(\theta)} {\partial \theta} = X^T(X\theta-Y) \end{equation} [because $\nabla_Atr(ABA^TC)=C^TAB^T+CAB$; here A=$\theta^T$, B=$X^TX$, C=$I$]
\begin{equation} \frac {\partial^2 J(\theta)} {\partial \theta^2} = X^TX \end{equation}
$X^TX$ is a PSD matrix ($u^TX^TXu=\Vert Xu\Vert^2$) and hence the cost function is convex with respect to $\theta$. That's the first proof.
The 2nd proof goes like this. It requires us to prove that \begin{equation} J(t\theta_1+(1-t)\theta_2)-tJ(\theta_1)-(1-t)J(\theta_2)\leq0 \end{equation} $\forall \theta_1, \theta_2$ and $\forall t \in [0,1]$.
We will call this $E_1$. Note that here \begin{equation} J(\theta) = \frac12( \theta^TX^TX\theta -2Y^TX\theta + Y^TY) \end{equation}
The full expansion of $E_1$ will be slightly verbose but we can make our life easy by considering that for any linear function $f(x)=ax+b$, \begin{equation} f(tx_1+(1-t)x_2)=tf(x_1)+(1-t)f(x_2) \end{equation} You can convince yourself of this by expanding both sides.
This means the term $\frac12( -2Y^TX\theta + Y^TY)$ of $J(\theta)$ will be $0$ in $E_1$. Let us now look at $E_1$ with only the first term of $J(\theta)$ and drop the $\frac12$ for convenience.
\begin{equation} LHS = {(t\theta_1+(1-t)\theta_2)}^TX^TX(t\theta_1+(1-t)\theta_2)-t\theta_1^TX^TX\theta_1-(1-t)\theta_2^TX^TX\theta_2 \end{equation} \begin{equation} LHS = t^2\theta_1^TX^TX\theta_1+(1-t)^2\theta_2^TX^TX\theta_2+2t(1-t)\theta_1^TX^TX\theta_2 -t\theta_1^TX^TX\theta_1-(1-t)\theta_2^TX^TX\theta_2 \end{equation}
[Note that $\theta_1^TX^TX\theta_2 $=$(X\theta_1)^T(X\theta_2)$=$(X\theta_2)^T(X\theta_1)$=$\theta_2^TX^TX\theta_1$]
\begin{equation} LHS = (t^2-t)\theta_1^TX^TX\theta_1+((1-t)^2-(1-t))\theta_2^TX^TX\theta_2+2t(1-t)\theta_1^TX^TX\theta_2 \end{equation}
\begin{equation} LHS = -t(1-t)[\theta_1^TX^TX\theta_1+\theta_2^TX^TX\theta_2-2\theta_1^TX^TX\theta_2] \end{equation}
[Note that $(1-t)^2-(1-t) = t^2-t=-t(1-t)$]
\begin{equation} LHS = -t(1-t)[(\theta_1-\theta_2)^TX^TX(\theta_1-\theta_2)] \end{equation}
\begin{equation} LHS = -t(1-t) \Vert X(\theta_1-\theta_2) \Vert^2 \end{equation}
which is always $\leq0$.
This completes our second proof.
If you are having trouble following the second proof, try to first prove that a scalar quadratic function $f(x)=ax^2+bx+c$ is convex for $a>0$. I promise that exercise will be helpful (since our function for $J(\theta)$ is also quadratic in $\theta$).
