wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Median of a Matrix
        
(Message started by: Sriram on Jul 30^th, 2006, 5:46am)

Title: Median of a Matrix
Post by Sriram on Jul 30^th, 2006, 5:46am

Hi All,

We have a N X N matrix whose rows and columns are in sorted order. It is called as Young's Tableau matrix. How effeciently can we find the median of those N^2 keys ?

Title: Re: Median of a Matrix
Post by towr on Jul 30^th, 2006, 1:42pm

At least O(N^2), but I figure you're looking for something better.

Title: Re: Median of a Matrix
Post by Grimbal on Jul 31^st, 2006, 3:46am

O(n log n) should be possible.

Title: Re: Median of a Matrix
Post by Sriram on Aug 3^rd, 2006, 9:11am

How O(n log n) solution is possible ? There are n^2 keys.

Title: Re: Median of a Matrix
Post by Grimbal on Aug 3^rd, 2006, 9:56am

Yes, but you don't have to test them all.

Maybe it is not as easy as I thought.

The idea was that given a value, there is a O(n) method to count how many elements are larger than that. Just start from the upper left corner and move down and left following the limit between smaller and larger elements. I thought of somehow dividing the set under scrutiny until there is only one element left. That would take O(log n) divisions each taking O(n) time. To divide the set, I could use the average between the min and max of the remaining set, but that works well only if the elements follow a somehow smooth distribution. It doesn't work well in some cases, for instance if we are comparing strings.

It still needs some thinking. But I am sure better than O(n²) is possible.

Title: Re: Median of a Matrix
Post by Sjoerd Job Postmus on Aug 3^rd, 2006, 1:25pm

on 07/30/06 at 05:46:17, Sriram wrote:

Hi All,

We have a N X N matrix whose rows and columns are in sorted order. It is called as Young's Tableau matrix. How effeciently can we find the median of those N^2 keys ?

This means, that for any i,j where they make sense:

A_i,j <= A_i,j+1
A_i,j <= A_i+1,j

This means that the highest number can be found at A_n,n, and the lowest at A_1,1...

Also... we do know something about the position of the item... For instance, all the positions that can possibly be the same or higher, must equal the number of positions that can possibly be equal or lower.

Assuming odd N.
Now, what would be true if (median = A[i,j])...

(p <= i && q <= j) => (A[p,q] <= A[i,j])
(p >= i && q >= j) => (A[p,q] >= A[i,j])

Thus, if it is the median:
(1) i * j <= N^2 / 2.
(2) (N-i+1)*(N-j+1) <= N^2 / 2

Warning: Original Erronous thought pattern follows:
expanding braces on 2 yields
(3) N^2 - jN + N - iN + i*j - i + N - j + 1 <= N^2 / 2
Simplifying and Substracting (1) from (3)
(3) N^2 + 2N + 1 - j*(N+1) - i*(N+1) <= 0
Noticing (a+1)^2 = a^2 + 2a + 1
(4) (N+1)^2 - j*(N+1) - i*(N+1) <= 0
Dividing.
(5) (N+1) - j - i <= 0
(6) N+1 <= i + j
(7) N <= i + j - 1
(8) j >= N - i + 1

--- Resuming thought patterns ---
Our limitations have cut of two parts... But, there is still some remaining part to test. The area we have to test is:
N^2 - 2*((.5N)(.5N+1)/2) = N^2 - ((.5N)^2 + .5N) = .5 N^2 - .5 N = .5 (N^2 - N)
In fact, the region is even smaller... but I'm trying to keep it at low-level math...

It's still O(N^2)... but it's more efficient than looking at all elements...

If there was a really quick median test, we could use that...

Title: Re: Median of a Matrix
Post by Barukh on Jun 13^th, 2007, 6:04am

The O(n log(n)) solution indeed exists.

Title: Re: Median of a Matrix
Post by anshulk_scorp on Jun 20^th, 2007, 2:46am

Please let me know if I am wrong....I am new here....

I believe the problem is quite simple....
I am declaring names for matrix positions in following figure...

D1 D2 D3 D4 ...
D2 D3 D4 D5 ...
D3 D4 D5 D6 ...
D4 D5 D6 D7 ...

