3
$\begingroup$

suppose

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

then, how do i prove it is separable.

$\endgroup$
5
$\begingroup$

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.

In your case:

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.

$\endgroup$
  • 1
    $\begingroup$ @Fat32, Thank you for fixing the Typo. $\endgroup$ – Royi Aug 27 '18 at 13:15
  • $\begingroup$ 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. $\endgroup$ – Fat32 Aug 27 '18 at 13:54
  • $\begingroup$ @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. $\endgroup$ – Royi Aug 27 '18 at 14:36
  • $\begingroup$ 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... $\endgroup$ – Fat32 Aug 27 '18 at 17:23
  • $\begingroup$ @Fat32, On the contrary. In Image processing you don't want to do 3 passes. You use those variables (You can watch MATLAB's imfilter(). In Linear Algebra you usually leave at the form of the SVD decomposition in order ot keep $ u $ and $ v $ part of orthonormal basis. $\endgroup$ – Royi Aug 27 '18 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.