Efficient way of computing average ALL function over matrix rows

Question

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.

Answer 1

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.