World's most popular travel blog for travel bloggers.

Filling a matrix with the sum of conditional values

, , No Comments
Problem Detail: 

I have $P$ vectors of size $N$ with elements in $\{0,1\}$. Each vector $v$ has a value $\alpha_v$.

I would like to Fill a square matrix $M$ of size $N\times N$ in the following way:

$$\forall i,j \in \{1,2,...,N\}~ M_{i,j} = \sum_{\text{vectors}~v : v_i v_j =1} \alpha_v$$

Is it possible to fill the matrix $M$ in time complexity better than $O(P\cdot N^2)$?

Assuming that each vector has at most $Q$ elements equal to $1$, is it possible to do better than $O(P\cdot(N+Q^2))$ ?

Asked By : Issam T.

Answered By : Yuval Filmus

Let $V$ be the $N\times P$ matrix whose columns are the vectors $v$, and let $D$ be the $P\times P$ diagonal matrix with elements $D_{vv} = \alpha_v$. Then you want to compute $VDV^T$. Computing $U = DV^T$ takes time $NP$, and it remains to compute $VU$. When $P < N^{0.3029}$, for every $\epsilon > 0$ there is an (impractical) algorithm to compute this product in time $O_\epsilon(N^{2+\epsilon})$. See Le Gall, who improved on an earlier result of Coppersmith.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37510

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback