3
$\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$
4
  • $\begingroup$ Is the $\leq$ pairwise? $\endgroup$ Commented Sep 16, 2015 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
    Commented Sep 16, 2015 at 22:16
  • $\begingroup$ @CliffAB actually, the non-differentiability of the 1-norm isn't a problem at all. See my answer below. $\endgroup$ Commented Sep 17, 2015 at 3:52
  • $\begingroup$ @BrianBorchers interesting. What does $t$ refer to? $\endgroup$
    – Cliff AB
    Commented Sep 17, 2015 at 5:34

3 Answers 3

4
$\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$
5
  • $\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
    Commented Sep 18, 2015 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$ Commented Sep 18, 2015 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
    Commented Sep 21, 2015 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$
    – Danica
    Commented Sep 21, 2015 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
    Commented Sep 24, 2015 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$
1
  • $\begingroup$ @ Dougal- Thank you for informing me about that Lasso research. I'd definitely try it out! $\endgroup$
    – Bob
    Commented Sep 21, 2015 at 9:14
0
$\begingroup$

As of writing a similar note on lasso in QP, which follows the same approach as in the answer of Brian Borchers, I also ran into non-strictly convex problems, i.e. where the Hessian matrix in the objective function is semidefinite (not definite) positive. When this happens it can be worth switching to a QP solver that handles non-strictly convex problems, for instance augmented-Lagrangian solvers like ProxQP or QPALM (bias disclaimer: I work in the team at Inria that develops ProxQP), or interior-point solvers like Clarabel.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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