2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is "SPAMS"? Is that from some software (eg, MATLAB)? $\endgroup$ – gung - Reinstate Monica Jan 13 '15 at 20:56
  • $\begingroup$ Yes,it is SPArse Modeling Software and widely used $\endgroup$ – Elyor Jan 13 '15 at 20:58
  • $\begingroup$ I just want to know the reformulation of (2) using algebraic or linear algebra manipulation. $\endgroup$ – Elyor Jan 13 '15 at 21:06
  • $\begingroup$ what does your $\alpha_{other}$ stand for? Do you have any concrete application about your formulation (2)? $\endgroup$ – Aaron Zeng Jan 14 '15 at 4:30
  • $\begingroup$ @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 $\endgroup$ – Elyor Jan 14 '15 at 9:32
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.