# How to Prove a 2D Filter Is Separable?

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.

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.

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'))