Decompose a 2D arbitrary transform into only scaling and rotation

Question

Related to: Newly Developed With Details - Describing orthographic projection using simple 2D transformations

Given an arbitrary 2D linear transform (which may include shear, i.e. the vectors or the basis may not form a straight angle), it is possible to decompose it into transforms that are only horizontal/vertical scaling (i.e. matrices of the form $\pmatrix{s_x&0\\0&s_y}$) and pure rotation (i.e. matrices of the form $\pmatrix{\cos \theta&-\sin\theta\\\sin\theta&\cos\theta}$).

The minimal number of steps to do so is probably 3:

1. Rotate it so that the next scaling step will give it the correct shape.
2. Scale it to give it the proper shape.
3. Rotate it into the final position.

In other words, it seems to be always possible to find parameters $\theta, s_x, s_y, \phi$ such that:

$$M = \pmatrix{m_{00}&m_{01}\\m_{10}&m_{11}} = \pmatrix{\cos\phi&-\sin\phi\\\sin\phi&\cos\phi} \pmatrix{s_x&0\\0&s_y} \pmatrix{\cos\theta&-\sin\theta\\\sin\theta&\cos\theta}$$

I don't know if it's always possible to do so. I have the hunch that it is. I could not figure out how; I got a big system of nonlinear equations when I tried by myself. That decomposition has 4 d.o.f. as does the original linear transform, which hints that if it's correct, then it's minimal (you can't do it with 2 rotations or 2 scalings, and you don't have enough d.o.f. with 1 rotation + 1 scaling).

I tried with Inkscape and trial and error, and I could not find any rhomboid I couldn't transform into a square, but I might have not tried hard enough.

My questions:

1. Is that decomposition always possible? Already answered by Rahul in a comment (thanks!): it's called Singular Value Decomposition)
2. If so, how to calculate $\theta, s_x, s_y, \phi$?
3. If not, how can it be done in the least number of steps? (Mooted by the answer to question 1).
4. (New question) I found a solution with 4 (sometimes 5) steps, posted in the linked question but it was somewhat convoluted. However, the SVD seems to be complex to calculate. Should I just go with my 4-5 step solution, or is there a simple enough way to perform the decomposition? I've found this answer: https://scicomp.stackexchange.com/questions/8899/robust-algorithm-for-2x2-svd but it looked kind of overkill and I don't understand how to use the code for this case. I also didn't understand how to use the analytical result for the 2x2 case from the Wikipedia page, so if it's easier, an explanation on using it would help too.

Answer 1

Jim Blinn gives a direct computation of the singular value decomposition for the $2\times 2$ case in his article "Consider the lowly $2\times 2$ matrix", which I summarize below:

We want the decomposition $$\begin{bmatrix}A&B\\C&D\end{bmatrix}=\begin{bmatrix}\cos\beta&\sin\beta\\-\sin\beta&\cos\beta\end{bmatrix}\begin{bmatrix}w_1&0\\0&w_2\end{bmatrix}\begin{bmatrix}\cos\gamma&\sin\gamma\\-\sin\gamma&\cos\gamma\end{bmatrix}.$$ Define $E$, $F$, $G$, and $H$ so that $$\begin{bmatrix}A&B\\C&D\end{bmatrix}=\begin{bmatrix}E&H\\-H&E\end{bmatrix}+\begin{bmatrix}F&G\\G&-F\end{bmatrix}.$$ Then $$\begin{align} \frac{w_1+w_2}2&=\sqrt{E^2+H^2},\\ \frac{w_1-w_2}2&=\sqrt{F^2+G^2},\\ \gamma-\beta&=\tan^{-1}(G/F), \\ \gamma+\beta&=\tan^{-1}(H/E). \\ \end{align}$$

As Blinn says, "You can take it from here."