Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Find Minimum Values of Matrix without MIN or For loops
Date: Mon, 2 May 2011 23:35:20 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 27
Message-ID: <ipnf3o$9g3$1@fred.mathworks.com>
References: <ipih48$enm$1@fred.mathworks.com> <ipkkvg$5ti$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: www-06-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1304379320 9731 172.30.248.38 (2 May 2011 23:35:20 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 2 May 2011 23:35:20 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:724875

"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