8
$\begingroup$

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?

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

1 Answer 1

7
$\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$
7
  • 1
    $\begingroup$ @Fat32, Thank you for fixing the Typo. $\endgroup$
    – Royi
    Aug 27, 2018 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, 2018 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, 2018 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, 2018 at 17:23
  • 1
    $\begingroup$ 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... $\endgroup$
    – Fat32
    Aug 27, 2018 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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