# Aiding Dictionary Learning Through Multi-Parametric Sparse Representation  
[PERSON]  
1 Department of Automatic Control and Computers, University Politehnica of Bucharest, 313 Spl. Independenteti, 060042 Bucharest, Romania 11 Department of Automatic Control and Computers, University Politehnica of Bucharest, 313 Spl. is to be represented. This has led us to consider a multi-parametric interpretation where the vector \(\mathbf{y}\) becomes a parameter which governs the optimization's problem solution and its domain of validity. While the multi-parametric approach is well-known in the optimization field [2], to the best of our knowledge, it appears not to have been employed by the dictionary learning (DL) community. Conceptually, the idea is simple: instead of solving repeatedly very similar optimization problems (with the same structure and differing only in the current value of a parameter), we instead break the problem into two distinct stages:  
1. the offline stage: find the way in which the optimal solution depends on parameter \(\mathbf{y}\) and store this information for later use in the online stage;
2. the online stage: for the current value of \(\mathbf{y}\), retrieve and apply the a priori computed solution. Further assume that the cost is quadratic and the constraints linear leads, in the offline stage, to a piecewise formulation with a polyhedral support [3; 4]. That is, the optimal solution is an affine law in parameter \(\mathbf{y}\) which is active on a so-called polyhedral _critical region_. Enumerating [5] all these disjoint critical regions covers completely the parameter space (or the restriction over which \(\mathbf{y}\) is defined). Thus, at the online stage, it remains only to find the region in which the current \(\mathbf{y}\) lies [6; 7; 8], retrieve the associated affine law and apply it. For further details with a practical bent, see the survey [9] which deals with the subtleties of multi-parametric problem in the context of _explicit MPC_. As a first step, we rewrite the sparse representation problem in its dual form (Karash-Kuhn-Tucker) in order to enumerate sets of active constraints from which the piecewise affine law and its polyhedral support are deduced. A couple of issues differentiate this approach from other formulations encountered in the literature (e.g., [8; 10] which solve a generic complementarity problem):  
1. the cost from the constrained optimization problem is rank-deficient (the dictionary is over-determined which means that the quadratic cost is defined by a semi-definite matrix);
2. the \(\ell_{1}\) norm used here (as a relaxation from the sparse restriction induced by the \(\ell_{0}\) norm) leads to a very-particular set of linear constraints (they define a cross-polytope, whose structure influences the optimization problem formulation [11]). Tackling these issues leads to a particular multi-parametric formulation and represents the main contribution of this paper (beyond the usage of the multi-parametric formalism in the DL context):  
1. The first issue requires a careful decomposition of the matrices (in order to avoid degeneracy in the formulations [12]); the upshot is that the particular KKT representation appears in a simple form (which allows simple matrix decompositions). 2. The second requires to consider a vertex-representation of the cross-polytope (as this is a more compact representation than its equivalent half-space representation [13]). In general, the opposite is true: to a reasonable number of linear inequalities corresponds a significantly larger number of vertices. Thus, most if not all of space partitioning induced by the multi-parametric representation exploit the \"half-space\" description of the feasible domain [9]. 3. We highlight a compact storage and retrieval procedure (which exploits the symmetry of the cross-polytope domain) with the potential to significantly reduce the numerical issues.