# 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. ## 2 Answers 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} $$Seprable 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 worled 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 rigourous in the claims moving form general SVD to the Eigen Decomposotion 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'))