Trying to understand a paper titled KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation by M.Elad, et al;
my take of section IV.C. detailed description of KSVD, is that we have an objectiove function which we wish to minimize with respect to two variables, D (which is called the dictionary) and X (the coefficient matrix. $$\min_{X,D} \{||Y-DX||_F^2\} \quad \textrm{ subject to} \quad \forall i, ||x_i||\leq T_0$$

One method of doing this is to divide it to two stages, sparse coding and dictionary update. In the sparse coding stage, we assume D is fixed and solve the above problem w.r.t X using a pursuit algorithm. Then we must update the dictionary to better fit our data using the coefficient matrix from previous stage. In the update stage, we keep both X and D fixed and only one column of D and its corresponding row in X remains in question. After simplifying the objective function and decomposing the multiplication DX to the sum of k rank-1 matrices, one might suggest to use svd. But that would ruin the sparsity of X, so wee need to set constraints. At this point, the authors define some variables and use them for setting constraints. The problem is, I don't understand what is meant by this statement:

examples that use the atom $d_k$,i.e. those where $x_T^{k} (i)$ is nonzero.

Any clarifications would be appreciated.


By examples that use the atom $d_k$,i.e. those where $x_T^{k} (i)$ is nonzero, the authors are referring to the nonzero elements of the coefficient matrix $X$ because only nonzero elements play a role in multiplying two matrices. Since we seek to have a sparse representation, we only pay attention to the nonzero elements of $X$ and keep the zero elements intact.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.