strict convexity of $\boldsymbol{\beta} \mapsto \| \mathbf{Y}-\mathbf{X}\boldsymbol{\beta}\|_2^2$ So I'm studying lasso regression using https://arxiv.org/pdf/1509.09169.pdf and on page 84 (the beginning of section 6.1) it is stated that $\boldsymbol{\beta} \mapsto \| \mathbf{Y}-\mathbf{X}\boldsymbol{\beta}\|_2^2$ (where $\mathbf{Y}$ is a $n\times 1$ vector, $\mathbf{X}$ is a $n\times p$ matrix and $\boldsymbol{\beta}$ is a $p\times 1$ vector ) is not strictly convex when we are the high dimensionality setting. That is when $p>n$. I'm not sure how this follows and could use some help.
 A: This analysis is intended to illuminate the basic underlying ideas.
Consider the system of linear equations
$$X\gamma = 0$$
where $\gamma$ is a column $p$ vector and $0$ is the zero $n$ vector.  When $p\gt n$ there are more equations $n$ than unknowns $p,$ whence there must be a nonzero solution $\gamma.$
Assuming there is a $\beta$ that minimizes the form $Q(\beta)= ||Y - X\beta||^2,$ this result about solving linear equations implies there are many minimizers of $Q$ because for any number $t,$
$$Y - X(\beta+t\gamma) = Y - (X\beta + X(t\gamma)) =Y-X\beta-t(X\gamma)= Y-X\beta - 0 = Y-X\beta$$
shows that $Q(\beta+t\gamma)=Q(\beta)$ also minimizes $Q.$  But that's not possible for a strictly convex form $Q$, because strict convexity would imply that
$$\begin{aligned}
\color{red}{Q(\beta)} &= Q(\beta+t\gamma)= Q((1-t)\beta+t(\beta+\gamma)) \\
&\color{red}\lt (1-t)Q(\beta) + tQ(\beta+\gamma) = (1-t)Q(\beta) + tQ(\beta) \\&= \color{red}{Q(\beta)},
\end{aligned}$$
a contradiction.

I leave it to you to prove (or believe) that any quadratic form $Q$ always has at least one minimizer.  That's the only fact we needed about $Q$ qua function of $Y-X\beta.$  Thus, this general result about non-strict convexity holds for any function of $Y-X\beta$ having at least one minimizer.  (This includes functions that are not differentiable or even continuous, cases where resorting to Calculus will not work.  In particular, the loss functions used in the Lasso and the Elastic Net are not everywhere differentiable, so this generality can be useful.)
A: First note that $$\frac{\partial^2 \| \mathbf{Y}-\mathbf{X}\boldsymbol{\beta}\|_2^2}{\partial \boldsymbol{\beta}\partial \boldsymbol{\beta}^T}=2\mathbf{X}^T\mathbf{X}.$$A function is strictly convex if the hessian is positive definite and convex if it is positive semidefinite. $\mathbf{X}^T\mathbf{X}$ is always positive semidefinite so $\boldsymbol{\beta} \mapsto \| \mathbf{Y}-\mathbf{X}\boldsymbol{\beta}\|_2^2$ is convex. However when $p>n$ $\mathbf{X}$ will not have full rank and since $\mathbf{X}^T\mathbf{X}$ is positive definite if and only if $\mathbf{X}$ has full rank we get that $\boldsymbol{\beta} \mapsto \| \mathbf{Y}-\mathbf{X}\boldsymbol{\beta}\|_2^2$ is only strictly convex when $n>p$ and thus convex when $p>n$.
