10/20/2010

10-20-10 - Discrete Math is the Bane of Computer Science

We are constantly faced with these horrible discrete optimization problems.

The specific example I've been working on today is YCbCr/YUV optimization. Say you know the reconstruction matrix (YUV->RGB) and you want to find the optimal YUV coefficients for some given RGB ?

Well the standard answer is you invert the reconstruction matrix and then multiply that by your RGB. That is wrong!.

In general what we are trying to solve here is a problem something like this :


13 * x + 17 * y = 200;
11 * x +  7 * y = 100;

find x & y to minimize the error
x & y are integers
and bounded in [-100,100]

I guess these types of problems are "integer programming" (this particular case is integer linear programming since my example is linear, but sometimes we have to do it on nonlinear problems), and integer programming is NP-hard , so there is no exact solution but brute force.

(more generally, minimize error E(x,y,..) subject to various linear constraints)

The usual approach is just to wave your hands around and pretend that your variables are actually continuous, work out the math for the solution as if they were, and then round to ints at the end.

The problem is that that can be arbitrarily far from the optimal solution. Obviously in some simple problems you can bound the error of using this approach, or you may even know that this is the minimum error, but in nasty problems it might be way off.

We saw this same issue before in DXT1

I've never really seen many pages or much reference on this kind of problem. I did at one point decide that I was sick of the approximate hacky solutions and tried to find some software package to do this for real and came up empty on real usable ones.

There are a few hacky tricks you can use :

1. Find the continuous solution, then for each float value try clamping it to various integers nearby. See which of these rounds is best. The problem is for an N variable problem this takes 2^N tries if all you try is floor and ceil, and really you'd like to try going +1 and -1 beyond that a few times.

2. You can always remove one linear variable. That is, if you can reduce the problem to just something like a x = b, then the optimal integer solution is just round(b/a). What that means is if you use some other approach for all but one variable (such as brute force search), then you can solve the last variable trivially.

3. Often the importance of the various variables is not the same, their coefficients in the error term may vary quite a bit. So you may be able to brute force search on just the term with the largest contribution to the error, and use a simpler/approximate method on the other terms.

2 comments:

ryg said...

"I guess these types of problems are "integer programming" (this particular case is integer linear programming since my example is linear, but sometimes we have to do it on nonlinear problems)"
It's a linear system but you didn't give your target function. ILP (like LP) only considers linear target functions which aren't very useful in this context. What you probably really want is Integer Least Squares.

NP-hard doesn't mean much in this context. Basically all of the general integer optimization problems are, but that's for two reasons: (1) in general, finding even one viable point that satisfies the constraints is NP-hard and (2) there's degenerate configurations that essentially force you to look at all grid points. (1) is a non-issue in our case - our constraints just select and integer cube. (2) is a bit more subtle: the complexity in any kind of exact discrete optimization task starts to explode once your problem gets close to singular - e.g. consider a 3-dimensional "grid" with the basis vectors very similar to each other. The continuous version of that problem just is ill-conditioned and numerically tricky to solve. The discrete version has the added complication that even a tiny sphere around some grid point will contain a significant fraction of the whole grid, which of course royally screws you.

That's the fundamentally hard cases where the complexity comes from. It's also cases we don't care about too much - essentially, if there's a really large number of points within a small neighborhood of your initial solution (presumably obtained from the continuous problem), there's little to gain from solving it to optimality.

There's also this paper. In short, under conditions that are fairly similar to what you're trying to do, the actual observed runtime of one particular (relatively simple) ILS solver is polynomial.

cbloom said...

Yeah .. I need to do some more reading.

BTW integer linear feasability does come up in one important problem for us - rasterization. If you have a polygon and ask if any integer pixel centers fall inside it.

old rants