ChapterZero

I’ve discovered, once again, the problem with using random test cases. I thought I’d come up with some nice manipulations that reduced the nonnegative least squares problem to a problem on a polytope (more relevantly, a bounded convex set), so I could apply any number of methods that have been developed for constrained minimization over bounded convex sets. When I tested one such algorithm in combination with my reduction, it gave wonderful results. But now, I’ve realized that my reduction was completely wrong (at some point I implicitly assumed that the matrix I’m dealing with has orthogonal columns!) and in fact, it’s easy to construct counterexamples. The issue is, when the target vector is in some sense the average of two *almost* orthogonal columns of the matrix, then the solution to the least squares problem contains an arbitrarily large component. Aaargh. So not only is my reduction incorrect, I can’t approach it from the viewpoint of reduction at all.

Possibly relevant posts:

• Vector space projection methods (2/22/2006)
• A lower bound on the norm of a useful class of matrices (1/12/2009)
• K-means as a matrix optimization problem (1/9/2010)