# QR factorization & Regularized Least Squares

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}

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

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

• @LutzL thanks, I updated my answer. Nov 15, 2016 at 23:42
• 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. Nov 15, 2016 at 23:56
• wouldn't the answer at the end be $x = (R^TR+\lambda I)^{-1}R^TQ^Tb$?
– h94
Nov 16, 2016 at 4:39
• I'm a little confused as to how $\lambda$ disappears in the solution.
– h94
Nov 16, 2016 at 4:43
• I've updated the question
– h94
Nov 16, 2016 at 4:55