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?

  • $\begingroup$ 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. $\endgroup$
    – whuber
    Jan 10, 2013 at 16:14
  • $\begingroup$ @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. $\endgroup$
    – Bitwise
    Jan 10, 2013 at 16:27
  • $\begingroup$ @whuber I rewrote some parts a little more clearer, I hope it is better now. $\endgroup$
    – Bitwise
    Jan 10, 2013 at 16:40
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2013 at 16:30
  • 1
    $\begingroup$ also, lasso/ridge penalty is what usually solve the problem of multicollinearity, why didn't it work in your case? and what do you mean when saying it didn't work? $\endgroup$
    – Kochede
    Dec 19, 2013 at 11:01

1 Answer 1


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.

  • $\begingroup$ Thanks, I haven't thought about this problem for a while. I will give your suggestion some thought. $\endgroup$
    – Bitwise
    Aug 27, 2014 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.