In a Machine Learning course, we had the followin theorem:

Theorem 3.6: Let $A\in\mathbb R^{m\times n}$, $b\in \mathbb R^{m}$, $C\in \mathbb R^{p\times n}$ have independent rows and $d\in \text{im}\left(C\right)\subset\mathbb R^{p}$. Consider the minimization problem $$\min_{x\in\mathbb R^{n}}\left\vert\left\vert Ax-b\right\vert\right\vert_{2}^{2}\qquad \text{s.t.} \quad Cx = d. \qquad\qquad (1)$$

A vector $\hat{x}\in\mathbb R^{n}$ solves $(1)$ if and only if there exists $z\in\mathbb R^{p}$ s.t.

$$\begin{pmatrix} A^{T}A & C^{T} \\ C & 0 \end{pmatrix}\begin{pmatrix} \hat{x} \\ z \end{pmatrix} = \begin{pmatrix} A^{T}b \\ d \end{pmatrix}. \qquad\qquad (2)$$

As a homework, we're supposed to prove it. I already tried it myself, and I think I got "$\Rightarrow$" with the help of Lagrange multipliers.

Concerning the other direction "$\Leftarrow$": I am not relly sure how to get started, could anybody please provide a hint?

  • $\begingroup$ Can you please show your calculations for the $\implies$ part ? $\endgroup$
    – JRC
    Commented May 4, 2021 at 5:09
  • $\begingroup$ Sure, I could do this! But may I ask: Why are you interested in the "$\Rightarrow$" part, my question is about the "$\Leftarrow$" part. $\endgroup$
    – Hermi
    Commented May 4, 2021 at 7:44
  • $\begingroup$ I think we need specify that $p<n$ $\endgroup$
    – framago
    Commented May 4, 2021 at 13:53
  • $\begingroup$ That could very well be.. I re-checked our lecture notes, and it doesn't say sothere, but I guess it would be much easier to judge if I had a proof upon which I could judge. :) $\endgroup$
    – Hermi
    Commented May 4, 2021 at 18:02


You must log in to answer this question.