QR factorization: How to get decreasing r_ii

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Hi, I'm attempting to implement a QR factorization with column pivoting so that the returned R matrix has decreasing diagonal elements (that is, $r_{i,i} \leq r_{i-1,i-1}$ for all $i\geq 2$). Mathematically, it would involve finding the matrix $P$ so that $AP=QR$, or $A=QRP^T$. I'm using Gram-Schmidt to compute QR.

One source I found was this: http://www.mathworks.de/matlabcentral/newsreader/view_thread/250632

Quote from the answer: "During the iteration #k, it is easy to show that if we pick among the set of remaining vectors (i.e., not yet included in the span) the vector that has the largest orthogonal component to the current subspace (generated by k first vectors), then the diagonal of R must decrease."

Sounds simple enough, but HOW do I determine which vector of the remaining ones that have the largest orthogonal component to the subspace that's already been found?

Thanks a lot in advance for any help on this matter!

Best regards Hallgeir

-

3
Is there any reason why you prefer Gram-Schmidt (you're using the modified version I hope, classical Gram-schmidt has piss-poor numerical stability) over using Householder reflections? – J. M. Oct 25 2010 at 4:28

2
Seconded. Also, check if you can link to the relevant LAPACK subroutine (netlib.org/lapack/lug/node42.html) instead of coding it from scratch. – Federico Poloni Oct 25 2010 at 9:19
Hi, these are reasonable points of course, but the whole point was to learn how to actually implement it. And I do indeed use the modified version. :) I learn better by doing, and as such I find that implementing the algorithm is a useful way of achieving that. – Hallgeir Oct 26 2010 at 5:31

1 Answer

At each step $k$, choose the column of the "reduced" working matrix $A(k:n,k:n)$ with largest Euclidean norm and bring it in front with a permutation. Notice that $r_{11}$ is the Euclidean norm of the first column...

-

A little late reply from me (seems the email notification came quite late), but thank you very much! :) Seems to work perfectly! – Hallgeir Oct 26 2010 at 5:34
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 8, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9279897809028625, "perplexity_flag": "middle"}