Lasso

Consider the Lasso problem

\[ \text{minimize} ~\|A x - b\|_2^2 + \lambda \|x\|_1, \]

which has the graph form representation

\[ \begin{aligned} &\text{minimize} & & \|y - b\|_2^2 + \lambda \|x\|_1 \\
& \text{subject to} & & y = A x. \end{aligned} \]

or equivalently

\[ \begin{aligned} &\text{minimize} & & f(y) + g(x) \\
& \text{subject to} & & y = A x, \end{aligned} \]

where

\[ f_i(y_i) = (1/2) (y_i - b_i) ^ 2, ~~\text{ and } ~~g_j(x_j) = \lambda |x_j|. \]

MATLAB Code

1
2
3
4
5
6
7
8
9
10
11
12
13
% Generate Data
A = randn(100, 10);
b = randn(100, 1);
lambda = 5;

% Populate f and g
f.h = kSquare;
f.b = b;
g.h = kAbs;
g.c = lambda;

% Solve
x = pogs(A, f, g);

This example can be found in the file 

1
<pogs>/examples/matlab/lasso.m
.

R Code

1
2
3
4
5
6
7
8
9
10
11
# Generate Data
A = matrix(rnorm(100 * 10), 100, 10)
b = rnorm(100)
lambda = 5

# Populate f and g
f = list(h = kSquare(), b = b)
g = list(h = kAbs(), c = lambda)

# Solve
solution = pogs(A, f, g)

This example can be found in the file 

1
<pogs>/examples/r/lasso.R
.

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <random>
#include <vector>

#include "pogs.h"

int main() {
  // Generate Data
  size_t m = 100, n = 10;
  std::vector<double> A(m * n);
  std::vector<double> b(m);
  std::vector<double> x(n);
  std::vector<double> y(m);

  std::default_random_engine generator;
  std::normal_distribution<double> n_dist(0.0, 1.0);

  for (unsigned int i = 0; i < m * n; ++i)
    A[i] = n_dist(generator);

  for (unsigned int i = 0; i < m; ++i)
    b[i] = n_dist(generator);

  // Populate f and g
  PogsData<double, double*> pogs_data(A.data(), m, n);
  pogs_data.x = x.data();
  pogs_data.y = y.data();

  pogs_data.f.reserve(m);
  for (unsigned int i = 0; i < m; ++i)
    pogs_data.f.emplace_back(kSquare, 1.0, b[i]);

  pogs_data.g.reserve(n);
  for (unsigned int i = 0; i < n; ++i)
    pogs_data.g.emplace_back(kAbs, 0.5);

  // Solve
  Pogs(&pogs_data);
}