Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

$$Q'W_iQx=Q'W_ib$$

$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|improve this question
1  
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

 
discard

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

Browse other questions tagged or ask your own question.