Author |
Topic: Median of a Matrix (Read 9917 times) |
|
Sriram
Newbie
Gender: 
Posts: 15
|
 |
Median of a Matrix
« on: Jul 30th, 2006, 5:46am » |
 Quote  Modify
|
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 ?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Median of a Matrix
« Reply #1 on: Jul 30th, 2006, 1:42pm » |
Quote Modify
|
At least O(N^2), but I figure you're looking for something better.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Median of a Matrix
« Reply #2 on: Jul 31st, 2006, 3:46am » |
Quote Modify
|
O(n log n) should be possible.
|
|
IP Logged |
|
|
|
Sriram
Newbie
Gender:
Posts: 15
|
|
Re: Median of a Matrix
« Reply #3 on: Aug 3rd, 2006, 9:11am » |
Quote Modify
|
How O(n log n) solution is possible ? There are n^2 keys.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Median of a Matrix
« Reply #4 on: Aug 3rd, 2006, 9:56am » |
Quote Modify
|
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(n2) is possible.
|
|
IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Median of a Matrix
« Reply #5 on: Aug 3rd, 2006, 1:25pm » |
Quote Modify
|
on Jul 30th, 2006, 5:46am, 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:
Ai,j <= Ai,j+1
Ai,j <= Ai+1,j
This means that the highest number can be found at An,n, and the lowest at A1,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
( 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...
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Median of a Matrix
« Reply #6 on: Jun 13th, 2007, 6:04am » |
Quote Modify
|
The O(n log(n)) solution indeed exists.
|
| « Last Edit: Jun 13th, 2007, 9:35am by Barukh » |
IP Logged |
|
|
|
anshulk_scorp
Newbie
Posts: 8
|
|
Re: Median of a Matrix
« Reply #7 on: Jun 20th, 2007, 2:46am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Median of a Matrix
« Reply #8 on: Jun 20th, 2007, 3:21am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 20th, 2007, 3:22am by Grimbal » |
IP Logged |
|
|
|
caoxuecheng
Newbie
Posts: 1
|
|
Re: Median of a Matrix
« Reply #9 on: Jun 21st, 2007, 9:14pm » |
Quote Modify
|
can I use an extern heap(size n) to store the smallest number of each row, so that can solve it in O(nlogn).
|
|
IP Logged |
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: Median of a Matrix
« Reply #10 on: Jul 10th, 2007, 9:49pm » |
Quote Modify
|
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..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Median of a Matrix
« Reply #11 on: Jul 11th, 2007, 1:19am » |
Quote Modify
|
on Jul 10th, 2007, 9:49pm, chetangarg wrote: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
|
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Median of a Matrix
« Reply #12 on: Jul 11th, 2007, 10:27am » |
Quote Modify
|
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 Li, Ri, s.t. if the median happens to lie in row i - say, it's Aij - then Li <= j <= Ri. At the beginning, of course Li = 1, Ri = 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 Li, Ri 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.
|
|
IP Logged |
|
|
|
Skandh
Junior Member
Gender:
Posts: 77
|
|
Re: Median of a Matrix
« Reply #13 on: Aug 22nd, 2007, 3:10am » |
Quote Modify
|
on Jul 11th, 2007, 10:27am, Barukh wrote: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 Li, Ri, s.t. if the median happens to lie in row i - say, it's Aij - then Li <= j <= Ri. At the beginning, of course Li = 1, Ri = 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 Li, Ri 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. |
|
Please explain it in detail.
|
| « Last Edit: Aug 22nd, 2007, 3:11am by Skandh » |
IP Logged |
I wanna pull by legs!!!
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Median of a Matrix
« Reply #14 on: Aug 26th, 2007, 5:37am » |
Quote Modify
|
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 = (a1, …, an), and an associated array of positive real numbers (called weights) W = (w1, …, wn), such that wi corresponds to ai.
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)  S(n), 2S(m)  S(n)
Note that the usual median is a special case of WM, when all the weights wi 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 a3 = 1, while the usual median is a1 = 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... 
|
|
IP Logged |
|
|
|
Skandh
Junior Member
Gender:
Posts: 77
|
|
Re: Median of a Matrix
« Reply #15 on: Aug 31st, 2007, 12:07am » |
Quote Modify
|
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.
|
|
IP Logged |
I wanna pull by legs!!!
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Median of a Matrix
« Reply #16 on: Sep 1st, 2007, 7:10am » |
Quote Modify
|
on Aug 31st, 2007, 12:07am, 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… 
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, Li, Ri for every row i = 1, …, n. The meaning of these is straightforward: in row i, the elements in columns Li through Ri are still “in the play”. In the course of algorithm’s execution, it may be happen for some row i that Li > Ri, which means no element of the i-th row is the sought K-th maximum. At the beginning, they are set Li = 1, Ri = 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 n; i = i + 1)
{
if (Li > Ri) continue;
mk = aij, where j = (Li + Ri) >> 1
wk = Ri - Li + 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 Pi, Qi (partitions) as follows:
for (i = 1, P = 0, Q = 0; i n; i = i + 1)
{
Pi = IF (ai1 m) THEN 0 ELSE max(j | aij > m)
Qi = IF (ain m) THEN n+1 ELSE min(j | aij < m)
P = P + Pi
Q = Q + Qi - 1
}
4. This step discards elements from the matrix as follows:
IF K P, THEN Ri = Pi, i = 1, …, n
ELSE IF K > Q THEN Li = Qi, i = 1, …, n
ELSE RETURN m as K-th maximum
5. Continue? Compute the total number of remaining “candidates” as C =  (Ri–Li+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?
|
| « Last Edit: Sep 1st, 2007, 7:11am by Barukh » |
IP Logged |
|
|
|
ic10503
Junior Member
Gender:
Posts: 57
|
|
Re: Median of a Matrix
« Reply #17 on: Jun 18th, 2008, 2:46pm » |
Quote Modify
|
on Jul 30th, 2006, 1:42pm, 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)?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Median of a Matrix
« Reply #18 on: Jun 18th, 2008, 3:09pm » |
Quote Modify
|
on Jun 18th, 2008, 2:46pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Median of a Matrix
« Reply #19 on: Mar 18th, 2011, 10:56pm » |
Quote Modify
|
on Jun 18th, 2008, 2:46pm, 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
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print