5
$\begingroup$

It is well-known that an AR(p) process $$ x_t=\sum_{i=1}^p \varrho_i x_{t-i} + \epsilon_t \,, $$ is causal and stationary if and only if the roots of the polynomial $$ \mathcal{P}(u) = 1 - \sum_{i=1}^p \varrho_i u^i $$ are all outside the unit circle in the complex plane. (Here is a Cross Validated discussion on the topic.)

My question is whether or not there exists a faster algorithm than the naïve one that consists in (a) finding the roots of $\mathcal{P}$ and (b) checking none one them is inside the unit circle.

Improve this question
$\endgroup$
3
  • $\begingroup$ This is a mathematical question. $\endgroup$
    – vinux
    Commented Jan 10, 2012 at 12:53
  • 1
    $\begingroup$ @vinux: It is more of a computational question in that I am looking for the smallest power $d$ such that the answer can be produced in a time $\text{O}(p^d)$... $\endgroup$
    – Xi'an
    Commented Jan 10, 2012 at 14:23
  • 1
    $\begingroup$ The process, as it's written is always causal. The condition about the roots tells if the system is stable - which implies stationarity. But it's more common to speak about stability conditions, rather than stationarity conditions, IMO. $\endgroup$
    – leonbloy
    Commented Apr 20, 2012 at 18:39

2 Answers 2

Reset to default
9
$\begingroup$

The Schur-Cohn algorithm has $d=2$; this is what I learned in a computational statistics class at Berkeley some years ago.

Improve this answer
$\endgroup$
5
  • $\begingroup$ For comparison purposes, do you also know of the order of an efficient root finder? $\endgroup$
    – Xi'an
    Commented Jan 10, 2012 at 19:35
  • 1
    $\begingroup$ I think they are also $d=2$, using the following thought process. Evaluation of a p-degree polynomial is $O(p)$. Finding a single root should be independent of the order of the polynomial. After the root is found, the polynomial can be reduced to a polynomial of degree $p-1$, but this doesn't affect the order. So each of the $p$ roots takes $O(p)$ to find, leading to an $O(p^2)$ algorithm. $\endgroup$
    – jbowman
    Commented Jan 10, 2012 at 20:49
  • 2
    $\begingroup$ Yes, Jenkins-Traub, which is what is used in IMSL, is $O(p^2)$: jstor.org/pss/2949376. $\endgroup$
    – jbowman
    Commented Jan 10, 2012 at 20:55
  • $\begingroup$ Superb! I though it would be more in $\text{O}(p^3)$ because of the same thought process with a $\text{O}(p^2)$ computing cost on the polynomial itself. $\endgroup$
    – Xi'an
    Commented Jan 11, 2012 at 9:55
  • 2
    $\begingroup$ Horner's method (cnx.org/content/m15099/latest) allows linear computing cost of the polynomial and is much more stable than evaluating it as it's written. I'm sure there are lots of others! $\endgroup$
    – jbowman
    Commented Jan 11, 2012 at 15:22
6
$\begingroup$

It is unnecessary to find the $p$ complex roots as far as these are not to be used for themselves. Moreover, most (if not all) root finding processes can fail for large $p$.

Another solution is as follows. The $\mathrm{AR}(p)$ model can be reparametrised thanks to its $p$ partial autocorrelations (PACs) $\zeta_k$ for $1 \le k \le p$. The PACs are often denoted as $\phi_{k,k}$ because their computation involves an array $\phi_{k,\ell}$. There is a one-to-one correspondence between the vector $\boldsymbol{\rho}$ of the $p$ coefficients in the stationarity region and the vector $\boldsymbol{\zeta}$ in the region defined by the $p$ conditions $|\zeta_k | < 1$ for $1 \le k \le p$. The transformation "AR to PAC" $\boldsymbol{\rho} \mapsto \boldsymbol{\zeta}$ is quite simple and is given as a pretty recursion formula due to Barndorff-Nielsen and Schou. Testing stationarity from the vector of coefficients boils down to computing the $\zeta_k$ and stop as soon as one condition $| \zeta_k | \ge 1$ is found. The less well-known inverse transform "PAC to AR" $\boldsymbol{\zeta} \mapsto \boldsymbol{\rho}$ is available explicitly (due to Monahan), and is as simple as is the direct one. It might also be useful in some cases.

The two transformations are implemented (in R) in a CRAN R package named FitAR which provides as well an efficient invertibleQ function to test stationarity. The package is described in the following article where list of references is provided.

McLeod, A.I. and Zhang Y., "Improved Subset Autoregression: With R Package" Journal of Statistical Software, vol. 28, Issue 2, Oct 2008. http://www.jstatsoft.org/v28/i02

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Further: PARCOR coefficients are the same (except for a sign change) as the "reflection coefficients", which can be obtained from the AR coefficients via Levinson-Durbin recursion. And, essentially, testing for reflection coefficients having modulus less than one, is the same as the Schur-Cohn test in the other answer. onlinelibrary.wiley.com/doi/10.1002/9780470611104.app6/pdf $\endgroup$
    – leonbloy
    Commented Apr 20, 2012 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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