Constrain transition matrix to have nonnegative eigenvalues?

[rmcgibbo]

Has anyone ever built an optimizer to find the maximum likelihood reversible transition matrix with strictly nonnegative eigenvalues from equilibrium transition counts ? The standard MLE transmat only bounds the eigenvalues in -1 < \lambda_i < \lambda_0 = 1. I'm planning to do this, but I don't want to repeat a lot of work if someone has done it already.

cc @kyleabeauchamp @schwancr @tjlane @rbharath

[kyleabeauchamp]

I've never done it right, and I don't have any useful code to share.

I recall playing with things like merging states when T{ii} < 0.5. I don't think I ever threw that inside the likelihood maximizer. I suppose in your case, the advantage of working with T{ii} is to avoid doing possibly millions of eigenvalue operations, which would be impossibly slow for microstate models.

(see http://en.wikipedia.org/wiki/Gershgorin_circle_theorem)

[kyleabeauchamp]

Do you have an optimizer that you plan on using for this? IMHO the various minimizers seem to severely lack robustness, which tends to get much worse as you add constraints to a problem.

[rmcgibbo]

For this problem, I'm not interested in particularly large numbers of states, so robustness isn't really the proximal issue, yet. I first need to figure out how I want to formulate it.

[schwancr]

Could you simply work in the eigenspace as opposed to transition matrix space? I.e. optimize the left eigenvectors and the eigenvalues and then get T after the fact? Then the positivity is easily constrained. I think reversibility should translate into it just fine too.

On Wed, Dec 4, 2013 at 4:04 PM, Robert McGibbon notifications@github.comwrote:

For this problem, I'm not interested in particularly large numbers of states, so robustness isn't really the proximal issue, yet. I first need to figure out how I want to formulate it.

— Reply to this email directly or view it on GitHubhttps://github.com/SimTk/msmbuilder/issues/267#issuecomment-29859361 .

[kyleabeauchamp]

I don't think that necessarily gives you T_{ij} > 0

[kyleabeauchamp]

Well, it might--but is there a way to calculate the likelihood in eigenspace? IMHO you have to re-calculate T_{ij}

[kyleabeauchamp]

IMHO one benefit of using the sufficient condition T_{ii} > 1 / 2 is that it can be expressed as a series of linear inequalities, even when you work with the symmetric counts X.

[rmcgibbo]

My current intuition is to formulate it as

max \sum_ij C_ij log((diag \pi^{-1/2}) S (diag \pi^{1/2}))_{ij}
s.t. S is p.s.d. and \pi >= 0

But there are a lot of ways to do the semi-definite programming problem.

[kyleabeauchamp]

I don't have much experience with PSD problems. I think you've done some work with them. If not, Pablo in Das lab has tried several of the Python wrapped solvers, so you could chat with him for a survey.

[rmcgibbo]

Kk. I'll close this for now then. If anyone has a stroke of insight, shout at me.