# How to Check Separability of 2D Filter / Signal / Matrix

Given:

    x(n1,n2) = {1 ,n1=0,n2=0 ;
2 ,n1=1,n2=0 ;
3 ,n1=0,n2=1 ;
6 ,n1=1,n2=1 }


How could one prove it is separable?

• By separable, do you mean $x(n1,n2)=x1(n1)x2(n2)$ ?
– user28715
Aug 26, 2018 at 7:17
• If so, the matrix will be rank 1. you can also have $x(n1,n2)=g(\sqrt{x1^2+x2^2})$
– user28715
Aug 26, 2018 at 8:36
• For integer case - dsp.stackexchange.com/questions/1868/….
– Royi
Aug 27, 2018 at 13:18
• Related to dsp.stackexchange.com/questions/35190.
– Royi
Nov 25, 2020 at 16:15

Nilesh Padhi, Welcome to the DSP Community.

The classic definition of separable means the data (2D) given by $X \in \mathbb{R}^{m \times n}$ can be written as:

$$X = \sigma u {v}^{T}$$

Where $\sigma \in \mathbb{R}$, $u \in \mathbb{R}^{m}$ and $v \in \mathbb{R}^{n}$.
This is called Rank 1 Matrix.

How can you get those parameters and vectors given $X$?
Well, the Singular Value Decomposition (SVD) is here to save the data.

The SVD of $X$ is given by:

$$X = U \Sigma {V}^{T} = \sum {\sigma}_{i} {u}_{i} {v}_{i}^{T}$$

You can see those match when ${\sigma}_{j} = 0$ for $j \geq 2$.
So what you should do is the following:

epsThr = 1e-7;
[mU, mD, mV] = svd(mX);
vD = diag(mD);
if(all(vD(2:end) < epsThr))
vU = mU(:, 1);
vV = mV(:, 1);
end


We checked if indeed the singular value of 2 and onward are small.
If they do (You can decide to what degree of small by epsThr) then it is separable and the vectors are vU and vV.

mX = [1, 3; 2, 6];
[mU, mD, mV] = svd(mX);

vD = diag(mD);
disp(vD);


The result is:

vD =

7.0711
0.0000


Since vD values are zero besides the first element (Only single non vanishing Singular Value) it is separable.

Indeed you can see that:

mD(1) * mU(:, 1) * mV(:, 1).'

ans =

1.0000    3.0000
2.0000    6.0000


As expected.

This method is really useful in Image Processing when we want to convolve with 2D kernel and we find it is separable and hence we can apply the 2D convolution using 2 1D convolutions (Along Columns / Rows).

In that case we define $\hat{u} = \sqrt{{\sigma}_{1}} u$ and $\hat{v} = \sqrt{{\sigma}_{1}} v$ where ${\sigma}_{1}$ is the Singular Value.
Then we convolve $\hat{u}$ along columns and $\hat{v}^{T}$ along rows.

• @Fat32, Thank you for fixing the Typo.
– Royi
Aug 27, 2018 at 13:15
• Very nice answer indeed. Note that there's a slight mismatch between the actual components, u ,v for $h = u \cdot v'$ and their computed counterparts hu,hv if computed from $hu = \sqrt{D(1)} mU$ and $hv = \sqrt{D(1)} mV$ (But the mismatch is cancelled through the row-column convolutions and yields a very accurate result. Yet if individual components are used for some other purposes, the slight mismatch shall be considered for accuracy sensitive applications. Aug 27, 2018 at 13:54
• @Fat32, Well, for Convolution usually we do as you wrote and multiply $u$ and $v$ by the square root of the Singular Value. I will add that.
– Royi
Aug 27, 2018 at 14:36
• hmm, either I stated it not very clear, or you misunderstood. If you will eventually perform the 2D conolution (in the separation manner) then do not compute hu and hv. Just use the first columns of U and V matrices and multiply the result by $\sigma_1$. Because the former would introduce more errors than the latter. If you, on the other hand, want to use the individual 1D filters for some other reasons, then the multiplication by $\sqrt{\sigma_1}$ is required... Aug 27, 2018 at 17:23
• you don't have to do 3 passes if you are so much into efficiency. You can merge that $\sigma_1$ into juts one of those 1D filters and perform just two passes ;-) And it will be more accurate and more efficient than merging $\sqrt{\sigma_1}$ into both filters and doing 2 passes... Aug 27, 2018 at 19:07