in general Dn is an element on nth line(considering lines parellel to +ve sloping diagonal) of +slope...( C(i)=C(j) )....

If these n^2 elements are sorted....
They wud be in following order...
(D1) (D2 D2) (D3 D3 D3) (D4 D4 D4 D4) (D5 D5 D5) (D6 D6) (D7)
for a matrix of size 4*4

The median therefore lies in the set of D4's....
Generaly speaking....The median is one of the element on the main diagonal of the n*n matrix....
That means we only have to find median of a set of n elements....
for a large set.....sorting is ok.....O(nlogn)
for a small set....O(n^2) approach of insertion sort is good....
Anyway...i dont think complexity can be reduced below O(nlog n)

Title: Re: Median of a Matrix
Post by Grimbal on Jun 20^th, 2007, 3:21am

I don't think it works

In the following array
1 1 1 1 3
1 1 2 3 3
1 1 3 3 3
1 1 3 3 3
1 1 3 3 3

The median is 2 and it is not in the main diagonal.

Title: Re: Median of a Matrix
Post by caoxuecheng on Jun 21^st, 2007, 9:14pm

can I use an extern heap(size n) to store the smallest number of each row, so that can solve it in O(nlogn).

Title: Re: Median of a Matrix
Post by chetangarg on Jul 10^th, 2007, 9:49pm

Can any one please tell me if there is any (n log n) solution to this problem...
I don't know how to implement this idea
divide the n x n matrix in four matrices of n/2 x n/2 each.
naming them
a b
c d

now median is definitely not in a and d
it is in either b or c. means we are left with half elements
now divide the sub matrix b and c in four parts
say
b1 b2 and c1 c2
b3 b4 c3 c4
compare the last element of b1 with last element of c1 if former is bigger than median can't be in b4
so we have reduced n/16 cases. i hope this approach can lead to a logarithmic solution but
i don't know how to implement it further..
can any one please help me..

Title: Re: Median of a Matrix
Post by towr on Jul 11^th, 2007, 1:19am

on 07/10/07 at 21:49:13, chetangarg wrote:

How will you divide a matrix with an odd number of rows and columns? At the very least you don't end up with 4 square matrices. (Unless you let them overlap, which probably presents its own problems)

Quote:

now median is definitely not in a and d

If you have
1 1 1 1
1 2 3 3
1 3 3 3
1 3 3 3
Then half the median is in a (with an even number of elements the median is the average of the middle two elements, so in this case (2+3)/2 and 2 lies in a)

Title: Re: Median of a Matrix
Post by Barukh on Jul 11^th, 2007, 10:27am

The O(n log(n)) algorithm exists (it was invented in 70s), but it's not trivial. Here's an outline.

For every row i of the matrix, keep 2 numbers L_i, R_i, s.t. if the median happens to lie in row i - say, it's A_ij - then L_i <= j <= R_i. At the beginning, of course L_i = 1, R_i = n.

At each step, the algorithm takes at most n numbers - one from each row - and finds a so called "weighted median" of them (this takes O(n) time). It is then shown how to adjust the boundaries L_i, R_i so that the constant fraction of remaining elements is excluded from candidates for the median. This guarantees the overall complexity.

If there is an interest, I can check the details.

Title: Re: Median of a Matrix
Post by Skandh on Aug 22^nd, 2007, 3:10am

on 07/11/07 at 10:27:16, Barukh wrote:

Please explain it in detail.

:) :) :)

Title: Re: Median of a Matrix
Post by Barukh on Aug 26^th, 2007, 5:37am

Well, I will try... I will make it in several posts.

First, we need to discuss the concept of “weighted median” of an array.

Consider an array A = (a₁, …, a_n), and an associated array of positive real numbers (called weights) W = (w₁, …, w_n), such that w_i corresponds to a_i.

Define S(m) = sum of weights corresponding to m smallest elements in A. Then, the weighted median (WM) of A is the m-th smallest element of A satisfying the following:

2S(m-1) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif S(n), 2S(m) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif S(n)

Note that the usual median is a special case of WM, when all the weights w_i equal to 1.

Example: A = (2, 5, 1, 3); W = (1, 2, 5, 1). Then, S(1) = 5, S(2) = 6, S(3) = 7, S(4) = 9. In this case, the weighted median is element a₃ = 1, while the usual median is a₁ = 2.

