6
$\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.

$\endgroup$
  • $\begingroup$ This is a mathematical question. $\endgroup$ – vinux Jan 10 '12 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 Jan 10 '12 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 Apr 20 '12 at 18:39
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ For comparison purposes, do you also know of the order of an efficient root finder? $\endgroup$ – Xi'an Jan 10 '12 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 Jan 10 '12 at 20:49
  • 1
    $\begingroup$ Yes, Jenkins-Traub, which is what is used in IMSL, is $O(p^2)$: jstor.org/pss/2949376. $\endgroup$ – jbowman Jan 10 '12 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 Jan 11 '12 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 Jan 11 '12 at 15:22
3
$\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

$\endgroup$
  • 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 Apr 20 '12 at 18:34

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.