1

I have a code that does a 4 level decomposition of an image. The levels are similar to the Wavelet transform of an image that decomposes the image into 4 levels: The approximation part, and the three detailed parts. The code that I have implemented uses generalized SVD to do this decomposition. Here is the code

      function[Y,U] = MSVD1(X)
       %multiresolution SVD (MSVD)
        %input-> x: image (spatial domain)
        %outputs-> Y: one level MSVD decomposition of x
        %          U: the unitary matrix (U in SVD)
         [m,n] = size(X);
        m = m/2; n = n/2;
        A = zeros(4,m*n); 
        for j = 1:n
         for i = 1:m
           A(:,i + (j-1)*m) = reshape(X((i-1)*2+(1:2),(j-1)*2+(1:2)),4,1);
         end
        end
      [U,S] = svd(A);
       T = U'*A;
      Y.LL = reshape(T(1,:),m,n);
      Y.LH = reshape(T(2,:),m,n);
      Y.HL = reshape(T(3,:),m,n);
      Y.HH = reshape(T(4,:),m,n);
      end

Now the basic operations involved in this are using SVD. So my question is should the time complexity in terms of Big O notation be same as a normal SVD of a matrix? If not what should be the terms that we need to take into account find the complexity in terms of input size of an image? Does the reshaping elements also add account for the time complexity or is it just O(1)? Can somebody help?

user311790
  • 192
  • 10

1 Answers1

3

First, the complexity of the constant size reshape (inside the loop) is O(1). Hence, the complexity of the for loop is \Theta(m*n). Second, the complexity of svd is O(max(m, n) * min(m, n)) and based on what data will be returned by the function it can be O(max(m, n)^2) (according to this reference). Moreover, base on the @Daniel comment, the worst-case scenario for reshapes at the end of your code, can O(m*n) (it is usually less than this).

Therefore, the complexity of the code is O(max(m, n)^2). Also, because of the loop, it is Omega(m*n).

OmG
  • 18,337
  • 10
  • 57
  • 90