I will be doing my master thesis on dictionary learning, and I am trying to understand basic concepts of the subject reading the following paper:
K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
In the following lines there are two conclusions or results which I don't understand well:
We now turn to the second, and slightly more involved, process of updating the dictionary together with the nonzero coefficients. Assume that both $D$ and $X$ are fixed and we put in question only one column in the dictionary $d_k$ and the coefficients that correspond to it, the $k$th row in $X$, denoted as $x_T^{k}$ (this is not the vector which is the $k$th column in $X$). [...] We have decomposed the multiplication $DX$ to the sum of $k$ rank-$1$ matrices. Among those, $k-1$ terms are assumed fixed, and one—the $k$th—remains in question. The matrix stands for the error for all the examples when the $k$th atom is removed.
Now my questions are:
- In the multiplication $DX$, the paper is talking about multiplying columns of $D$ by rows of $X$, is this mathematically correct? I was taught that we multiply rows of the first matrix by the columns of the second one, isn't it so?
- What is meant by the sentence in bold, "sum of $k$ rank-$1$ matrices"?
The $(i,j)$ entry of the matrix product $DX$ is indeed the product of the $i$'th row of $D$ and the $j$'th column of $X$. This is talking about the same multiplication from a slightly different perspective. Each element in the $k$'th column of $D$ gets multiplied by each element in the $k$'th row of $X$, and the results put in different entries of the product. If $D$ is $m \times n$ and $X$ is $n \times p$, $DX$ is the sum of the $n$ matrices $d_k x_T^k$, $k = 1 \ldots n$, each of which is an $m \times p$ matrix that has rank $1$. Thus $DX$ is the sum of $n$ rank-$1$ matrices.