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

Question

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?

Answer 1

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.

For more details about the soft-thresholding operator of LASSO, refer to this thread. For more information about the geometric representation, check here.

Hope this might help a little bit.

Answer 2

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.

Despite that, some operator splitting approach will be able to solve this problem using the LASSO solver.