Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$).
