1
$\begingroup$

Assume that a matrix $M\in [0;1]^{n\times d}$ is given, i.e., all values in the matrix are in the range 0 to 1. I would like to compute the following function for all rows of $M$:

$$ f(m_1,m_2,...,m_d)=\frac{1}{n}\sum_{i=1}^{n} \begin{cases}1 \quad \text {if} \quad M[i,j] \le m_j \text{for all} j\\ 0\quad \text{else} \end{cases} $$ The input $m_1,m_2,...,m_d$ is one row of $M$, and I would like to compute $f$ for all rows. Intuitively, $f$ computes the average number of rows for which it holds that all columns are smaller (or equal) than all columns of the input row.

This can be naively done by directly computing $f$ for $i\in 1,...,n$ but this would require a total of $\mathcal{O}(n^2\cdot d)$ computations.

Question: Is there a more efficient way of getting the result for all rows? For example, an algorithm that requires $\mathcal{O}(n\log n \cdot d)$ steps.

My gut feeling tells me this should be possible using dynamic programming because we can reuse several intermediate results of each call to $f$, but I don't know how.

$\endgroup$

1 Answer 1

1
$\begingroup$

Except in some special cases where $d$ is very small, I don't think there is any algorithm whose running time is noticeably better than $\mathcal{O}(n^2)$ (ignoring the dependence on $d$). In particular, I suspect one can prove a reduction showing that you can't do better than $\mathcal{O}(n^{2-\epsilon})$ unless the Strong Exponential Time Hypothesis (SETH) is false. Since SETH is an open conjecture, this would supply evidence that it won't be easy to exhibit an algorithm to substantially improve on the naive algorithm you've already gotten.

If $d$ is very large, I suspect you'll be able to get good results by a random linear project down to $d'=O(\lg n)$ dimensions.

Relevant reading: https://cstheory.stackexchange.com/q/37361/5038, https://algorithm-wiki.csail.mit.edu/wiki/Partial_Match, https://stuff.mit.edu/afs/sipb/user/bert/debug/root/mit/jfc/tmp/subset%20queries.pdf.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, and especially for the links. They are very useful. $\endgroup$
    – mto_19
    Jan 19 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.