# Aiding Dictionary Learning Through Multi-Parametric Sparse Representation
## 4 Integration of the Multi-Parametric Formulation in the Representation Problem
### On the Multi-Parametric Interpretation of the 'Given Approximation Quality' Case  
For simplicity, we discuss only the sparse representation case shown in (7). The cosparse case (9) can be treated similarly and is not detailed here.  
Recall that, as stated in Section 2, the \"true\" DL formulations are those shown in (1) and (7) where the \(\ell_{0}\) norm appears (either explicitly in the first case or implicitly in the second case). Thus, all of the other formulations appearing in Section 2 are relaxations (exploiting the sparsity induced by the \(\ell_{1}\) norm, appearing either in the cost or as a constraint) which aim to simplify the computational effort.  
Until here, we have concentrated on these forms where the \(\ell_{1}\) norm appears in the constraint part of the optimization problem. Now, we mention some of the drawbacks and possible solutions for the other class of relaxations (those for which the \(\ell_{1}\) norm appears in the cost). First, we consider an over-approximation of the quadratic constraint. Any ellipsoid (and therefore the ball \(\|\mathbf{y}-\mathbf{D}\mathbf{x}\|_{2}^{2}\leq\epsilon\)is a convex set, which by definition means that it can be approximated arbitrarily well by a polyhedral set [18], say, a construction like  
\[\{\mathbf{x}:\;\mathbf{F}(\mathbf{D}\mathbf{x}-\mathbf{y})\leq\theta\}\subset\{\mathbf{x}:\;\|\mathbf{y}-\bm {D}\mathbf{x}\|_{2}^{2}\leq\epsilon\}\subset\{\mathbf{x}:\;\mathbf{F}(\mathbf{D}\mathbf{x}-\mathbf{y}) \leq(1+\epsilon)\theta\}, \tag{28}\]  
with \(F,\theta\) appropriately chosen.  
Proceeding as in Section 3, we arrive at the dual (KKT) form  
stationarity: \[\mathbf{0}\in\partial\left(||\mathbf{x}||_{1}\right)+\
abla(\mathbf{F}\mathbf{D} \mathbf{x}-\mathbf{F}\mathbf{y}-\theta)\cdot\lambda,\] (29a) primal feasibility: \[\mathbf{F}\mathbf{D}\mathbf{x}-\mathbf{F}\mathbf{y}-\theta\leq 0,\] (29b) dual feasibility: \[\mathbf{\lambda}\geq 0,\] (29c) complementarity: \[\mathbf{\lambda}\times(\mathbf{F}\mathbf{D}\mathbf{x}-\mathbf{F}\mathbf{y}-\theta)=0.\] (29d) There are several issues that make (29) challenging to solve as in Section 3:  
1. the gradient is not well defined in inflexion points (where at least one of the vector's components is zero); this requires the use of the'sub-gradient' notion which is set-valued (29a) becomes '\(\mathbf{0}\in\text{sign}(\mathbf{x})+(\mathbf{F}\mathbf{D})^{\top}\cdot\mathbf{\lambda}\)', where \[\text{sign}(x_{i})=\begin{cases}1,&x_{i}>0,\\ -1,&x_{i}<0,\\ \left[-1,1\right],&x_{i}=0.\end{cases}\]
2. the problem may be relatively large (depending on the number of inequalities used to over-approximate the initial quadratic constraint).  
**Remark 10**.: _An alternative to item 4.3 is to consider a zonotopic representation of the quadratic constraints. The ellipsoid they describe is in fact a zonoid (a set which can be approximated arbitrarily well by a zonotope [20]). The advantage of this method is that, in generator representation, a zonotope has a much more compact form (which directly leads to a reduced KKT form)._