# Aiding Dictionary Learning Through Multi-Parametric Sparse Representation
## 3 Analysis of the Multi-Parametric Formulation Induced by the DL Problem
### Karush-Kuhn-Tucker Form  
The second particularity of (10) (or, equivalently, of (14)) is that the optimization depends on parameter \(\mathbf{y}\). Inspired by the approach followed in explicit MPC constructions [9] (and which, to the best of our knowledge, has no equivalence in the dictionary learning state of the art), we propose to provide an explicit description of the optimal solution in terms of parameter \(\mathbf{y}\). The first step is to rewrite (14) in its dual form (i.e., the Karash-Kuhn-Tucker representation--see [2] or any standard optimization book for a more in-depth description):  
stationarity: \[\
abla\left(\|\mathbf{y}-\mathbf{T}\mathbf{F}\mathbf{\alpha}\|_{2}^{2}\right)+ \
abla\left(-\mathbf{\alpha}\right)\cdot\mathbf{\lambda}+\
abla\left(\mathbf{1}^{\top}\mathbf{ \alpha}\right)\cdot\mu=0,\] (15a) primal feasibility: \[-\mathbf{\alpha}\leq 0,\ \mathbf{1}^{\top}\mathbf{\alpha}=\delta,\] (15b) dual feasibility: \[\mathbf{\lambda}\geq 0,\] (15c) complementarity: \[\mathbf{\lambda}\times(-\mathbf{\alpha})=0.\] (15d)  
The \(\
abla\) operator denotes the gradient operation applied for: the cost, the inequalities and the equality appearing in the primal problem (14). \(\mathbf{\lambda}\in\mathbb{R}^{2n}\) and \(\mu\in\mathbb{R}\) are the Lagrangian multipliers (also called dual variables) associated with the inequalities, respectively the equality constraint of (14). '\(\times\)' denotes the complementarity condition which requires that either the i-th Lagrangian multiplier \(\lambda_{i}\) is zero or the i-th inequality is active (\(-\alpha_{i}\leq 0\mapsto-\alpha_{i}=0\)). Applying the gradient, the KKT form (15) becomes  
\[2\left(\mathbf{T}\mathbf{F}\right)^{\top}\cdot\left(\mathbf{T}\mathbf{F}\mathbf{ \alpha}-\mathbf{y}\right)-\mathbf{\lambda}+\mathbf{1}\mu=0, \tag{16a}\] \[\mathbf{\lambda}\geq 0,\ -\mathbf{\alpha}\leq 0,\ \mathbf{1}^{\top}\mathbf{ \alpha}=\delta,\] (16b) \[\mathbf{\lambda}\times(-\mathbf{\alpha})=0. \tag{16c}\]  
Under [PERSON]'s conditions of optimality [2], the primal variable \(\mathbf{\alpha}\) and dual variables \(\mathbf{\lambda},\mu\) verifying (16) describe the optimum (primal and dual). Using the well-known result that \(\text{rank}(AB)\leq\min(\text{rank}(A)\,\text{rank}(B))\) and that for a matrix \(A\in\mathbb{R}^{r\times q}\), \(\text{rank}(A)\leq\min(r,q)\), we have that \(\text{rank}(\mathbf{T}\mathbf{F})\leq\min\left(\min(m,n),\min(n,2n)\right)=\min(m,n)\). Thus, the semi-definite matrix \(\left(\mathbf{T}\mathbf{F}\right)^{\top}\mathbf{T}\mathbf{F}\) appearing in (16a) is rank-deficient (is a square matrix of dimension \(2n\) but its rank is at most \(\min(m,n)\)). Hereinafter, we consider (the opposite case would unfold in the same manner and is not followed here) that \(m\leq n\) and proceed accordingly (i.e., \(\min(m,n)=m\)). As a next step, we consider the SVD decomposition \(\mathbf{T}\mathbf{\Delta}=\mathbf{U}\mathbf{\Sigma}\mathbf{W}^{\top}\) with \(\mathbf{U}\in\mathbb{R}^{m\times m}\) and \(\mathbf{V}\in\mathbb{R}^{n\times n}\) orthogonal matrices and \(\mathbf{\Sigma}\in\mathbb{R}^{m\times n}\) the matrix containing the singular values of \(\mathbf{T}\mathbf{\Delta}\). This decomposition allows for writing \(\mathbf{T}\mathbf{F}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{\top}\), where \(\mathbf{V}^{\top}= \begin{bmatrix}\mathbf{W}^{\top}&-\mathbf{W}^{\top}\end{bmatrix} \in \mathbb{R}^{n\times 2n}\). For further use, we consider the decompositions \(\mathbf{\Sigma}= \begin{bmatrix}\mathbf{\Sigma_{1}}&\mathbf{0}\end{bmatrix} \) and \(\mathbf{V}^{\top}= \begin{bmatrix}\mathbf{V_{1}}&\mathbf{V_{2}}\end{bmatrix} ^{\top}\), where \(\mathbf{\Sigma_{1}}\in\mathbb{R}^{m\times m}\) and \(\mathbf{V}_{1}^{\top}\in\mathbb{R}^{m\times 2n}\), \(\mathbf{V}_{2}^{\top}\in\mathbb{R}^{(n-m)\times 2n}\).