3
$\begingroup$

Given regularized-least squares

$$\min_x ||Ax - b||^2+ \lambda||x||^2 $$

How do you use QR decomposition to find a solution?

I understand that QR decomposition leads to $Rx = Q^Tb$, but how do you incorporate $\lambda||x||^2$?

Following the suggestions and solutions I have: $$ \begin{align} (Ax-b)^T(Ax-b) + \lambda x^Tx &= x^T(A^TA+\lambda I)x - 2b^TAx+b^Tb \\ (take \ derivative) &= 2(A^TA+\lambda I)x - 2A^Tb = 0 \\ &= (A^TA+\lambda I)x = A^Tb \\ &= ((QR)^TQR + \lambda I)x = (QR)^Tb \\ &= (R^TR + \lambda I)x = R^TQ^Tb\\ &= x = (R^TR+ \lambda I)^{-1} R^TQ^Tb \\ \end{align}$$

$\endgroup$
5
  • $\begingroup$ Hint: rewrite the objective to $x^T C x + d^Tx + e$. $\endgroup$
    – LinAlg
    Nov 14, 2016 at 14:41
  • $\begingroup$ Can you hint what $e$, $C$, and $d$ are? $\endgroup$
    – h94
    Nov 15, 2016 at 1:03
  • $\begingroup$ Write $||Ax-b||^2$ as $(Ax-b)^T(Ax-b)$, and $||x||$ as $x^T I x$. $\endgroup$
    – LinAlg
    Nov 15, 2016 at 9:30
  • $\begingroup$ Then would you get the express: $(QRx-b)^T(QRx-b) + \lambda x^TIx$and minimize that? $\endgroup$
    – h94
    Nov 15, 2016 at 19:03
  • $\begingroup$ I've updated the question to show some of my work. $\endgroup$
    – h94
    Nov 15, 2016 at 19:36

1 Answer 1

Reset to default
0
$\begingroup$

Note that the objective is $(Ax-b)^T(Ax-b)+ \lambda x^T x = x^T (A^T A +\lambda I) x - 2 b^T Ax + b^Tb$. Taking the derivative yields $2(A^TA+\lambda I)x - 2 A^Tb = 0$, or $(A^TA+\lambda I)x = A^Tb$. Hence $x=(A^TA+\lambda I)^{-1}A^Tb$. The trick is now to take a QR decomposition of $A^TA+\lambda I$ (instead of just $A^TA$), so you can write $x=R^{-1}Q^TA^Tb$.

$\endgroup$
6
  • $\begingroup$ @LutzL thanks, I updated my answer. $\endgroup$
    – LinAlg
    Nov 15, 2016 at 23:42
  • 1
    $\begingroup$ Numerically, one wants to avoid computing $A^TA$ as that squares the condition number. Use $A=QR$ to reduce to $(R^TR+λI)x = y=R^TQ^Tb$ where now in the lower part $x_k=λ^{-1}y_k$ and only the upper part where $R^TR$ is non-trivial needs to be solved. $\endgroup$
    – Lutz Lehmann
    Nov 15, 2016 at 23:56
  • $\begingroup$ wouldn't the answer at the end be $x = (R^TR+\lambda I)^{-1}R^TQ^Tb $? $\endgroup$
    – h94
    Nov 16, 2016 at 4:39
  • $\begingroup$ I'm a little confused as to how $\lambda$ disappears in the solution. $\endgroup$
    – h94
    Nov 16, 2016 at 4:43
  • $\begingroup$ I've updated the question $\endgroup$
    – h94
    Nov 16, 2016 at 4:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .