Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$Q$ is a rectangular matrix with orthonormal columns. A linear system composed of $$Qx= b$$ is really easy to solve as:

$$Q'Q=I$$ hence: $$x=Q'b$$

Given that $Q$ is orthonormal can this be used to solve a weighted linear regression problem efficiently? The normal equation for this system is:


$W_i$ is a diagonal matrix with only positive entries along the ridge. For each different $W_i$ I do a Cholesky factorization of the normal equation with the associated cost $O(n^3)$. Are there methods that would do better.

For some back ground reading: Iteratively reweighted least squares

share|cite|improve this question
Are you sure that your weighted normal equations are correct? The inverses for $Q'$, $Q$ and $W_i$ are simply $Q$, $Q'$ and $W_i^{-1}$ (putting the inverses on the diagonal), respectively and hence, the solution would be $x=Q'b$... – Dirk Feb 11 '13 at 10:31
I think they are right but I could be making a basic error. I used your comment to set the normal equation up as $x=Q'W^{-1}QQ'Wb$. $QQ'$ is not $I$ as only the columns are orthonormal. Will appreciate if you can confirm that this makes sense. Thanks. – Atlas Feb 11 '13 at 12:15
What are the dimensions of $Q$? Best (for the answer I may have) would be if it has one less column from square, $n \times (n-1)$, as in that case a rank one update could be done to go from solution for $Q$ to that for $WQ$. – adam W Feb 11 '13 at 17:24
$Q$ is an $m \times n$ matrix with $m>>n$. – Atlas Feb 11 '13 at 18:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.