# Aiding Dictionary Learning Through Multi-Parametric Sparse Representation
## 3 Analysis of the Multi-Parametric Formulation Induced by the DL Problem
### Multi-Parametric Interpretation  
The difficulty of solving (16), even when making use of (17), lies in the complementarity condition (16c). There are multiple formulations in the literature [4; 8; 10], each proposing a particular 'flavor'. In what follows, we make use of one of the most common approaches: the _active set_ method [6]. This approach enumerates (the selection of sets of active constraints and the stop criteria for the search of feasible combinations are subject to significant research and still an open topic [14]) combinations of active (those for which \(\lambda_{i}>0\)) and inactive constraints (those for which \(\lambda_{i}=0\)). Subsequently, problem (16) is solved for each of the particular combinations of active constraints. As a first step, we form submatrices associated with the active/inactive set of constraints (\(\widetilde{(\cdot)}\) for those corresponding to active constraints and \(\widetilde{(\cdot)}\) for those corresponding to inactive constraints (for example, \(\tilde{\mathbf{V}}_{2}^{\top}\) is the matrix constructed from the columns of \(\mathbf{V}_{2}^{\top}\) which correspond to active constraints--those for which \(\tilde{\alpha}_{i}=0\)) and reformulate (16) correspondingly:  
\[ \begin{bmatrix}\tilde{\mathbf{V}}_{1}^{\top}\\ \mathbf{1}^{\top}\end{bmatrix} \hat{\mathbf{\alpha}}- \begin{bmatrix}\left(\mathbf{\Sigma} _{1}^{-1}\right)^{\top}\mathbf{U}^{\top}\mathbf{y}+\frac{1}{2}\left(\mathbf{\Sigma}_{1}^{ -2}\right)^{\top}\left(\tilde{\mathbf{V}}_{1}^{\top}\tilde{\mathbf{\lambda}}-\mathbf{V}_{ 1}^{\top}\mathbf{1}\mu\right)\end{bmatrix}  =0, \tag{18a}\] \[\tilde{\mathbf{V}}_{2}^{\top}\tilde{\mathbf{\lambda}}-\mathbf{V}_{2}^{\top} \mathbf{1}\mu =0,\] (18b) \[\tilde{\mathbf{\lambda}}>0,\,\tilde{\mathbf{\alpha}} =0,\] (18c) \[\hat{\mathbf{\lambda}}=0,\,\hat{\mathbf{\alpha}} >0. \tag{18d}\]  
We note with \(\tilde{m},\tilde{m}\) the number of active, respectively inactive, constraints (hence \(\tilde{m}+\tilde{m}=n\)). At this stage, most multi-parametric formulations employ various heuristics for the selection of the set of active constraints [5; 8] and solve (18). We proceed similarly with the observation that the cardinality of the set of active constraints has to lead to a well-defined problem (18). In other words, we expect that \(\tilde{m}\leq m+1\) (i.e., the number of rows in the matrix left-multiplying \(\hat{\mathbf{\alpha}}\) in (18a) is at least equal with the number of columns, which means that the matrix admits a full-rank pseudo-inverse). Having to accommodate the case \(\hat{m}<m+1\) requires a further partitioning of the matrices appearing in (18), this time in row-blocks: we add the subscript '1' for the sub-matrices formed from the first \(\hat{m}-1\) rows and subscript '2' for the sub-matrices formed from the remaining \(m-\hat{m}+1\) rows. Note that, as before, the partitioning is not unique and any permutation which does not change the number of rows is admissible. For example, \(\tilde{\mathbf{V}}_{1}^{\top}\in\mathbb{R}^{m\times\hat{m}}\) is partitioned into \(\tilde{\mathbf{V}}_{1}^{\top}= \begin{bmatrix}\hat{\mathbf{V}}_{11}&\tilde{\mathbf{V}}_{ 12}\end{bmatrix} ^{\top}\) where \(\tilde{\mathbf{V}}_{11}^{\top}\in\mathbb{R}^{(\hat{m}-1)\times\hat{m}}\) and \(\tilde{\mathbf{V}}_{12}^{\top}\in\mathbb{R}^{(m-\hat{m}+1)\times\hat{m}}\). With these notations, (18a)-(18b) become:  
\[ \begin{bmatrix}\tilde{\mathbf{V}}_{11}^{\top}\\ \mathbf{1}^{\top}\end{bmatrix} \hat{\mathbf{\alpha}}- \begin{bmatrix}\left(\mathbf{\Sigma} _{11}^{-1}\right)^{\top}\mathbf{U}^{\top}\mathbf{y}+\frac{1}{2}\left(\mathbf{\Sigma}_{11 }^{-2}\right)^{\top}\left(\tilde{\mathbf{V}}_{1}^{\top}\tilde{\mathbf{\lambda}}-\mathbf{V }_{1}^{\top}\mathbf{1}\mu\right)\end{bmatrix}  =0, \tag{19a}\] \[\tilde{\mathbf{V}}_{12}^{\top}\hat{\mathbf{\alpha}}-