For some λ ≥ 0, suppose that we have two lasso solutions β hat, γ hat with common optimal value c*. I need to show that it must be the case that Xβ = Xγ meaning that the two solutions must yield the same predicted values. does any body knows the answer for this question or could give direction for how can i solve it?
i tried everything. thank's!
We prove a more generalized version of your question below. For LASSO, you have $f(x)=\|x\|_2^2$ and $h(x)=\lambda \|x\|_1$ with $\lambda\ge 0$. Also, note that the solution set of a convex program is convex. For your case, we can let $S$ in the following lemma to be the solution set of the LASSO problem.
$\textbf{Lemma}$. Let $f:\mathbb R^m \rightarrow \mathbb R$ be a strictly convex function, and $h:\mathbb R^N \rightarrow \mathbb R$ be a convex function. If $f(Ax -y) + h(x)$ is constant on a convex set $S \subseteq \mathbb R^N$, then $Ax=A z$ and $h(x)=h(z)$ for all $x, z\in S$.
$\textbf{Proof}$. Let $x$ and $z$ be in $S$ for which $Ax\ne Az$. Suppose $f(Ax-y)+h(x)=f(Az-y)+h(z)=c$. For $\lambda \in (0,1)$, we have $\lambda x+(1-\lambda z)\in S$ and $f(A[\lambda x+(1-\lambda) z]-y)+h(\lambda x+(1-\lambda) z)=c$. But, we have \begin{equation} \begin{split} c & = f(A[\lambda x+(1-\lambda) z]-y)+h(\lambda x+(1-\lambda) z) \\ & = f(\lambda [Ax-y]+(1-\lambda) [Az-y])+h(\lambda x+(1-\lambda) z) \\ & < \lambda f(Ax-y) +(1-\lambda)f(Az-y)+h(\lambda x+(1-\lambda) z) \quad \text{(strict convexity of $f$) }\\ & \le \lambda f(Ax-y) +(1-\lambda)f(Az-y)+\lambda h(x)+(1-\lambda) h(z) \quad \text{(convexity of $h$)}\\ & = \lambda [f(Ax-y)+h(x)]+(1-\lambda) [h(z)+f(Az-y)] \\ & \lambda c+(1-\lambda)c\\ & = c. \end{split} \end{equation} The above gives a contradiction so that we must have $Ax=Az$. As a result, we can simply show that $h(x)=h(z)$ as well.