1
$\begingroup$

enter image description hereI 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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ Thank you for your answer. This is the usual way. In the Scharf's Statistical Signal Processing book on page 365 and 366, this issue is explained. Also, this is a problem appearing on page 415 (Problem 9.1). After giving the usual way as you suggested, the author say that LS problem can also be solved by following the constrained approach which is my question. You can consider the problem as follows: What would be best approximate of y if you force it lie on a subspace <H>? $\endgroup$ Jul 7 '21 at 12:34
  • $\begingroup$ @OsmanCoskun: Does it explicitly say to use Lagrange multipliers? I don't have the book here, so I can't check, but using $x=H\theta$, with variable $\theta$, is the obvious way to force the solution to lie in the subspace spanned by the columns of $H$. $\endgroup$
    – Matt L.
    Jul 7 '21 at 13:39
  • $\begingroup$ I attach the image of the original question above. My interpretation was to use Lagrange multiplier to solve this constrained minimization problem. $\endgroup$ Jul 7 '21 at 23:30
  • $\begingroup$ @OsmanCoskun: I'm still not sure if or how you can solve such a problem with Lagrange multipliers. The obvious way to take that constraint into account is to replace $x$ in the objective function by $H\theta$. Geometrically, the result is of course obvious: the best approximation is the projection of $y$ onto the space spanned by the columns of $H$. $\endgroup$
    – Matt L.
    Jul 8 '21 at 8:58
  • $\begingroup$ L: Thank you for your answer. I had tried some alternative forms of constraints as well, but I couldn't do it neither. My purpose was to derive it in a different way while I was reviewing the fundamental concepts with Scharf's book. If I can find something, I will write down the solution here. Thanks again. $\endgroup$ Jul 8 '21 at 9:12
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.