How to Prove a 2D Filter Is Separable?

Question

I want to prove that 2D Gaussian filter is separable and we can separate it into two dimensions, my problem is about the size of filters. we should prove that $G(x,y)*I$(where $G(x,y)=$$\begin{bmatrix}0.01 & 0.1 & 0.01 \\0.1 & 1 & 0.1 \\ 0.01 & 0.1 & 0.01\end{bmatrix}$,I is image and $*$ is convolution operator) is equal to $G(x)*I*G(y)$ where $G(x)=$$\begin{bmatrix}0.1 & 1 & 0.1 \end{bmatrix}$ $,G(y)=$$\begin{bmatrix}0.1\\1\\ 0.1\end{bmatrix}$ and I is image. in other words we should prove that $G(x,y)=G(x)*G(y)$ but I don't know how to convolve these filters with different sizes.

Answer 1

Let's have a different perspective on that.

Let's say our 2D Linear Operator is given by the Matrix $ G \in {\mathbb{R}}^{n \times n} $.
Using the SVD Decomposition the operator can be written as:

$$ G = \sum_{i = 1}^{n} {\sigma}_{i} {u}_{i} {v}_{i}^{T} $$

Separable Linear 2D Operator is defined as operator which can be composed by Outer Product of 2 vectors.
Looking at the SVD Decomposition of $ G $ we can conclude that $ G $ is separable operator if and only if $ \forall i > 1 \; {\sigma}_{i} = 0 $ and it is given by:

$$ G = {\sigma}_{1} {u}_{1} {v}_{1}^{T} $$

Usually LPF 2D Linear Operators, such as the Gaussian Filter, in the Image Processing world are normalized to have sum of 1 (Keep DC) which suggests $ {\sigma}_{1} = 1 $ moreover, they are also symmetric and hence $ {u}_{1} = {v}_{1} $ (If you want, in those cases, it means you can use the Eigen Value Decomposition instead of the SVD).

So basically, to prove that a Linear 2D Operator is Separable you must show that it has only 1 non vanishing singular value.

Note: I was not rigorous in the claims moving form general SVD to the Eigen Decomposition yet the intuition holds for most 2D LPF operators in the Image Processing world.

Answer 2

Given that $G(x)$ is a row vector, while $G(y)$ is a column one, their convolution will be identical to the matrix product $G(x,y)=G(x)*G(y)=G(x)G(y)$. For this reason, as soon as $G(x,y)$ is rank-1, the convolution kernel can be separated (decomposed into two 1-D filters). This is because the other columns of the matrix could be written as a linear combination of the elements of the first.

So to prove that a kernel is separable, just check the rank:

s = svd(G);
sum(s > eps('single'))