MATLAB Central Newsreader - Find Minimum Values of Matrix without MIN or For loops

Find Minimum Values of Matrix without MIN or For loops

Stephen Smitherman — Sun, 01 May 2011 02:39:04 +0000

I am reviewing for a test and my teacher loves to ask us questions that require the removal of explicit loops (FOR and WHILE) and use implicit (Array Operations) instead. For example instead of

for n=1:100
     b=sin(n);
end
b

instead use

n=1:100;
b=sin(n);
b

so the function we are to convert is as follows
A is an arbitrary predifined Matrix

clear,clc
for m=1:length(A(1,:));
    S(m)=A(1,m);
    for k=2:length(A(:,1));
         if(S(m)>A(k,m))
                S(m)=A(k,m);
         end
     end
end
S

Where S is a vector with the minimum value of each column.
I know this could be solved with Min(A), but that is not what is being ask. How would I use vectorization to make the same above operation to work?

Re: Find Minimum Values of Matrix without MIN or For loops

Roger Stafford — Sun, 01 May 2011 03:24:04 +0000

I don't think you can hope to eliminate both for-loops within the spirit of your assignment. If you replace the "if-end" construct with the appropriate logical vectors, however, you could accomplish the task with a single for-loop. End of hint.

Roger Stafford

Re: Find Minimum Values of Matrix without MIN or For loops

m4 Chrennikov — Sun, 01 May 2011 07:46:04 +0000

If I get it clearly, you are searching the minimum element in each column?
min(A)
can replace all code.

Re: Find Minimum Values of Matrix without MIN or For loops

m4 Chrennikov — Sun, 01 May 2011 07:54:05 +0000

oops :-)

here is another code

clear,clc
sz = [5 8];
A = rand(sz);
S = sort(A);
S(1,:)

Re: Find Minimum Values of Matrix without MIN or For loops

Nasser M. Abbasi — Sun, 01 May 2011 08:02:20 +0000

On 5/1/2011 12:46 AM, m4 Chrennikov wrote:
> If I get it clearly, you are searching the minimum element in each column?
> min(A)
> can replace all code.

but OP said clearly they do _not_ want to use MIN.

It is even in the subject.

Re: Find Minimum Values of Matrix without MIN or For loops

Srikanth — Sun, 01 May 2011 18:34:44 +0000

For the minimum of the entire matrix, do V=sort(A(:)). Then V(1)
contains the smallest value of the entire matrix.

Re: Find Minimum Values of Matrix without MIN or For loops

Roger Stafford — Sun, 01 May 2011 19:09:04 +0000

"m4 Chrennikov" <abrek77@gmail.com> wrote in message <ipj3it$or2$1@fred.mathworks.com>...
> .......
> S = sort(A);
> S(1,:)
Srikanth <skt@xdtech.com> wrote in message <d46cdd28-70e5-4816-95bd-fa7afe0cbe56@r27g2000prr.googlegroups.com>...
> For the minimum of the entire matrix, do V=sort(A(:)). Then V(1)
> contains the smallest value of the entire matrix.
- - - - - - - - -
Replacing an order O(m*n) algorithm with an O(m*log(m)*n) or an O(m*n*log(m*n)) algorithm (for A an m x n matrix) involving sorting is hardly likely to be appreciated by Stephen's teacher in my opinion. Finding the vector minimum in that problem is an inherently order O(m*n) problem and he would do well to restrict himself to solutions of that order of complexity. The number of lines of code used is surely not a measure of the quality of a solution.

Roger Stafford

Re: Find Minimum Values of Matrix without MIN or For loops

John D'Errico — Sun, 01 May 2011 19:39:05 +0000

"Roger Stafford" wrote in message <ipkb4g$9uf$1@fred.mathworks.com>...
> "m4 Chrennikov" <abrek77@gmail.com> wrote in message <ipj3it$or2$1@fred.mathworks.com>...
> > .......
> > S = sort(A);
> > S(1,:)
> Srikanth <skt@xdtech.com> wrote in message <d46cdd28-70e5-4816-95bd-fa7afe0cbe56@r27g2000prr.googlegroups.com>...
> > For the minimum of the entire matrix, do V=sort(A(:)). Then V(1)
> > contains the smallest value of the entire matrix.
> - - - - - - - - -
> Replacing an order O(m*n) algorithm with an O(m*log(m)*n) or an O(m*n*log(m*n)) algorithm (for A an m x n matrix) involving sorting is hardly likely to be appreciated by Stephen's teacher in my opinion. Finding the vector minimum in that problem is an inherently order O(m*n) problem and he would do well to restrict himself to solutions of that order of complexity. The number of lines of code used is surely not a measure of the quality of a solution.
>
> Roger Stafford

