Okay, linear programs are amazing things! And okay, L1 minimization and related sparse methods are magical. But can these be related? I always thought “no!” After all, the L1 norm involves an absolute value operator, and that isn't linear; linear programs are linear (it's in the name!). But today Soledad Villar (JHU) blew me away with the following (retrospectively simple) observation: If you augment any variable that you are going to L1 (that variable could be a parameter or a residual) with an auxiliary variable that is constrained to be greater than both the original variable and also the variable multiplied by negative one, then you can set up linear programs such that the auxiliary variables become the absolute values of their associated varaibles. And the optimization performed by the linear program becomes an L1 optimization. It's beautiful, we coded it up today in a few different contexts, and it worked!
No comments:
Post a Comment