# $y^TX^TXy$ achieves minimum when its second derivative is positive definite.

Prove that $y^T X^T X y$ achieves minimum value when its matrix of second derivative is a positive definite matrix.

I differentiated with respect to $y$ and got that the second derivative of this term only depends on $X^T X$ and thus $X^T X$ is our matrix of second derivative but I don't see the connection between then minimum and positive definiteness in this case and am unable to proceed with the proof.

Any critical point $\mathbf{y_0} \in \mathbb{R}^n$ (where the gradient $\nabla f(\mathbf{y})$ is zero) of a multi-variable function $f(\mathbf{y}): \mathbb{R}^n\rightarrow\mathbb{R}$ is a minimum if the Hessian (matrix of second derivatives) $Hf(\mathbf{y})$ of this function evaluated at that critical point (i.e. $Hf(\mathbf{y_0})$) is a positive definite matrix. Your function is no exception!

If you approximate your function $\mathbf{y}^TX^TX\mathbf{y}=f(\mathbf{y})$ (or any other one) using a second order approximation (Taylor expansion) you get (knowing that $\nabla f(\mathbf{y_0})=\mathbf{0}$):

$f(\mathbf{y})\approx F(\mathbf{y})=f(\mathbf{y_0})+\frac{1}{2}(\mathbf{y}-\mathbf{y_0})^T Hf(\mathbf{y_0})(\mathbf{y}-\mathbf{y_0})$.

If $\mathbf{y_0}$ is the point where the function is minimum then $f(\mathbf{y_0})$ is the value of this minimum (it's the minimum itself). Which means that the function $f(\mathbf{y})$ has to have values that are $>f(\mathbf{y_0})$ for this point $\mathbf{y_0}$ to be a minimum (by definition!).

In other words, the term (called quadratic form) $\frac{1}{2}(\mathbf{y}-\mathbf{y_0})^T Hf(\mathbf{y_0})(\mathbf{y}-\mathbf{y_0})$ has to be $>0$. And this is exactly what it means for $Hf(\mathbf{y_0})$ to be positive definite (i.e. its quadratic form is positive).

Now for your function, $f(\mathbf{y})=\mathbf{y}^TX^TX\mathbf{y}$. Its Hessian is equal to $2X^TX$ (because $X^TX$ is symmetric, you can check this!)

This means that for the Hessian to be positive definite, $X^TX$ has to be positive definite, and for $X^TX$ to be positive definite your function (which is also a quadratic form) has to be positive.

Conclusion:

• For your question "Prove that $\mathbf{y}^TX^TX\mathbf{y}$ achieves minimum value when its matrix of second derivative is a positive definite matrix". The answer is that this holds for all multi-variable functions not only this one.
• For the Hessian of your function to be positive definite at the critical point, your function itself has to be positive at that point.

If it's second derivative is positive definite, $X^TX$ is positive definite.

$y^TX^TXy > 0, \forall y \neq 0$

Choose $y=0$ to show that the minimum can be attained.

• positive definite implies that $y^TX^TXy > 0, \forall y$ Thus $y = 0$ doesn't necessarily give us the minimum value. Commented Oct 12, 2016 at 21:06
• hmmm, what values are $y$ allowed to take? Commented Oct 12, 2016 at 21:07
• $y$ is a non zero column vector of $n$ real numbers Commented Oct 12, 2016 at 21:07
• Let $n=1$, and say, $X=1$. we see a problem if we exclude $0$ right? as the minimal can't be attained. Commented Oct 12, 2016 at 21:09
• Yes that is true. I misunderstood. The condition I gave above is the values $y$ can take in the definition of a positive definite matrix. For the purposes of this question it can be any real vector. Commented Oct 12, 2016 at 21:14

Let $X_{n\times p}$ and $y\in \mathbb{R}^p$. So your minimization problem is $\min_{y\in \mathbb{R}^p}||Xy||^2_2$. As such, $$||Xy||_2^2=y'X'Xy,$$ derivation w.r.t $y$ gives you the gradient of this quadratic form, i.e., the critical point is $$2X'Xy=0.$$ You get a homogeneous system of equation that has a unique trivial soluation iff $X'X$ is a full rank matrix. Thus, let $b\neq 0, b\in \mathbb{R}^p$, thus $b'X'=c, c\in \mathbb{R}^n$, hence $$b'X'Xb=c'c=\sum_{i=1}^nc_i^2\ge0.$$ I.e., $X'X$ is positive semi-definite and if $X'X$ is a full rank matrix then it is strictly positive definite.

That is, $y'X'Xy$ attains its minimum if the Hessian, $X'X$, is strictly positive definite matrix.

• But that is the point. I need to prove that when the minimum is attained $X^tX$ is necessarily strictly positive definite. Commented Oct 12, 2016 at 21:17
• I've edited my answer. Hope it helps. Commented Oct 12, 2016 at 21:46
• A little thing: square is lacking on your first formula. Commented Oct 12, 2016 at 22:40