0

The sparse coding problem is:

$\underset{\boldsymbol{r}}{\text{min}} \left\Vert \boldsymbol{r} \right\Vert_0 ~s.t.~\textbf{x}=\text{D}\boldsymbol{r}$

Why do sparse dictionary learning algorithms such as MOD and K-SVD solve

$\underset{\text{D},\left\{ \boldsymbol{r}_i \right\}_{i=1}^{s}}{\text{min}}~~\overset{s}{\underset{i=1}{\sum}} \left\Vert \textbf{x}_i - \text{D}\boldsymbol{r}_i \right\Vert_2^2 ~s.t.~\left\Vert \boldsymbol{r}_i \right\Vert_0 \leq k~,~1 \leq i \leq s$

rather than the following problem?

$\underset{\text{D},\left\{ \boldsymbol{r}_i \right\}_{i=1}^{s}}{\text{min}}~~ \left\Vert \boldsymbol{r}_i \right\Vert_0 ~s.t.~ \overset{s}{\underset{i=1}{\sum}} \left\Vert \textbf{x}_i - \text{D}\boldsymbol{r}_i \right\Vert_2^2 \leq \epsilon~,~1 \leq i \leq s$

elliotp
  • 155
  • According to wikipedia it does https://en.wikipedia.org/wiki/K-SVD "or in another objective form" – mathreadler Apr 15 '18 at 01:02
  • @mathreadler I understand that it is possible, but the original paper and other papers and books also prefer the problem of constraining the sparsity and apply it. I was wondering if there is a reason for this. – elliotp Apr 15 '18 at 01:17
  • The 0 norm is discrete and binary. It becomes a combinatorial problem which is in general nastier than continous optimization. – mathreadler Apr 15 '18 at 01:19
  • @mathreadler Then why are greedy methods that solve the 0 norm more often used for dictionary learning rather than methods that relax it to the 1 norm? – elliotp Apr 15 '18 at 01:39
  • It depends a lot on if you need to solve it exactly or just find a quite good one quickly. Greedy ones can be good for the latter. – mathreadler Apr 15 '18 at 01:42

0 Answers0