How to convert the objective function to canonic form of sparse coding?

As we know the conventional sparse coding problem (LASSO) is:

$\min_{\alpha} \| X-D\alpha\|_F^2 + \lambda \|\alpha\|_{1} \tag{1}$

where $X$ , $D$, and $\alpha$ are data, dictionary and coefficients matrices, respectively. There are many toolboxes to solve this problem, e.g., SPAMS.

However, when I want to add another objective function to this formulation. For example,

$\min_{\alpha} \| X-D\alpha\|_F^2 + \lambda_1 \|\alpha_{other}-\alpha\|_{1} + \lambda_2 \|\alpha\|_{1} \tag{2}$

How can I transform $(2)$ to conventional sparse coding $(1)$ mentioned above so that I can apply SPAMS toolbox?

• What is "SPAMS"? Is that from some software (eg, MATLAB)? – gung - Reinstate Monica Jan 13 '15 at 20:56
• Yes,it is SPArse Modeling Software and widely used – Elyor Jan 13 '15 at 20:58
• I just want to know the reformulation of (2) using algebraic or linear algebra manipulation. – Elyor Jan 13 '15 at 21:06
• what does your $\alpha_{other}$ stand for? Do you have any concrete application about your formulation (2)? – Aaron Zeng Jan 14 '15 at 4:30
• @Aaron Lets assume $D$, $X$ $\alpha_{other}$ are given, and I want to reconstruct coefficients using additional constraint with $\alpha_{other}$. alpha_other is prior knowledge about about alpa – Elyor Jan 14 '15 at 9:32

I have no answer to your question. But here might be what you can start with. Your formulation $$\min_{\alpha} \| X-D\alpha\|_F^2 + \lambda_1 \|\alpha_{other}-\alpha\|_{1} + \lambda_2 \|\alpha\|_{1} \tag{2}$$ can be transformed back into the constrained optimization problem with two constraints, $$\min_{\alpha} \| X-D\alpha\|_F^2 \\ s.t. \begin{cases} \|\alpha_{other}-\alpha\|_{1} \leq s_1 \quad & (a)\\ \|\alpha\|_{1} \leq s_2 \quad & (b) \end{cases}$$

Consider a simple problem where $\alpha$ is of 2 dimension (then $\alpha_{other}$ is also 2-dimensional). Geometrically, constraint (b) defines the feasible region to be a diamond centered at the origin. And constraint (a) forces the feasible region to be another diamond with the center at point $\alpha_{other}$. That is, in your formulation, the feasible solution would be the intersect of the two diamond.

I am not sure how the SPAMS toolbox solves the LASSO problem. As for as I see, the existing algorithms are based on the theoretic soft-shareholding solution to LASSO. So you might also want to derive the theoretic solution to your problem analogously and then figure out how you can employ the toolbox, or write your own algorithm.

There exists some (not necessarily square) matrix $Q$ so that the constraint set $\mathcal{C} = \{\|x\|_1 \leq c_1, \|x-a\|_1 \leq c_2\} = \{\|Qx\|_\infty \leq c_1, \|Q(x-a)\|_\infty \leq c_2\}$. Then, by stacking these constraints, we see that $$\mathcal{C} = \{ \| \begin{bmatrix} \frac{1}{c_1} Q \\ \frac{1}{c_2} Q \end{bmatrix} x - \begin{bmatrix} 0 \\ a \end{bmatrix} \|_\infty \leq 1 \},$$ which may or may not be able to transform back to being a one norm, depending on the amount of redundancy in the constraints. In general, this is not an $\ell_1$ norm, though, and, unless the LASSO solver is quite general (and hence not very optimized), it will not be able to solve this problem.