# Aiding Dictionary Learning Through Multi-Parametric Sparse Representation
## 4 Integration of the Multi-Parametric Formulation in the Representation Problem
### The Enumeration Roadblock
```
Data: signals set \(\mathbf{Y}\in\mathbb{R}^{m\times N}\) collection of critical regions \(\mathcal{P}=\{\mathcal{O}\}\subset\mathbb{R}^{m}\) piecewise affine law \((\mathcal{M}=\{\mathcal{O}\},\backslash=\{\mathcal{O}\})\subset\mathbb{R}^{n \times m}\times\mathbb{R}^{n}\)
1 for\(k=1:N\)do
2 Find index of the region containing the current value of parameter \(\mathbf{y}\): \[i=\arg\min_{i,\mathcal{R}^{i}\in\mathcal{P}}\mathbf{y}\in\mathcal{R}^{i};\] if\(i=\{\mathcal{O}\}\)then
3 solve (20) for the current value of \(\mathbf{y}\) obtaining the affine law \((\mathbf{M}_{\alpha},\mathbf{N}_{\alpha})\) as in (22) and the critical region \(\mathcal{R}\), as in (23);  update the partition and the affine law collections: \(\mathcal{P}=\mathcal{P}\cup\{\mathcal{R}\}\), \(\mathcal{M}=\mathcal{M}\cup\{\mathbf{M}_{\alpha}\}\) and \(\backslash=\mathcal{N}\cup\{\mathbf{N}_{\alpha}\}\);  change the index to point to the last collection element: \(i=\#\mathcal{P}\);
4 apply the selected law to the current parameter: \(\mathbf{\alpha}=\mathbf{M}_{\alpha}^{i}\mathbf{y}+\mathbf{N}_{\alpha}^{i}\), \(\mathbf{x}=\mathbf{F}\mathbf{\alpha}\)
```  
**Algorithm 2**Multi-parametric implementation of the sparse problem. Steps 3 and 6 of the algorithm deserve some additional thought. Recall that \(\mathbf{V}^{\top}= \begin{bmatrix}\mathbf{W}^{\top}&-\mathbf{W}^{\top}\end{bmatrix} \) has a symmetrical structure. Coupling this with the observations around (25)-(26) shows that, for each combination of \(\hat{m}\) active constraints (i.e., those for which \(\hat{\mathbf{\alpha}}>0\)), there are \(2^{\hat{m}}\) permutations in the column selection from \(\mathbf{V}^{\top}\) such that the resulted sub-matrices differ only through the signs of their columns. That is, there exist suitably chosen diagonal matrices \(\hat{\mathbf{P}},\hat{\mathbf{P}}\) with \(\pm 1\) entries such that, e.g., \(\hat{\mathbf{V}}_{1}^{\top}\mapsto\hat{\mathbf{V}}_{1}^{\top}\hat{\mathbf{P}}\), \(\hat{\mathbf{V}}_{12}^{\top}\mapsto\hat{\mathbf{V}}_{1}^{\top}\hat{\mathbf{P}}\). Recalling that, for an active set selection \((\hat{\cdot}),(\hat{\cdot})\) there exist solutions \(\mathbf{\alpha}(\mathbf{y}),\mathbf{\lambda}(\mathbf{y})\), introducing the sign permutations characterized by \(\hat{\mathbf{P}},\hat{\mathbf{P}}\) into (20) leads to a similar sign permutation of the solution:  
\[\begin{cases}\hat{\mathbf{\alpha}}(\mathbf{y})&=\hat{M}_{\alpha}\mathbf{y}+\hat{N}_{ \alpha},&\xrightarrow[]{\hat{\mathbf{P}},\hat{\mathbf{P}}} \begin{cases}\hat{\mathbf{\alpha }}(\mathbf{y})&=\hat{M}_{\alpha}\mathbf{y}+\hat{N}_{\alpha},&\xrightarrow[]{\hat{\mathbf{ P}}^{2}=I,\hat{\mathbf{P}}^{2}=I}\\ \hat{\mathbf{\lambda}}(\mathbf{y})&=\hat{M}_{\lambda}\mathbf{y}+\hat{N}_{\lambda},& \xrightarrow[]{\hat{\mathbf{\alpha}}(\mathbf{y})}&=\hat{P}\hat{M}_{\alpha}\mathbf{y}+\hat {P}\hat{N}_{\lambda}.\end{cases}\begin{cases}\hat{\mathbf{\alpha}}(\mathbf{y})&=\hat{P} \hat{M}_{\alpha}\mathbf{y}+\hat{P}\hat{N}_{\alpha},\\ \hat{\mathbf{\lambda}}(\mathbf{y})&=\hat{P}\hat{M}_{\lambda}\mathbf{y}+\hat{P}\hat{N}_{ \lambda}.\end{cases}  \tag{27}\]  
The last implication exploits the structure of \(\hat{\mathbf{P}},\hat{\mathbf{P}}\) by noting that their squared forms are the identity matrices. The meaning of (27) is twofold:1. only a single representative of the same family of active constraints has to be stored (Step 6 of Algorithm 2); the remaining \(2^{th}-1\) variations may be deduced by multiplying with suitable \(\hat{P},\hat{P}\);
2. the inclusion test (Step 3 of Algorithm 2) has to account for the sign permutations; this can be done, e.g., by checking whether \(\big{[}\hat{M}_{\alpha}y+\hat{N}_{\alpha}\big{]}\odot\big{[}\hat{M}_{\lambda} y+\tilde{N}_{\lambda}\big{]}_{j}\geq\mathbf{0}\) holds. We denoted with '\(\odot\)' the elementwise product and with \([\cdot]_{j}\) the selection of \(\hat{m}\) (out of \(\hat{m}\)) rows which correspond to the ones appearing in \(\hat{\mathbf{\kappa}}\). Recall that weights \(\alpha\) come in pairs (since they are attached to the unit vectors \(\pm e_{i}\)).