2
$\begingroup$

I want to solve a sparse coding problem with the conventional form:

$\arg \min (||y-dX||_2)^2+ \lambda ||X||_1$

$s.t.:$

$0 \leq X \leq b$

For the moment I am work on the sparsity problem assuming that $d$ ($1\times n$) is fixed and I want to find the best $X$ which is $n \times m$ to the above problem. The problem is that in the literature I couldn't find a good algorithm which solve the sparse problem with constraints like above!

$\endgroup$
  • $\begingroup$ Is the $\leq$ pairwise? $\endgroup$ – jlimahaverford Sep 16 '15 at 14:40
  • $\begingroup$ I think this is going to be a fairly difficult problem, particularly because the objective function is not differentiable. As such, I would guess that there's no generic algorithm for it (like SQP which could be easily used with an $L_2$ error). $\endgroup$ – Cliff AB Sep 16 '15 at 22:16
  • $\begingroup$ @CliffAB actually, the non-differentiability of the 1-norm isn't a problem at all. See my answer below. $\endgroup$ – Brian Borchers Sep 17 '15 at 3:52
  • $\begingroup$ @BrianBorchers interesting. What does $t$ refer to? $\endgroup$ – Cliff AB Sep 17 '15 at 5:34
3
$\begingroup$

Unfortunately, this isn't one of the simpler types of problems commonly encountered in compressive sensing for which specialized methods have been developed.

However, it's quite straight forward to formulate this as a convex quadratic programming problem with linear inequality constraints:

$\min (y-Dx)^{T}(y-Dx)+\lambda e^{T}t$

subject to

$x \leq t$

$-x \leq t$

$Ax \leq b$

Here $e$ is the vector of all ones. $e^{T}t=\sum_{i=1}^{n} t_{i}$.

The vector of auxiliary variables $t$ is added as a way of moving the L1 norm out of the objective function and into the constraints. The constraints ensure that $t_{i} \geq | x_{i} |$ for $i=1, 2, \ldots, n$. Since the $t$ variables don't appear elsewhere in the problem, and we're minimizing the sum of the $t_{i}$, this ends up minimizing $\| x \|_{1}$. This "epigraph trick" is a standard method for dealing with minimization of 1-norm terms in convex optimization.

Depending on the relative sizes and density of $A$, $D$, $x$ and $y$ this could be solvable by standard QP software. Just how big and dense are your instances?

$\endgroup$
  • $\begingroup$ Thank you Brian. But I've already tried QP formulation. It seems my problem is not convex according to specific form of vector x that I have in my problem. $\endgroup$ – Bob Sep 18 '15 at 11:57
  • 1
    $\begingroup$ @Bob- I'm afraid that you've made an error in getting the problem into your QP software. The objective function that I gave is always convex, because it's the sum of two terms, the first of which is a convex quadratic form and the second of which is linear. We might be able to help if you provided the specific error message and told us what software you were using for the QP. $\endgroup$ – Brian Borchers Sep 18 '15 at 14:33
  • $\begingroup$ @ Brian. Actually in my problem $y$ and $d$ are both vectors ($1\times l$ and $1\times m$) and $X$ is a matrix ($m\times l$) and when i tried to formulate it to the common quadratic form i ended up with $$dXX^{T}d^{T}$$. So i decided to use $vec(X)$ to treat $X$ as a vector which lead to having the following QP form: $$x^{T}Hx+2f^{T}x+r$$ in which the $H$ is block diagonal form and also not positive semi-definite! $\endgroup$ – Bob Sep 21 '15 at 9:10
  • $\begingroup$ What is $X$? In the original notation of the problem, just use $x^T \underbrace{D^T D}_{H} x+ \underbrace{-2 y^T D}_{f^T} x + \lambda e^T t$. $H$ is guaranteed psd; you can get $x$ and $t$ from a vector $z$ of their concatenation by throwing in an appropriate diagonal 0-1 matrix. If that's not what you're doing, you should edit the question to reflect what you're actually doing.... $\endgroup$ – Dougal Sep 21 '15 at 14:19
  • $\begingroup$ Following is the Matlab code i used for QP: % X is 10x20 d=rand(1,10); y=rand(1,20)'; %% problem formulation % ||y-dX||==> 1/2*x'Hx + f'x + (constant parts) p=length(d) l=length(y) for i=1:l H0(p*(i-1)+1:pi,i)=d; end H=full(2*H0*H0'); f=(-2*H0*y); %% checking the analytical formulation x0=rand(size(d,2),length(y)); xinit=x0(:); check1=xinit'Hxinit/2-norm(dx0)^2 check2=sum(-2*(dx0)*y)-f'xinit %% opt = quadprog(H,f,[], [], [], [],[],[]); xn=reshape(opt,size(x0)); norm_err=(norm(dxn - y')^2) $\endgroup$ – Bob Sep 24 '15 at 7:56
1
$\begingroup$

Your optimization problem is equivalent to adding linear inequality constraints to the Lasso regression problem. Luckily, someone wrote a paper about that:

James, Paulson, and Rusmevichienton. The Constrained Lasso. Tech report, USC, 2013.

They give a modification of the standard coordinate descent algorithm for Lasso to account for the inequalities.

You could also formulate it for general-purpose solvers, which will probably be less work for you and may or may not be fast enough. Brian's answer gives one approach; here's an example of someone doing it in TFOCS.

$\endgroup$
  • $\begingroup$ @ Dougal- Thank you for informing me about that Lasso research. I'd definitely try it out! $\endgroup$ – Bob Sep 21 '15 at 9:14

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.