The important (for this discussion) result about WM is that it can be computed in linear time even when A is not sorted.

To be continued... ;)

Title: Re: Median of a Matrix
Post by Skandh on Aug 31^st, 2007, 12:07am

Sorry Barukh, I was out of station for some time. Will you please continue. I am getting it little bit, but it will be very helpful if you please enlighten me further.

Title: Re: Median of a Matrix
Post by Barukh on Sep 1^st, 2007, 7:10am

on 08/31/07 at 00:07:26, Skandh wrote:

Sorry Barukh, I was out of station for some time. Will you please continue. I am getting it little bit, but it will be very helpful if you please enlighten me further.

I didn’t forget about this thread, I just needed some inspiration to continue… ;D

The algorithm I am going to describe was invented by D. Johnson and T. Mizogushi and published back in 1978. As I already mentioned before, it performs iterations on the original matrix to remove from it elements that cannot be the sought quantity. It achieves an overall O(n log(n)) run time by ensuring that the number of elements removed at each iteration is at least a constant fraction of the overall number of elements left at the previous iteration.

What I am going to present, solves a more general problem, that is:

Find the K-th maximal element in a matrix with sorted (non-increasing) rows and columns.

In order to keep track on matrix elements that are candidates for the K-th maximum, the algorithm retains 2 indices, L_i, R_i for every row i = 1, …, n. The meaning of these is straightforward: in row i, the elements in columns L_i through R_i are still “in the play”. In the course of algorithm’s execution, it may be happen for some row i that L_i > R_i, which means no element of the i-th row is the sought K-th maximum. At the beginning, they are set L_i = 1, R_i = n.

The algorithm consists of the following essential steps:

1. Form two arrays M, W of size maximum n as follows:

for (i = 1, k = 1; i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n; i = i + 1)
{
if (L_i > R_i) continue;
m_k = a_ij, where j = (L_i + R_i) >> 1
w_k = R_i - L_i + 1
k = k + 1
}

2. Find the weighted median, m, of array M w.r.t to weights W.

3. This step computes the quantities P, Q and P_i, Q_i (partitions) as follows:

for (i = 1, P = 0, Q = 0; i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n; i = i + 1)
{
P_i = IF (a_i1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif m) THEN 0 ELSE max(j | a_ij > m)
Q_i = IF (a_in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif m) THEN n+1 ELSE min(j | a_ij < m)
P = P + P_i
Q = Q + Q_i - 1
}

4. This step discards elements from the matrix as follows:

IF K http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif P, THEN R_i = P_i, i = 1, …, n
ELSE IF K > Q THEN L_i = Q_i, i = 1, …, n
ELSE RETURN m as K-th maximum

5. Continue? Compute the total number of remaining “candidates” as C = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(R_i–L_i+1). If C > n, GOTO step 1, OTHERWISE, sort the remaining elements to find the desired entry.

Phew, that's it! I am leaving the analysis (of both correctness and run-time) for another post… Meanwhile, is anybody willing to comment on this? ;)

Title: Re: Median of a Matrix
Post by ic10503 on Jun 18^th, 2008, 2:46pm

on 07/30/06 at 13:42:12, towr wrote:

At least O(N^2), but I figure you're looking for something better.

can you please propose your n^2 algorithm ?
Can anyone give the link for the original paper which has order nlgn algorithm (as told by barukh)?

Title: Re: Median of a Matrix
Post by towr on Jun 18^th, 2008, 3:09pm

on 06/18/08 at 14:46:02, ic10503 wrote:

can you please propose your n^2 algorithm ?

After two years, I can't say I remember.

You seem to be digging up fairly old topics a lot; albeit not by the dozens per week. But please bare that in mind.

Maybe it'll come to me tomorrow.

Title: Re: Median of a Matrix
Post by birbal on Mar 18^th, 2011, 10:56pm

on 06/18/08 at 14:46:02, ic10503 wrote:

can you please propose your n^2 algorithm ?
Can anyone give the link for the original paper which has order nlgn algorithm (as told by barukh)?

O(n^2) is quite easy. See this http://en.wikipedia.org/wiki/Selection_algorithm