Evaluate a "matrix of bilinear-forms"

Question

I have $n\times m$ sparse matrices $U$ and $V$ ($n \gg m)$, $$ U = \left[ \begin{array}{1} \mathbf{u}_1 \\ \vdots \\ \mathbf{u}_n \end{array} \right],\quad V = \left[ \begin{array}{1} \mathbf{v}_1 \\ \vdots \\ \mathbf{v}_n \end{array} \right] $$ and would like to calculate a matrix $W$ with entries $$ w_{i,j} = \mathbf{u}_i X_{i,j} \mathbf{v}_j^T $$ where each $X_{i,j}$ is a diagonal matrix, with only positive values on the diagonal. In the case that $X=I$ this is easy: $W$ is a sparse matrix multiply $UV^T$. Are there efficient approaches for the general case? I'm particularly interested in a reduction of the problem to a sequence of calculations which would exploit the sparsity of the problem, preferably sparse matrix multiplications (my $n$ is large).

Answer 1

I am not sure this might help, but look at vec-operator to simplify this. So, vec operator $vec(A)$ is defined as the vector obtained by stacking columns of matrix $A$. Now we have the identity $$vec(ABC)=(C^T\otimes A)vec(B)$$ where $\otimes$ is the kronecker operator. Here $A=u_i,B=X_{ij},C=v_j^T$. Verify yourself that $$p=(C^T\otimes A)=(v_j\otimes u_i)$$ is a $1 \times m^2$ vector in your case. Also $$q=vec(B)=vec(X_{ij})$$ is a $m^2\times 1$ vector. Thus, your problem boils down to multiplying vectors $p$ and $q$. Now, since $X_{ij}$ is diagonal, only $m$ entries of vector $q$ at $[1,m+1,2m+1,\dots]$ will be non-zero. So you need to pick only the corresponding entries in $p$. Note that $$p=(v\otimes u)=[v_1u_1,v_1u_2,\dots,v_1u_m,~~v_2u_1,v_2u_2,\dots,v_2u_m,\dots]$$ Notice the pattern and taking the corresponding entries in $p$.