# Non negative least squares with minimal colinearity

I am trying to fit a dataset using the standard NNLS (non-negative least squares) approach. Formally:

$\min_x ||Ax-b||^2_2$ s.t. $x\ge0$

This is a quadratic program and can be solved optimally. The solution I find fits the data reasonably well and is relatively sparse (which is good for me) but has an undesirable property: I find that it may assign high weights to features (columns of $A$) that are highly correlated. I would like my solution to be such that the correlation between support features (features that have high weights) will be minimal. Note that in my setting all entries of $A$ and $b$ are non-negative, and I can normalize the columns of $A$ so that the norm of each column is 1.

I tried approaching the problem by directly minimizing possible formalizations of the quantity I want. Note that $A^TA$ is the covariance matrix, so it could potentially be a good thing to minimize (perhaps not the diagonal, though). But minimizing $||Ax-b||^2_2+x^TA^TAx$ does not make any sense and minimizing $||Ax-b||^2_2+x^T(A^TA-I)x$ makes the optimization non-convex (because you get negative eigenvalues). With this approach, I can see that intuitively this is a bit like doing the opposite of ridge-regression/Tikhonov regularization.

I also tried L1 regularization ($||Ax-b||^2_2+\lambda||x||_1$) just for the heck of it, but it doesn't solve this problem.

Formally, I am looking to modify the objective function such that it penalizes solutions in which features that are "similar" to each other both get high weights. There are several ways to formalize this notion, for example one being that I would like the support columns to be as orthogonal as possible.

Does anyone have ideas on how else to approach this?

-
I'm not sure you have a well-defined problem here. If the optimal solution assigns high weights to correlated features, well--that's the optimal solution. To obtain any other solution you either have to modify the objective function or further limit the domain of feasible solutions. What guidance can you give us concerning either of those options? You seem to be fishing for a modified objective function but I don't see where you state any principles or objectives for changing it. – whuber Jan 10 '13 at 16:14
@whuber I don't agree completely with your reasoning, because you can say the same for any least squares regularization. The problem with least squares is that it is the optimal fit for the given data but doesn't necessarily generalize well. What people do with regularization is create some new objective function so that the solution will have some desirable properties. The challenge is to pick an objective function that will both desire what you want and be efficiently computable. I will write this more explicitly in the question. – Bitwise Jan 10 '13 at 16:27
@whuber I rewrote some parts a little more clearer, I hope it is better now. – Bitwise Jan 10 '13 at 16:40
Marcos Lopez de Prado developed Mini-Max Subset Correlation algorithm that (while not strictly non-negative) may be close to what you are looking for. – onlyvix.blogspot.com Sep 19 '13 at 16:30
very interesting, i had a similar problem but had no time to solve it properly, so just end up selecting several uncorrelated variables manually. please post your final solution. – Kochede Dec 19 '13 at 10:59

I think minimizing $\| Ax -y \|^2 + \lambda x ^\top A^\top Ax$ does make sense. think of it as just a particular non-diagonal covariance gaussian prior. then you can vary $\lambda$ (and cross validate) to achieve different error/feature support tradeoffs.