Rules of image's separability

Question

We know separable convolution helps reduce number of calculations during convolution operation. As usual we see this separability is being applied on convolution kernels. Can't we apply this separability to images as well? If we can do that, therefore, it would be a mathematically valid operation and the total number of calculations will be massively reduced. But it is unfortunate that not all 2D matrices are separable to make 1Ds. So what are the rules for a matrix to be separable and is there any mathematical formulation for that to find the separated form?

Answer 1

A separable image $I$ that could be written in a separable way with vectors $a$ and $b$ as:

$$ I= a^Tb$$

would necessarily be of rank one at most. Either a zero-matrix (rank 0), or with only one linearly independent row or column. This are rather dull images alone. But this could be a model for a slowly varying background, some people use that for background source separation in image sequences. The following images are such images, generated the following way. $a$ and $b$ are uniform random sequences, $a_s$ is $a$ with sorted values, and $b_s$ is the cumulative sum of vector $b$:

However, splitting an image in a weighted sum of rank-one matrices is at play in SVD decomposition. Finding low-rank approximations to matrices is a very current problem, and depends a lot on "how close is the approximation" (ie: with what norm?).

• Wikipedia: Low-rank approximation
• Bart Wronski: Separate your filters! Separability, SVD and low-rank approximation of 2D image processing filters