# Aiding Dictionary Learning Through Multi-Parametric Sparse Representation
## 4 Integration of the Multi-Parametric Formulation in the Representation Problem
### The Enumeration Roadblock  
The \"dirty\" secret in multi-parametric programming is that the number of critical regions explodes exponentially with the parameter space size and with the complexity of the feasible domain [9]. Moreover, the number of feasible (non-empty) regions is not usually known a priori [6]. In this particular case, the cross-polytope's specific structure means that we can bound a priori the number of critical regions and enumerate them constructively. To do this, we recall [11] that, for each pair of non-opposite vertices, there is an edge joining them. More generally, each set of \(k+1\) orthogonal vertices corresponds to a distinct \(k\)-dimensional face that contains them (particular, more familiar instances of the '\(k\)-dimensional face' are the \(0,1,n-1\)-dimensional faces--the vertices, edges and, respectively, facets of a polyhedron). The number of \(k\)-dimensional faces in an \(n\)-dimensional cross-polytope is therefore  
\[2^{k+1}\binom{n}{k+1}. \tag{25}\]  
As highlighted in Section 3, the constrained optimum \(\mathbf{\xi}_{i}^{\star}=\mathbf{F}\mathbf{\kappa}_{i}^{\star}\) is found by fixing \(\hat{m}\) of the cross-polytope's vertices (i.e., those for which \(\hat{\mathbf{\kappa}}>0\)). Due to the cross-polytope's properties, we know that these vertices describe an \(\hat{m}-1\)-dimensional face. With the full-rank condition employed in (18), \begin{table}
\begin{tabular}{c c c} \hline \hline
**Sparse Representation** (2) & **Form** (14) & **Cosparse Representation** (8) \\ \hline \(\mathbf{x}\in\mathbb{R}^{n}\) & \(\mathbf{\xi}\) & \(\mathbf{z}\in\mathbb{R}^{m}\) \\ \(\mathbf{y}\in\mathbb{R}^{m}\) & \(\mathbf{y}\) & \(\mathbf{y}\in\mathbb{R}^{m}\) \\ \(\mathbf{D}\in\mathbb{R}^{m\times n}\) & \(\mathbf{T}\) & \(\mathbf{I}\in\mathbb{R}^{m}\) \\ \(\mathbf{I}\in\mathbb{R}^{m\times n}\), \(\mathbf{1}\in\mathbb{R}^{n}\) & \(\mathbf{\Delta},\mathbf{\delta}\) & \(\mathbf{\Omega}\in\mathbb{R}^{n\times m}\), \(\mathbf{1}\in\mathbb{R}^{n}\) \\ \(\left[\mathbf{D}\quad-\mathbf{D}\right]\in\mathbb{R}^{m\times 2n}\) & \(\mathbf{TF}\) & \(\left[\mathbf{\Omega}\quad-\mathbf{\Omega}\right]\in\mathbb{R}^{n\times 2m}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Equivalences of the sparse and cosparse representations w.r.t. form (14). \(\hat{m}\leq m+1\), and applying the bound from (25), we have that the total number of faces with dimension \(m\) or lower is  
\[\sum_{\hat{m}=1}^{m+1}2^{\hat{m}}\binom{n}{\hat{m}}. \tag{26}\]  
Each \(\hat{m}\)-dimensional face corresponds to (a possibly empty) region (23). Thus, the total number of feasible combinations of active constraints is (26). Unfortunately, depending on the values of \(m,n\), the number of regions may prove to be prohibitively large (both from a computational and from a memory footprint/retrieval viewpoint). While there are multiple approaches that attempt to alleviate the issue [14], there is no panacea. In what follows, we consider a simple approach: regions \(\mathcal{R}^{i}\) are added to the partition only on an \"as-needed\" basis. More precisely, \(\mathbf{y}\) is searched in the list of already-computed regions; if found, the affine law (24) is applied; if not, (20) is solved for the current parameter \(\mathbf{y}\) in order to identify the optimal solution and the critical region over which it is valid. Once found, these are stored for further use. A sketch of the approach is shown in Algorithm 2 (for simplicity's sake, only for the sparse representation case is the cosparse case similar and can be deduced easily).