Projection Matrix derivation to constrained optimization problem with Lagrange multiplier

Question

I am trying to derive famous Projection operator as a constrained minimization problem for the least square problem. The question is as follows:

Find $x$ minimizing $ (y-x)^T(y-x)$ subject to $x = H\theta$ where $y$, $x$ and $\theta$ are vectors and $H$ are matrix. How can I solve this problem with Lagrange multiplier?

The solution to the problem will be of the form $\hat{x} = Py$ where $P = H(H^TH)^{-1}H^T$ is the classical projection matrix on $H$.

This problem is classical least square estimation. Unconstrained form of this question is follows:

Find $\theta$ minimizing $ (y-H\theta)^T(y-H\theta)$. This is easily found by takind gradient and setting equal to zero. Or by using vector space approach it can easily be shown that the error ($y-H\hat{\theta}$) will be orthogonal to the columns of $H$ or the basis vectors of the subspace $H$.

But my question is I want to reach the well-known projection matrix with the help of Lagrange multiplier for the solution of constrained minimization problem as stated in the first equation.

If the constraint had the form $Cx = c$ instead of $x = H\theta$, it can be solved easily. But, I couldn't find the solution for this form of constraint $x = H\theta$.

Any help will be much appreciated.

Answer 1

You can't solve the problem in the way you intend to, because $x=H\theta$ is not a constraint in the usual sense. Note that $\theta$ is unknown and must be chosen such that $||y-x||$ is minimized. A constraint is given as $Ax=b$ with $A$ and $b$ fixed and known. If $\theta$ were known then there wouldn't be any minimization problem; the solution would just be $x=H\theta$.

So the only meaningful way to solve the problem is to replace $x$ by $H\theta$ in the objective function, minimize with respect to $\theta$, and then obtain the solution as $x=H\hat{\theta}$, where $\hat{\theta}$ is the solution of the minimization problem.

---

EDIT:

In order to be able to use Lagrange multipliers one needs to reformulate the constraint as $A^Tx=0$, where the column space of $A$ is the orthogonal complement of the column space of $H$, i.e., $A^TH=0$. Now the constraint is in the form mentioned above, i.e., a with constant matrix $A$ and a constant vector $b=0$.

The Lagrangian is

$$\mathcal{L}(x,\lambda)=x^Tx-2y^Tx+y^Ty+\lambda^TA^Tx$$

and solving in the usual way yields

$$x=\left[I-A(A^TA)^{-1}A^T\right]y$$

Now we need to recognize that $A(A^TA)^{-1}A^T=P_A$, and, consequently, $I-P_A=P_H$, i.e., $x=P_Hy$.

Answer 2

The usual way to apply Lagrange multipliers is to augment the cost function with an additional term that incorporates the constraints:

Instead of minimizing

$$ C = (y-x)^T(y-x)$$

minimize

$$ C' = (y-x)^T(y-x) + \lambda (x - H \theta) $$

But, as Matt L. says, this formulation doesn't make sense as the $x = H\theta$ isn't expressed the way a constraint is usually expressed.