min L1 norm of P*u -q

[Ether Jones]

Hello.

I have an overdetermined linear system P*u = q + eps,

P is m by n, m > n.

u is n by 1.

q and eps are m by 1.

P and q are known; u and eps are unknown.


I want to find u which minimizes the L1 norm of eps;
in other words I want to minimize ||P*u-q||1

I do *not* want u to be constrained to be >= 0.

It's not clear to me how to solve this in Octave.

The objective is not smooth so that appears to rule out Octave's sqp().

The objective is not linear so that *appears* to rule out Octave's glpk().



However...

According to this web page:

http://cvxopt.org/examples/mlbook/l1.html

... minimizing ||P*u-q||1 is equivalent to the LP problem:

minimize 1'v
subject to
[P, -I; -P, I]*[u; v] <= [q,-q]

with m+n variables and 2m constraints.


And according to the Octave manual,

glpk() can solve problems of the form:

[ min | max ] C'*x

subject to

A*x [ "=" | "<=" | ">=" ] b
  x >= LB
  x <= UB


So if I create:

I = m by m identity matrix

A = [P, -I; -P, I]

x = [u; v]

b = [q; -q]

c = a vector of 1's of size m

... then I should be able to pass c, A, b, LB=0, UB=0 to glpk():

glpk (c, A, b, lb, ub, ctype, vartype, sense, param)


Does this sound correct so far?


My questions are:

1) Is there a better (more straightforward) way to do this?

2) Do I have to initialize v to something, and if so, what?

3) What should the glpk() arguments ctype, vartype, sense, and param be set to?


Thank you.