Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a set of column vectors $v_1, v_2,...,v_t$ is there a way to calculate a unique transition matrix?

In other words, is there one and only one matrix $A$ such that $Av_{i} = v_{i+1}$?

Additionally, is it possible to find the "transition matrix of best fit" for $v_1, v_2,...v_t$? In other words, the matrix $A$ that minimizes the error between a predicted vector and the actual?

I'm asking because I'm trying to use Markov chains to predict a series of column vectors and I'm curious if there's a more "vectorized" (i.e. linear algebra based) implementation of calculating the transition matrix.

share|improve this question
    
I'm assuming you actually want $Av_i = v_{i+1}$, and not just $Av_1 = v_2$. It depends on the $v_i$; for a trivial example, if $v_i=\mathbf{0}$ but $v_{i+1}\neq\mathbf{0}$, then no matrix $A$ with $Av_i=v_{i+1}$ exists. More generally, if $v_i\in\mathrm{span}(v_1,\ldots,v_{i-1})$, $v_i=\alpha_1v_1+\cdots+\alpha_{i-1}v_{i-1}$, then the relations $Av_1=v_2$, $Av_2=v_3$, etc. force $v_{i+1}=Av_i = \alpha_1v_2+\cdots+\alpha_{i-1}v_i$. These conditions are necessary; if the $v_i$ satisfy the conditions, then $A$ exists; uniqueness only follows if the $v_i$ span the vector space. –  Arturo Magidin Jan 30 '12 at 17:45
    
If I misread your problem and you actually want just $Av_1=v_2$, then if $v_1\neq\mathbf{0}$ there are generally lots of matrices $A$: complete $\{v_1\}$ to a basis $v_1,u_2,\ldots,u_n$, pick your favorite vectors $w_2,\ldots,w_n$; then there is a matrix $A$ such that $Av_1=v_2$ and $Au_j=w_j$ for $j=2,\ldots,n$. Clearly, this gives lots of liberty in choosing $A$ if you only subject it to the condition $Av_1=v_2$. –  Arturo Magidin Jan 30 '12 at 18:04
    
Yep, that was a typo, thanks. What you said about span makes sense, however, for my particular dataset I can't guarantee that will be true. –  Jeff Wu Jan 30 '12 at 20:37

1 Answer 1

I can't (yet) describe the theory behind it, but I wrote an article on fitting Leslie matrices to data: http://arxiv.org/abs/1203.2313

The above article references the method as presented in Caswell's book on matrix population models, and only really works for a specific format of transition matrix. The method can actually be made quite general and should be framed in terms of Kronecker products and the columnize-ing vec operator. I am working on that article currently, and will post a draft if you ask me to.

To get you started consider a data matrix $D$ at time t being the result of multiplication by an unknown transition matrix $X$:

$D_{t+1}=XD_{t}$

This is equivalent to the following with $I$ a conformable identity matrix:

$D_{t+1}=IXD_{t}$ (1)

Now you can use the following formula (from various textbooks):

$vec(ABC)=(C^{T}\otimes A)vec(B)$

For our case, B is the unknown transition matrix, A is the identity matrix, C is the data matrix. Take $vec()$ of both sides of (1):

$vec(D_{t+1}) = vec(IXD_{t}) = (D_{t} \otimes I)vec(X) $

This is a standard matrix equation. Rewrite as

$ (D_{t} \otimes I)^{-1} vec(D_{t+1}) = vec(X)$

and solve if possible. It is unlikely that there is a single solution to this (see textbooks etc), but you can minimize the following

$|| (D_{t} \otimes I)^{-1} vec(D_{t+1}) - vec(X) ||_2$ (2)

Then you de-vec $vec(X)$ to get the original transition matrix.

Caveats: So far I have found that you need to constrain the heck out of X to make it usable and enforce sparsity, and you also probably want to minimize the norm of (2) for an underdetermined solution. I do the following in the paper, and I am working on articulating how to do the latter with SVD now.

If you are using this, please cite me, and feel free to IM or ask questions here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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