RE: [Help-glpk] Book recommendations

[Meketon, Marc]

[On a plane flight and obviously bored, so here's a much longer answer
than I would ordinarily give to your question about any comments on Bob
Vanderbei's LP book regarding L1.]

Bob's book gives an interesting discussion on L1.  I don't have it in
front of me, but if I recall it doesn't mention the relationship between
affine scaling methods and iteratively re-weighted least squares for
solving L1.

An easy approach to solving L1 is to first solve the L2 regression
problem (what we all call "least squares") and then continue to resolve
the L2 problem with weights that are the inverse of the residuals.

Specifically, find the least squares solution to Y = Xb + e (e is the
vector of error terms, typically thought of as being an IID vector of
normal-distributed random variates with mean 0 and common standard
deviation of "sigma").  Y is an n-vector of dependent observations, X is
an n x m vector of independent variables, b is an m-vector of unknowns.

The solution, b*, solves the normal equations of XtXb* = Xty  Here Xt is
the transpose of X.

b* solves the minimum of the sum{j in 1..n} ( y[j] - sum{i in 1..m}
x[j,i]*b[i])^2

Let R = Y - Xb*, called the residuals.  Examine the weighted least
squares problem of

  sum{j in 1..n} [( y[j] - sum{i in 1..m} x[j,i]*b[i])^2]/abs(r[j])

The idea is that if we first solve the ordinary least squares problem,
calculate the residuals, then use the residuals to solve the above
weighted least squares problem (whose solution solves the modified
normal equations of XtDXb* = XtDy, where D is diag(1/r[j]) [the diagonal
matrix with the inverse of the residuals on the diagonal]), we would get
close to solving the L1 norm.  If you iterate a few times, the algorithm
generally converges.

To see this more intuitively, let R(b) = Y-Xb, and each element of R(b)
is r[j,b].  If on the kth iteration we have a solution bk, then the next
iteration is to solve

  sum{j in 1..n} r[j,b]^2/|r[j,bk]|

Which looks a lot like the L1 norm of

  sum{j in 1..n} |r[j,b]|

An alternative approach is to take the dual of the L1 problem as defined
by linear programming (and I believe that Bob also looks at the dual):

Find the n-vector W so that

  max YtW

  subject to XtW = 0

And
  -1 <= w[j] <= 1

If you work this out using affine scaling, you would get that the
algorithm to solve this is also an iterative weighted least squares
problem of the same size and type as above, but the diagonal matrix D
has elements always strictly between 0 and 1.  If I recall, at the kth
iteration of affine scaling method, there is a solution Wk, and to get
the next solution set D = diag(1-|wk[j]|), then solve XtDX bk = XtDY,
and W(k+1) = the k+1st iteration = Wk - s*(I - inv(XtDX) bk)

Of course, affine scaling isn't the best algorithm (Bob's book does a
good job at discussing that), but you could also use the primal-dual,
predictor-corrector method and still work it out so that each step is
just a weighted least squares step.  And, back to the first paragraph,
it would have been nice (in my not-so-humble opinion) if Bob's book
talked more about that connection.  And maybe it does, I just don't have
it with me at the moment.

I end this with an exercise for the reader:  if p and q are conjugate
(1/p + 1/q = 1), then the dual to the Lp regression problem is:

  max YtW

  subject to XtW = 0

and
  ||W||q <= 1

-Marc
-----Original Message-----
From: address@hidden
[mailto:address@hidden On
Behalf Of Reginald Beardsley
Sent: Friday, August 13, 2010 12:23 PM
To: address@hidden
Subject: [Help-glpk] Book recommendations

Many thanks to Marc for getting me pointed in the right direction.

L1 methods only got a passing nod in my inverse theory class 20 years
ago.  It's become painfully obvious I have very little idea of how to do
this well.

Most of my references are pretty dated, so I'm looking for
recommendations.  My interest is in L1 solutions to linear and nonlinear
regression problems.   Amazon turned up Robert Vanderbei's book.  Does
anyone have any comments or other suggestions?

thanks,
Reg


      

_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
---------------------------------------------------------------------------- 
This e-mail and any attachments may be confidential or legally privileged.  If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 

Thank you for your cooperation.
----------------------------------------------------------------------------