1
$\begingroup$

Minimizing the following SVM formulation \begin{align} \arg\min_{\mathbf{w}}\frac{1}{2}\|\mathbf{w}\|^2_2 \\ \text{subject to } \quad y_i(\mathbf{w}\cdot\mathbf{x_i}) \ge 1 \end{align} can be done quite easily in MATLAB:

%% problem setup
n = 200;
d = 2;
X = mvnrnd(5*ones(d,1),0.3*eye(d),n/2);
y = ones(size(X,1),1);
X = [X; -X];
y = [y; -y];

%% algorithm
[n,d] = size(X);
H = diag(ones(d,1));
f = zeros(d,1);
A = diag(-y)*X;
b = -ones(n,1);
w = quadprog(H,f,A,b);

where $X$ is a matrix of $x_i$ and $y$ a vector containing $y_i$, $n$ being the number of samples and $d$ the dimension.

I am looking for an example to minimize the L1 regularized version in MATLAB: \begin{align} \arg\min_{\mathbf{w}}\frac{1}{2}\|\mathbf{w}\|_1 \\ \text{subject to } \quad y_i(\mathbf{w}\cdot\mathbf{x_i}) \ge 1 \end{align} Is there a way to do it (maybe with linprog)?

$\endgroup$
  • 3
    $\begingroup$ The standard way to include two constraints for each $w_i$: $w_i \le t_i$ and $-w_i \le t_i$. Then you minimize $\sum_i t_i$ instead of the $L_1$ norm. The $w_i$ still stay variables, but they are not part of the objective (or have coefficient $0$). $\endgroup$ – fabee Jul 22 '14 at 12:56
  • $\begingroup$ @fabee Thx. I get the exact same result as with the L2 norm. Shouldn't I see a sparse (or at leas different) solution? f = [zeros(d,1); ones(d,1)]; A = [diag(y)*X zeros(n,d);[eye(d) -eye(d); -eye(d) -eye(d)]]; b = [b; zeros(2*d,1)] $\endgroup$ – Manuel Schmidt Jul 22 '14 at 14:42
  • 1
    $\begingroup$ Not necessarily, no. The 1-norm tends towards sparsity but there are no guarantees of this in the general case. It would seem that your problem is sufficiently constrained that the choice of objective function does not have a significant impact. Besides, $w$ is dimension 2, right? What does sparsity even mean in that case? $\endgroup$ – Michael Grant Jul 22 '14 at 15:38
2
$\begingroup$

If you're willing to use my toolbox CVX, then it's as simple as this:

cvx_begin
    variable w(d)
    minimize(0.5*norm(w,1))
    subject to
        diag(y) * X * w >= 1;
cvx_end

But yes, fabee's comment is a valid option as well; he should promote it to an answer so it can be voted up.

$\endgroup$
  • $\begingroup$ Works as described. Easy setup, nice toolbox! $\endgroup$ – Manuel Schmidt Jul 23 '14 at 6:29
0
$\begingroup$

Just for completion here is the code I used to implement fabees solution:

f = [zeros(d,1); ones(d,1)];
A = [diag(-y)*X zeros(n,d)
    [eye(d) -eye(d); -eye(d) -eye(d)]];
b = [-ones(n,1); 1*ones(2*d,1)];
p = linprog(f, A, b);
w = p(1:length(p)/2);
$\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.