L1 regularized SVM in Matlab

Question

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)?

Answer 1

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.

Answer 2

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);