<p>By <em>examples that use the atom $d_k$,i.e. those where $x_T^{k} (i)$ is nonzero</em>, 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 <strong>sparse</strong> representation, we only pay attention to the nonzero elements of $X$ and keep the zero elements intact. </p>

CC BY-SA 3.0
2016-08-20T13:47:33.987Z
2016-08-20T13:47:33.987Z
Gigili
<p>Trying to understand a paper titled <a href="http://dl.acm.org/citation.cfm?id=2201437" rel="noreferrer">KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation</a> by M.Elad, et al;<br />
my take of <em>section IV.C.</em> <em>detailed description of KSVD</em>, 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.
<span class="math-container">$$\min_{X,D} \{||Y-DX||_F^2\} \quad \textrm{  subject to} \quad \forall i, ||x_i||\leq T_0$$</span></p>
<p>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:</p>
<blockquote>
<p>examples that use the atom <span class="math-container">$d_k$</span>,i.e. those where <span class="math-container">$x_T^{k} (i)$</span> is
nonzero.</p>
</blockquote>
<p>Any clarifications would be appreciated.</p>

<approximation-algorithms><machine-learning><paper-review>
Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al
Gigili
# Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al

(Asked by: username_0 on 2015-09-02)

Trying to understand a paper titled [KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation](http://dl.acm.org/citation.cfm?id=2201437) 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.

**Tags:** approximation-algorithms, machine-learning, paper-review


---

## 1 answers

### Answer by username_0 on 2016-08-20. Score: 1

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.


---