I'm not sure that is true. There was no statement of
asymptotic efficiency as a requirement. We don't
know what is the goal of the instructor is in this case.

The stated goal was merely to find a solution that did
not use min and did not employ an explicit loop. The
application of sort satisfies all stated requirements.

John

Re: Find Minimum Values of Matrix without MIN or For loops

Adrien Leygue — Sun, 01 May 2011 21:57:04 +0000

Ok, here is a one-liner solution

As other answers have pointed, it is difficult to provide an answer to your problem that would have a computational complexity equivalent to the simplest loop that would look for the min over all columns. Yet, this is one of the the point of vectorizing it is sometimes faster to compute too much stuff if an efficient way than just what you need.

>> S = A((repmat(eye(size(A,1)),[1 size(A,1)]) *...
(kron(A,ones(size(A,1),1)) < kron(ones(size(A,1),1),A)))==0)'

basically:
1-use kron to generate all pairwise comparisons between the elements.
2-use a matrix matrix product to reduce all the comparisons and for each element of A, compute how many elements of the column are less than this element.
3-the min over each columns is the element wich have zero in their corresponding entry.
4-use logical indexing to extract the values

Hope this helps.

A.

Re: Find Minimum Values of Matrix without MIN or For loops

Roger Stafford — Mon, 02 May 2011 23:35:20 +0000

"Adrien Leygue" wrote in message <ipkkvg$5ti$1@fred.mathworks.com>...
> Ok, here is a one-liner solution
>
> As other answers have pointed, it is difficult to provide an answer to your problem that would have a computational complexity equivalent to the simplest loop that would look for the min over all columns. Yet, this is one of the the point of vectorizing it is sometimes faster to compute too much stuff if an efficient way than just what you need.
>
> >> S = A((repmat(eye(size(A,1)),[1 size(A,1)]) *...
> (kron(A,ones(size(A,1),1)) < kron(ones(size(A,1),1),A)))==0)'
>
> basically:
> 1-use kron to generate all pairwise comparisons between the elements.
> 2-use a matrix matrix product to reduce all the comparisons and for each element of A, compute how many elements of the column are less than this element.
> 3-the min over each columns is the element wich have zero in their corresponding entry.
> 4-use logical indexing to extract the values
>
> Hope this helps.
>
> A.
- - - - - - - - - - -
  That is an ingenious one-line solution, Adrien.

  I notice you can reduce it from complexity O(n^3*m) to only O(n^2*m) (where A is n by m) by doing a reshape over to a three-dimensional n x n x m size of the n^2 x m result of comparison between the two 'kron' products. Then you can do a "not-any" operation on the columns of this 3D matrix which should give you the same result. (Or if I have this wrong, something along these lines.) Multiplication by the repeated 'eye' matrix which makes it O(n^3*m) is surely not necessary.

  The result of this algorithm differs from that of 'min' in cases where there are repetitions of the minimum value within columns of A. Each repetition would appear in the final S giving it more than m values, whereas 'min' would only give the first encountered in each column.

  I still claim it might be a risky thing to hand in a solution to a teacher of greater complexity than that needed by 'min'. I would fear their grade score would be awarded in inverse proportion to the complexity used.

Roger Stafford

Re: Find Minimum Values of Matrix without MIN or For loops

Adrien Leygue — Tue, 10 May 2011 21:35:15 +0000

> I still claim it might be a risky thing to hand in a solution to a teacher of greater complexity than that needed by 'min'. I would fear their grade score would be awarded in inverse proportion to the complexity used.
>
> Roger Stafford

Well, if I were to ask to my students such an exercise (min over all columns) without loops and without the min function, I would not grade on efficiency. The problem itself is twisted. Imho, the only benefit from such exercise is to challenge the student creativity. In a sense the teacher is asking the students to surprise him.

A.