How to find out if a transform matrix is separable?

Question

In image processing, when we have a series of basis images, how could we know if the transformation is separable or not? For example, I know that following bases are separable and transformation can be done with matrix $A$, but I don't know how to find $A$ from $A_1$, $A_2$, $A_3$ or find separability. \begin{equation} A_1 = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} A_2 = \frac{1}{2}\begin{bmatrix} 1 & -1 \\ 1 & -1 \end{bmatrix} A_3 = \frac{1}{2}\begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix} \\ A = \frac{1}{\sqrt 2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \end{equation}

Answer 1

I admit I did not really thought about it before. I hope my notations won't be too sloppy.

I assume that given an operator matrix $A(u,v)$, you can apply this operator as a transform on an image $I$, to obtain an image in a novel domain $J(u,v)$. For instance a Fourier kernel would give $$a_{m,n}(u,v) = \exp^{-2\pi \imath \left(um/M+vn/N\right)}\,.$$

For each choice of a $(u,v)$ pair, you get a specific kernel, for instance a basis element.

The transform is separable, in the common sense, when you can write it as a element-wise product, for instance: $$a_{m,n}(u,v) = b_{m}(u) . c_{n}(v) $$ where $b(u)$ and $c(v)$ are 1D vectors: $$A(u,v) = b(u) . c^T(v)\,, $$ one acting on rows, the other on columns.

Thus, the vectors being of rank at most one (the rank of a matrix is lower than its minimum size), $A$ is at most of rank $1$ as well. I take it as sufficient condition. If I rule out uninteresting matrices and vectors of rank $0$, that should be a necessary condition. More details for instance at A rank-one matrix is the product of two vectors.

So:

• if $A$ is of rank $>1$, it does not appear to be separable (at least with this definition)
• if $A$ is of rank $1$, take a non-zero vector for the span, and then multiply it by appropriate coordinates to get the matrix back.

For $A_3$, the determinant is zero, so the matrix is rank $1$. You will get vector $[1 -1]^T$ in the image, and quickly:

$$2 A_3 = [1 -1]^T [1 -1]\,.$$

Note, the separation is not unique.