Can someone explain me how we can compute RQ decomposition for a given matrix (say, $3 \times 4$). I know how to compute QR decomposition.

I know the function in MATLAB which computes this RQ decomposition. But, I want to know how we can do that on paper.

PS: The practical use of RQ decomposition is in extracting the intrinsic and extrinsic parameters of the camera when the camera matrix $P(3 \times 4$) is given

thanks!

up vote 9 down vote accepted

$\newcommand\iddots{\mathinner{ \kern1mu\raise1pt{.} \kern2mu\raise4pt{.} \kern2mu\raise7pt{\Rule{0pt}{7pt}{0pt}.} \kern1mu }}$

This concerns $RQ$ decompositions of square matrices.

Suppose you have a $n \times n$ matrix $A$ and want to compute the RQ decomposition. If you know how to compute QR decompositions, you will just need a few transpositions / row-column permutations.

Note that given the matrix $P := \begin{bmatrix} & & 1\\ & \iddots & \\ 1 & & \\ \end{bmatrix}$ (this is different to the camera matrix mentioned in the question), we get that $AP$ reverses the order of columns of $A$ and $PA$ reverses the order of rows. Also note that $P^T = P$ and $PP = E_n$, so $P^{-1} = P = P^T$, in particular $P$ is orthogonal.

Consider the following algorithm:

i.) Compute $\tilde A := PA$ (i.e. reverse rows of $A$)

ii.) Compute decomposition of $\tilde A ^T = \tilde Q \tilde R$

iii.) Set $Q := P \tilde Q^T$ (i.e. reverse rows of $\tilde Q^T$, note that $Q$ is orthogonal)

iv.) Set $R := P \tilde R^T P$

In step iv.) the following happens: $\tilde R$ is an upper triangular matrix. By transposing it, it becomes a lower triangular matrix. So we reverse rows and columns and obtain again an upper triangular matrix $R$. See sketch (start with lower triangular, reverse rows, then revere columns).

$$\begin{bmatrix} * & \cdot & \cdot \\ * & * & \cdot \\ * & * & * \end{bmatrix} \to \begin{bmatrix} * & * & * \\ * & * & \cdot \\ * & \cdot & \cdot \end{bmatrix} \to \begin{bmatrix} * & * & * \\ \cdot & * & * \\ \cdot & \cdot & * \\ \end{bmatrix} $$

Altogether $R$ and $Q$ yields our decomposition:

$$RQ = (P \tilde R^T P)(P \tilde Q^T) = P \tilde R^T \tilde Q^T = P(\tilde Q \tilde R)^T = P(\tilde A ^T)^T = P \tilde A = PPA = A$$

  • Copied as Comment by @NicholasCasale: From this link, and working through a RQ decomposition for an image projection, it seems that the accepted answer needs a left-to-right flip on R for it to be upper triangular. (MATLAB's fliplr(.)) – hardmath Feb 11 '17 at 6:04
  • You seem to be saying that $r(\tilde{R}^T)$ is upper triangular when $\tilde{R}$ is upper triangular. But although $\tilde{R}^T$ is surely lower triangular in this case, reversing the rows (which amounts to premultiplying by a particular permutation matrix $P$) does not produce an upper triangular matrix: $$\begin{bmatrix} * & \cdot & \cdot \\ * & * & \cdot \\ * & * & * \end{bmatrix} \to \begin{bmatrix} * & * & * \\ * & * & \cdot \\ * & \cdot & \cdot \end{bmatrix} $$ – hardmath Feb 11 '17 at 16:22
  • @hardmath Thanks, I refactored my post. It should be okay now. If you don't mind, please have a look and tell me if you see any more mistakes! – johnnycrab Feb 11 '17 at 21:00
  • At a glance you fixed it exactly as I would have. It might worth a caution that your permutation matrix $P$ differs from the "camera matrix" $P$ briefly mentioned in the Question. – hardmath Feb 11 '17 at 21:08
  • 1
    Ah, yes, didn't recognize there is also a $P$ in the question. Thanks again for all the effort! – johnnycrab Feb 11 '17 at 21:14

protected by Community Jul 3 at 13:12

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.