MATLAB: Improving the speed!

for loopinitial value that satisfies some constraintsmatrixspeedtakes forever

Hey MATLAB guys,

Could someone please tell me how I can improve this code. It works pretty quick for nt_L=1:3. But, as nt_L increases, it takes forever. Any idea would be greatly appreciated.

    K = 10;
    nbrOfSubCarriers = 2*ones(1, K);
    nt_L = 10;
    nr_L = 3*ones(1, nt_L);    
    ulim_c = 1;    % max value of each element
    llim_c = 0;    % min value of each element
    sumlim_c = 1;    
    c0 = zeros(max(nr_L(:)), numel(nr_L), numel(nbrOfSubCarriers), max(nbrOfSubCarriers(:)));
    for k = 1 : K
        for m = 1 : nbrOfSubCarriers(k)
            RMat = rand(max(nr_L(:)), numel(nr_L))*(ulim_c-llim_c) + llim_c;
            Rsum = sum(RMat(:));
            Rcheck = Rsum > sumlim_c;
            while any(Rcheck)
                RMat = rand(max(nr_L(:)), numel(nr_L))*(ulim_c-llim_c) + llim_c;
                Rsum = sum(RMat(:));
                Rcheck = Rsum > sumlim_c;
            end
            if Rsum <= sumlim_c
                c0(:,:,k,m) = RMat;
            else
                c0(:,:,k,m) = RMat ./ Rsum;  %makes the sum exactly 1
            end
        end
    end

Best Answer

I love this kind of problems. First of all, Matlab comes with a debugger that tell you in which part you are losing your time (It's called Run and Time). After running it, it says that the while loop is really slow, so you have to search one way to make the condition succesful in the first attemp. I have try a solution with some other modifications like the if condition which is achieve by the while.

tic
K = 10;
mult_nbrOfSubCarriers = 2;
nbrOfSubCarriers = mult_nbrOfSubCarriers*ones(1, K);
nt_L = 10;
nr_L = 3*ones(1, nt_L);
ulim_c = 1;    % max value of each element
llim_c = 0;    % min value of each element
sumlim_c = 1;
max_nr_L = max(nr_L(:));
numel_nr_L = numel(nr_L);
c0 = zeros(max_nr_L, numel_nr_L, K, mult_nbrOfSubCarriers);
sumlim_c2 = (sumlim_c - llim_c)/(ulim_c-llim_c);
for k = 1 : K
    for m = 1 : nbrOfSubCarriers(k)
        RMat = rand(max_nr_L, numel_nr_L);
        sum_RMat = sum(RMat(:));
        if sum_RMat > sumlim_c2
            RMat = RMat./sum_RMat.*sumlim_c2;
        end
        c0(:,:,k,m) = RMat.*(ulim_c-llim_c) + llim_c;
    end
end
toc

Related Solutions

MATLAB: Creating random vector with 10 different lengths

You need to tell it either one row or one column. Try this:

inc = [10000, 20000 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000];
maxValue = 100000; % Whatever you want the potential max value in the vector to be.
for k = 1 : length(inc) % Creating a loop to go through the 10 values of inc
	% Generating random vector from 1-respective value of inc.
	vec1 = randi(maxValue, 1, inc(k)); % or randi(maxValue, inc(k), 1);
	fprintf('Made a vector with %d rows and %d columns.\n', size(vec1, 1), size(vec1, 2));
end

MATLAB: Sum of a 4D matrix

The problem is a relatively easy one, as long as the total sum does not exceed 1. It gets nasty above that.

I'll look at the problem in TWO dimensions, that is, imagine I want to find random numbers that lie within the unit square [0,1]X[0,1], such that the sum, x1 + x2 does not exceed 1.

The set of viable solutions lies within a triangle, the triangle with vertices [0, 0], [0,1], and [1,0]. So an isosceles triangle, with legs of length 1.

This is a different problem than what randfixedsum solves, in a subtle way. It solves the problem where the sum is constrained to be exactly 1. So you cannot use randfixedsum directly. (Though you CAN use it, with a subtle tweak, as long as the maximum on the sum does not exceed 1. That upper limit is important.)

Your admissable set is shown in the figure:

fill([0 0 1 0],[0 1 0 0],'r')

We want to see that the 2-d case is just a simple variation of the n-d case. In n-dimensions, 3 for example, the admissable set becomes an isosceles tetrahedron, so a 3-simplex with legs connecting the four points [0,0,0], [0,0,1], [0,1,0], and [1,0,0]. The number of dimensions is just the number of total elements in your vectors. So, if your vector is of length 100, then the points live in a 100 dimensional space. And then the admissable set will live in a 100-simplex, composed of 101 vertices. Hard to visualize, but a basic extension of the red triangle.

So that is your goal. Again, randfixedsum does not solve that specific problem. But it is close, in a sense.

How can we solve your problem? The idea is we can start with a set that sums to 1. Then take a nonlinear combination of those points with the point at the origin. And since the origin is at zero, it is simple. In two-dimensions, this reduces to:

ndim = 2;
nsample = 10000;
S = randfixedsum(ndim,nsample,1,0,1);
p = rand(1,nsample).^(1/ndim);
S = S.*p;
plot(S(1,:),S(2,:),'.')

Note that this will fail miserably if the maximum sum is greater than 1.

Be careful now. Because the first thing you might do is look at the distribution of the sum of those numbers. Even in the 2-dimensional case, the expected median value for the sum will be

1/sqrt(2)
ans =
      0.70711

But in 100 dimensions, the median of the sums will be quite close to 1.

ndim = 100;
nsample = 10000;
S = randfixedsum(ndim,nsample,1,0,1);
p = rand(1,nsample).^(1/ndim);
S = S.*p;
median(sum(S,1))
ans =
      0.99305

These points are still uniformly distributed in theory in the domain in question. But you need to understand that the probability of finding a point inside the isosceles 100-hypersimplex with leg length 0.5 is VERY small. That would be:

1/2^100
ans =
   7.8886e-31

In fact, what is the the probability of finding a point in that uniformly distributed simplex, such that NONE of the variables x1,...,x100 exceed 0.99?

(0.99)^100
ans =
      0.36603

That happens only about 37% of the time.

So don't compute the sum of the samples, and be surprised or disappointed. It will get even worse in a much higher number of dimensions.

Oh, and again, things go to hell if that sum exceeds 1, because then the domain that contains the points is not a single hyper simplex, but much more complex.

Best Answer

Related Solutions

MATLAB: Creating random vector with 10 different lengths

MATLAB: Sum of a 4D matrix

Related Question