Filling a matrix with the sum of conditional values
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 &lt; N^{0.3029}$, for every $\epsilon &gt; 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.