---
abstract: 'Matrix $\bfC$ can be blindly deconvoluted if there exist matrices $\bfA$ and $\bfB$ such that $\bfC= \bfA \ast \bfB$, where $\ast$ denotes the operation of matrix convolution.  We study the problem of matrix deconvolution in the case where matrix $\bfC$ is proportional to the inverse of the autocovariance matrix of an autoregressive process.  We show that the deconvolution of such matrices is important in problems of Hankel structured low-rank approximation (HSLRA).  In the cases of AR(1) and AR(2) models, we fully characterize the range of parameters where such deconvolution can be performed and provide construction schemes for performing deconvolutions.  We also consider general stationary AR($p$) processes, where we prove that the deconvolution $\bfC= \bfA \ast \bfB$ does not exist if the matrix $\bfB$ is diagonal and its size is larger than $p$.'
author:
- 'Nina Golyandina[^1], Anatoly Zhigljavsky[^2]'
title: Blind deconvolution of covariance matrix inverses for autoregressive processes
---

[Keywords: matrix convolution; structured low-rank approximation; autoregressive process; correlated noise]{}

MSC 2000 classification: 15A24, 15A21, 62M10

Introduction
============

Let $A$ and $B$ be positive integers and $\bfa = (a_0, \ldots, a_{A})^\top \in \spR^{A+1}$ and $\bfb = (b_0, \ldots, b_{B})^\top\in \spR^{B+1}$ be two vectors.  The convolution of vectors $\bfa$ and $\bfb$ is the vector $\bfc = \bfa \ast \bfb=(c_0, \ldots, c_{C})^\top \in \spR^{C+1} $ with $C = A + B $ and $c_i = \sum_k a_k b_{i-k},$ where $i=0,1, \ldots, C\, $ and the sum taken over the set of indices $k$ such that the elements $a_{k}$ and $b_{i-k}$ are defined (that is, $ \max\{0,i-B\} \leq k \leq  \min\{A,i\}$).  The definition of vector convolution naturally extends to matrices as follows.  Let $\bfA=(a_{i,j})_{i,j=0}^A$ and $\bfB=(b_{i, j})_{i,j=0}^B$ be matrices of sizes $(A\!+\!1)\!\times\!(A\!+\!1)$ and $(B\!+\!1)\!\times\!(B\!+\!1)$, respectively.  A matrix $\bfC = (c_{i, j})_{i,j=0}^{A+B}$ is a convolution of the matrices $\bfA$ and $\bfB$ if $ c_{i,j}= \sum_{k,l} a_{k,l}b_{i-k,j-l}$, where the sum is taken over the sets of indices $k$ and $l$ such that the elements $a_{k,l}$ and $b_{i-k,j-l}$ are defined (that is, $ \max\{0,i-B\} \leq k \leq \min\{A,i\}$ and $\max\{0,j-B\} \leq l \leq  \min\{A,j\}$). 

The generating function (gf) of a vector $\bfu=(u_0,\ldots,u_M)^\top$ is defined as $G_\bfu(t) = u_0 +u_1 t + \ldots + u_M t^M\,$. Similarly, the generating function of a matrix $\bfU=(u_{i,j})_{i,j=0}^M$ is $G_\bfU(t,s)= \sum_{i,j=0}^M u_{i,j} t^i s^j  $, where $t,s \in \spC$.

From the definition of convolution, $\bfc = \bfa \ast \bfb$ if and only if $G_\bfc(t)= G_\bfa(t) G_\bfb(t)$ for all $t \in \spC$. Similarly, $\bfC= \bfA \ast \bfB$ if and only if $G_\bfC(t,s)= G_\bfA(t,s) G_\bfB(t,s)$ for all $t,s \in \spC$. This yields that all statements about vector and matrix convolutions (and deconvolutions) can be equivalently formulated in the language of generating functions. 

A vector $\bfc$ can be blindly deconvoluted if there exist vectors $\bfa$ and $\bfb$ such that $\bfc = \bfa \ast \bfb$. This problem (interesting only under some restrictions on $\bfa$ and $\bfb$) is equivalent to studying the roots of the gf $G_\bfc(t)$.

A matrix $\bfC $ can be blindly deconvoluted if there exist matrices $\bfA$ and $\bfB$ such that $\bfC= \bfA \ast \bfB$.

There exists an extensive literature related to matrix convolution and (blind) deconvolution but it is mostly related to applications in image processing; see e.g. [@Kundur. Hatzinakos1996; @Michailovich. Tannenbaum2007].  We are interested in the blind deconvolution of matrices $\bfC$ which are (proportional to) inverses of the autocovariance matrices of autoregressive processes. 

The structure of the paper is as follows.  In Section 2 we establish that a correspondence between two different norms in the HSLRA problem exists if and only if the matrix, inverse to the autocovariance matrix of the noise process, can be blindly deconvoluted.  In Section 3 we derive some auxiliary statements about generating functions (gf) of diagonals of matrices and relate gf of banded matrices to gf of its diagonals.  In Section 4 we provide the main matrices of interest (inverses to autocovariance matrices for AR(1) and AR(2) processes) and derive some relations between gf of diagonals of these matrices.  In Section 5 we prove our main results establishing ranges of parameters in the AR(1) and AR(2) models, where the deconvolution can be performed.  In particular, we establish that for the stationary AR(1) and AR(2) models the inverse to the autocovariance matrix cannot be deconvoluted.  In cases where the deconvolution is possible, we provide the construction schemes for the matrices $\bfA$ and $\bfB$. In Section 6 we specialize results of Section 5 when we require an additional condition of non-negative definiteness for the matrices $\bfA$ and $\bfB$. Finally, in Section 7 we derive some partial results for the general AR($p$) model. 

Motivation: selection of a matrix norm in HSLRA
===============================================

Our [motivation]{} is the problem of extraction of a signal $\bfs=(s_0,s_1, \ldots, s_{N-1})^\top$ from an observed noisy signal $\bfx=(x_0,x_1, \ldots, x_{N-1})^\top=\bfs+\bm\xi$ of length $N$, where $\bm\xi=(\xi_0,\xi_1, \ldots, \xi_{N-1})^\top$ is a vector of (unobserved) random noise with zero mean and covariance matrix $\bm\Sigma = \Expect \bm\xi \bm\xi^\top$.

We consider a wide class of signals, which have an explicit parametric form of a finite sum: $$\label{eq:model_pol}
  s_n = \sum_k \tsp_k(n)\exp(\alpha_k n) \sin(2\pi \omega_k n + \phi_k),$$ where $\alpha_k, \omega_k$ and $\phi_k$ are arbitrary real numbers and $\tsp_k(n)$ are polynomials in $n$.

This class of signals can be defined through low-rank Hankel matrices as follows.  Set a window length $L$, $1<L\leq N/2$; $K = N - L +1$. With a series $\bfz=(z_0,z_1, \ldots, z_{N-1})^\top$, we associate the so-called trajectory matrix $$\begin{aligned}
  \calT_L(\bfz) = \left(
  \begin{array}{llll}
    z_0      & z_1 & \dots     & z_{K-1}     \\
    z_1      & \cdots  & \;\cdots    & z_{K}    \\
    \; \ldots   & \;\ldots   & \ \:\ldots    & \; \ldots   \\
    z_{L-1}  & z_{L} & \dots & z_{N-1}
  \end{array}
  \right) \in \spR^{L \times K}.\end{aligned}$$ If there exists an integer $r<\lfloor N/2 \rfloor $ such that $r$ is the rank of $\calT_L(\bfz)$ for any $L\in [r,  \lfloor N/2 \rfloor ]$, then we say that $\bfz$ is a *series of rank $r$* [and write $\rank \bfz = r$]{}. 

The problem of finite-rank signal extraction can be reduced to the problem of approximation of the $L$-trajectory matrix $\calT_L(\bfx)$ of the observed time series $\bfx$ by a Hankel matrix of rank $r$. This problem belongs to the class of problems of Hankel structured low-rank approximation (HSLRA), see e.g. [@Chu.etal2003; @Markovsky2019; @Markovsky.etal2006]. 

The HSLRA problem can be stated in two forms: (a) vector form and (b) matrix form.  The vector (time series) form of this problem is: for given $\bfx \in \spR^{N}$ and positive integer $r<\lfloor N/2 \rfloor $, $$\label{eq:L-rank_task}
\|\bfx-\bfy\|^2_{\bfW} \to \min_{\bfy: \rank \bfy \le r}\,,$$ where $\bfy = (y_0, y_1, \ldots, y_{N-1})^\top$, $\|\bfz\|_{\bfW}^2 = \bfz^\top \bfW \bfz$ for $\bfz \in \spR^{N}$ and $\bfW$ is some positive definite matrix of size $N\times N$.

The solution of can be considered as a weighted least-square estimate (WLSE) of the signal $\bfs$. If noise $\bm\xi$ is Gaussian with covariance matrix $\bm\Sigma$, then the WLSE with $\bfW_0 = \bm\Sigma^{-1}$ is the maximum likelihood estimate (MLE).  If the properties of the noise process are known then the vector form is the most natural way of defining the HSLRA problem.  Solving the problem in the vector form is extremely difficult, however, see [@gillard2013optimization]. [ Although the vector form allows fast implementations, these implementations are very complex and need a starting point that is close to the solution [@Markovsky. Usevich2014; @Zvonarev. Golyandina2018].]{} 

The matrix form of HSLRA allows one to use simple alternating projection methods [@Cadzow1988] and hence [is typically computationally much preferable]{} than the vector form .  Define the inner product in $\spR^{L \times K}$ as $\langle \bfX, \bfY \rangle = \langle \bfX, \bfY \rangle_{{\bfA}, {\bfB}} = \operatorname{tr}({\bfA}\bfX {\bfB}\bfY^\top)$, where ${\bfA}=(a_{i,j})_{i,j=0}^{L-1} \in \spR^{L \times L}$, ${\bfB}=(b_{i,j})_{i,j=0}^{K-1}  \in \spR^{K \times K}$; $\| \bfX \|_{{\bfA}, {\bfB}}$ is the corresponding matrix norm in $ \spR^{L \times K}$. The Hankel SLRA problem in the matrix form is the following optimization problem: $$\label{eq:rank_task}
  \|\bfX - \bfY \|_{{\bfA}, {\bfB}}^2 \to \min_{\bfY\in \cM_r \cap \cH}\;, \;\;$$ where $\cH \subset \spR^{L\times K}$ is the space of Hankel matrices of size $L \times K$, $\cM_r\subset \spR^{L\times K}$ is the set of matrices of rank not larger than $r$. If HSLRA is used for the solution of , then $\bfX = \calT_L(\bfx)$ and $\bfY = \calT_L(\bfy)$.

Particular cases of the correspondence between the vector-norm and matrix-norm formulations and of the Hankel SLRA problem is considered in several papers, see e.g. [@gillard2015stochastic; @Zvonarev. Golyandina2017].  The general case is established in the following theorem. 

\[th:W\_L\_R\] For any $\bfz \in \spR^{N}$, $\|\calT_L(\bfz)\|_{{\bfA}, {\bfB}} = \|\bfz\|_\bfW$ if and only if \[eq:b\_decomp\] = . 

Consider the squared norm $\|\mathbf{X}\|_{{\bfA}, {\bfB}}^2={\operatorname{tr}\,\mathbf{A} \mathbf{X}\mathbf{B}\mathbf{X}^T}$ with $\mathbf{X}= \calT_L(\bfz)$ so that $x_{l,k}=z_{l+k}$ for $l=0, \ldots, L-1$ and $k=0, \ldots,K-1$. We have $$\begin{aligned}
  \|\mathbf{X}\|_{\mathbf{A,B}}^2=
  \sum_{l,l',k,k'}  a_{l,l'} x_{l',k'} b_{k',k} x_{l,k}
  =\sum_{l,l',k,k'}    a_{l,l'} z_{l'+k'} b_{k',k} z_{l+k}
  = \sum_{l,l',k,k'}   z_{ n'} a_{l,l'}  b_{ n'-l',{n-l}} z_{n}\end{aligned}$$ where $n=k+l$, $n'=k'+l'$ and all sums above are taken for $l,l'=0, \ldots, L-1$ and $k,k'=0, \ldots,K-1$. By changing the summation indices in the last sum $k \to n$ and $k' \to n'$ we obtain the required. 

In a typical application, when the structure of the noise in the model ‘signal plus noise’ is assumed, the HSLRA problem is formulated in a vector form with a given matrix $\bfW$. As mentioned above, algorithms of solving the HSLRA problem are much easier if we have the matrix rather than vector form of the HSLRA problem.  Therefore, in view of Theorem \[th:W\_L\_R\], for a given $\bfW$ we would want to find positive definite matrices $\bfA$ and $\bfB$ such that holds; that is, we would want to perform a blind deconvolution of the matrix $\bfW$.

Matrices $\bfA$ and $\bfB$ in and therefore in should be symmetric non-negative definite, see e.g. [@Allen2014] and [@golyandina2018singular p.62].  In Theorems 2–4 below we shall require symmetry of matrices $\bfA$ and $\bfB$ in and discuss if they can be chosen to be non-negative definite in Section \[sec:ABnonnegative\]. 

It follows from the results of [@Zhigljavsky.etal2016] that in the case when the noise $\bm\xi$ is white, and therefore $\bfW = \bfI_N$, the matrix $\bfW$ cannot be blindly deconvoluted under the condition that $\bfA$ and $\bfB$ are positive definite matrices (however, for a wide range of parameters $N$ and $L$ there are many pairs of non-negative definite diagonal matrices $\bfA$ and $\bfB$ such that holds).  This paper extends results of [@Zhigljavsky.etal2016] to the case of banded matrices corresponding to autoregressive noise $\bm\xi$.

Generating functions and convolution of banded matrices
=======================================================

Generating function of a matrix via generating functions of its diagonals
-------------------------------------------------------------------------

In some cases (e.g, for banded matrices), it is natural to construct generating functions of matrices as a sum of generating functions of diagonals.  Consider a matrix $\bfU=\{u_{i,j}\}_{i,j=0}^M$ and let $ G_\bfU(t,s)$ be its generating function. 

Define $\operatorname{diag}_i({\bfU})$, the $i$-th diagonal of $\bfU$, as the vector of length $M-|i|+1$ with elements with indices $(j,k)$ satisfying $k-j=i$, $i=-M,\ldots,M$. This $i$-th diagonal $\operatorname{diag}_i({\bfU})$ has the univariate gf $\tsu_i (\tau)= G_{\operatorname{diag}_i({\bfU})}(\tau) = \sum_{j=0}^{M-|i|} u_{j,j+i} \tau^j$.

\[lem:gf2\] G\_(t,s) = \_[i=-M]{}\^[M]{} t\^[(|i|-i)/2]{} s\^[(|i|+i)/2]{} \_[i]{} (ts).\
If $\bfU$ is symmetric, this formula simplifies to $
  G_\bfU(t,s) = \tsu_{0} (ts) + \sum_{i=1}^{M} (t^i + s^i) \tsu_{i} (ts). 
$

$$\begin{aligned}
  G_\bfU(t,s) &=& \sum_{j,k=0}^M u_{j,k} t^j s^k = \sum_{i=-M}^M \sum_{k-j=i} u_{j,k} t^j s^k =\\
  &=& \sum_{i=1}^M t^i \sum_{j=0}^{M-i} u_{j+i,j} t^j s^j + \sum_{i=1}^{M} s^i\sum_{j=0}^{M-i} u_{j,j+i} t^j s^j +  \sum_{i=0}^M u_{i,i} t^i s^i = \\
  &=& \sum_{i=0}^M t^i \tsu_{-i}(ts) + \sum_{i=1}^{M} s^i \tsu_{i}(ts)
  = \sum_{i=-M}^{0} t^{-i} \tsu_{i}(ts) + \sum_{i=1}^{M} s^i \tsu_{i}(ts) =\\
  &=&\sum_{i=-M}^{M} t^{(|i|-i)/2} s^{(|i|+i)/2} \tsu_{i} (ts).\end{aligned}$$

Convolution of matrices expressed through convolution of diagonals; banded matrices
-----------------------------------------------------------------------------------

\[lem:ABCgf\] Let $\bfA=(a_{i,j})_{i,j=0}^A$, $\bfB=(b_{i, j})_{i,j=0}^B$ and $\bfC=\bfA\ast\bfB$. For a given integer $i$, let $\tsa_i(t)= G_{\operatorname{diag}_i(\bfA)}(t)= \sum_{j=0}^{A-|i|} a_{j,j+i} t^j$ ($|i|\leq A$), $\tsb_i(t)= G_{\operatorname{diag}_i(\bfB)}(t)$ ($|i|\leq B$) and $\tsc_i(t)=G_{\operatorname{diag}_i(\bfC)}(t)$ ($|i|\leq C = A+B$) be the generating functions of the diagonals $\operatorname{diag}_i(\bfA)$, $\operatorname{diag}_i(\bfB)$ and $\operatorname{diag}_i(\bfC)$, respectively.  Then $$\label{eq:W_L_R3}
  \tsc_i(t) = \sum_{j+k = i} t^{(|j|+|k| - |j+k|)/2} \tsa_j(t) \tsb_k(t)  \;\;(i = -C, \ldots, C)\, .$$

Following Lemma \[lem:gf2\], we should prove that $$\begin{aligned}
  \sum_{i=-C}^{C} t^{(|i|-i)/2} s^{(|i|+i)/2} \tsc_{k}(ts) =
  \sum_{i=-C}^{C} t^{(|i|-i)/2} s^{(|i|+i)/2} \sum_{j+k = i} (ts)^{(|j|+|k| - |j+k|)/2} \tsa_j(ts) \tsb_k(ts).\end{aligned}$$ Indeed, $$\begin{aligned}
  &&\sum_{i=-C}^{C} t^{(|i|-i)/2} s^{(|i|+i)/2} \tsc_{k}(ts)  \\
  &=&\left(\sum_{j=-A}^{A} t^{(|j|-j)/2} s^{(|j|+j)/2} \tsa_{j}(ts)\right)
  \left(\sum_{k=-B}^{B} t^{(|k|-k)/2} s^{(|k|+k)/2} \tsb_{k}(ts)\right)\\
  &=&
  \sum_{j=-A}^{A} \sum_{k=-B}^{B} t^{(|j|-j)/2} s^{(|j|+j)/2} \tsa_{j}(ts)t^{(|k|-k)/2} s^{(|k|+k)/2} \tsb_{k}(ts)\\
  &=&\sum_{i=-(A+B)}^{A+B} \sum_{j+k=i} t^{(|j|-j)/2} s^{(|j|+j)/2} t^{(|k|-k)/2} s^{(|k|+k)/2} \tsa_{j}(ts)\tsb_{k}(ts)\\
  &=&\sum_{i=-C}^{C} \sum_{j+k=i} t^{(|j|+|k|-(j+k))/2} s^{(|j|+|k|+(j+k))/2} \tsa_{j}(ts)\tsb_{k}(ts).\end{aligned}$$ Since $j+k=i$ within the sum, the proof is complete. 

\[rem:diag\_simplified\] We have: $$\begin{aligned}
  (|j|+|k| - |j+k|)/2 =
  \begin{cases}
    0, & \mbox{if \ \ } jk \ge 0\\
    t^{|k|} & \mbox{if \ \ }  jk < 0, |j| \ge |k|; \\
    t^{|j|} & \mbox{if \ \ }  jk < 0, |j| < |k|. 
  \end{cases}\end{aligned}$$

The following corollary is a reformulation of Lemma \[lem:ABCgf\] using the explicit form for the diagonals of $\bfC$.

\[lem:conv\] Let matrices $\bfA$, $\bfB$ and $\bfC=\bfA\ast\bfB$ be as in Lemma \[lem:ABCgf\].  Then the $i$-th diagonal of $\bfC$ is $$\label{eq:conv_diag}
  {\rm diag}_{i}(\bfC) = \sum_{j+k = i}
  \begin{pmatrix}
    0_{(|j|+|k| - |j+k|)/2} \\
    \operatorname{diag}_j(\bfA) \ast \operatorname{diag}_k(\bfB) \\
    0_{(|j|+|k| - |j+k|)/2}
  \end{pmatrix},$$ where $i = -C, \ldots, C$, $C=A+B$, and $0_m \in \spR^{m}$ is a vector of zeros of size $m$.

In the case of banded matrices, Corollary \[lem:conv\] takes the following form. 

\[prop:p1p2\] Let $\bfA=(a_{i,j})_{i,j=0}^A$ be a $(2p_1+1)$-diagonal matrix with $p_1\leq A$, $\bfB=(b_{i, j})_{i,j=0}^B$ be $(2p_2+1)$-diagonal with $p_2\leq B$ and $\bfC=\bfA\ast\bfB$. Then $\bfC$ is $(2p+1)$-diagonal with $p=p_1 + p_2$ and the $i$-th diagonal $\operatorname{diag}_i(\bfC)$ of $\bfC$ $(i = -p, \ldots, p)$ is given by ; its gf is given by . 

When $p_2 = 0$ so that $\bfB$ is diagonal, Corollary \[prop:p1p2\] gives the following particular case. 

\[prop:p\_diag\] Let ${\bfA}$ be a $(2p+1)$-diagonal matrix and ${\bfB}$ be diagonal with $\bfb$ on the main diagonal.  Then $\bfC=\bfA\ast\bfB$ is $(2p+1)$-diagonal with $\operatorname{diag}_i(\bfC) = \operatorname{diag}_i({\bfA}) \ast \bfb$, $i = -p, \ldots, p$; in terms of gf, we have $\tsc_i(t) = \tsa_i(t) \tsb_0(t)$, $i = -p, \ldots, p$.

Autocovariance matrices and their inverses for AR(1) and AR(2) models
=====================================================================

Inverse autocovariance matrices
-------------------------------

It is well known that the inverse to the autocovariance matrix of AR($p$) is positive-definite symmetric $(2p+1)$-diagonal matrix [@Shaman1975 p.534].  Below we consider explicit forms of $\bm\Sigma^{-1}$ for the AR(1) and AR(2) models. 

### AR(1)

Let $\bm\xi=(\xi_0,\xi_1, \ldots, \xi_{W})^\top$ follows the AR(1) process $$\begin{aligned}
\label{eq:AR1}
  \xi_j=\phi_1\xi_{j-1}+\varepsilon_j,\end{aligned}$$ where $j=1, \ldots, W$, [$\phi_1\neq 0$]{}, and $ \varepsilon_1, \varepsilon_2, \ldots$ are i.i.d.  normal random variables ${\cal N} (0,1)$; $\xi_j$ are ${\cal N} (0,\sigma^2)$ for all $j=0, \ldots, W$, where $\sigma^2=1/(1-\phi_1^2).$ The condition of stationarity of the process is $|\phi_1|<1$. The covariance matrix $\bm\Sigma$ of the vector $\bm\xi$ is $\bm\Sigma = \sigma^2( \phi_1^{|i-j|})_{i,j=0}^{W}$. The inverse of $\bm\Sigma$ is the tridiagonal matrix [$\bm\Sigma^{-1}= \bfW \in \spR^{(W+1)\times (W+1)}$, ]{} where $$\begin{aligned}
\label{eq:AR1W}
  \bfW=
  \begin{pmatrix}
    1&k_{1}&0&0  &\ldots\\
    k_1 & k_0    &k_1&0&\ldots\\
    0& k_1    &k_0&k_1&0\\
    \vdots&\ddots&\ddots&\ddots&\ddots&\ddots\\
    && 0    &k_1&k_0&k_1\\
    &&0& 0&k_{1}&1\\
  \end{pmatrix}~,\end{aligned}$$ $k_0=1+\phi_1^2$, $k_1=-\phi_1$. Note that the matrix is defined for any $\phi_1$, not necessarily for $|\phi_1|<1$.

### AR(2)

Let $\bm\xi=(\xi_0,\xi_1, \ldots, \xi_{W})^\top$ follows the AR(2) process $$\begin{aligned}
\label{eq:AR2}
  \xi_j=\phi_1\xi_{j-1}+\phi_2\xi_{j-2}+\varepsilon_j\; \;(j=2, \ldots, W)\end{aligned}$$ where $\varepsilon_j$ are i.i.d.  ${\cal N} (0,1)$ and $\xi_j$ are ${\cal N} (0,\sigma^2)$ for all $j=0, \ldots, W$; here $\sigma^2=(1-\phi_2)/[(1+\phi_1-\phi_2)(1-\phi_1-\phi_2)(1+\phi_2)]$. The conditions of stationarity are $\phi_2+|\phi_1|<1$ and $|\phi_2|<1$. The region of stationarity of the AR(2) model is depicted in Figure 1.  The inverse of the covariance matrix $\bm\Sigma$ is a five-diagonal matrix $\bm\Sigma^{-1}= \bfW  =(w_{i,j})_{i,j=0}^W$, where $$\begin{aligned}
\label{eq:AR2W}
  \bfW=
  \begin{pmatrix}
    1&k_{12}&k_2&0  &0&0&\ldots\\
    k_{21}&k_{22}&k_1&k_2&0&0&\ldots\\
    k_2 & k_1    &k_0&k_1&k_2&0&\ldots\\
    0&k_2 & k_1    &k_0&k_1&k_2\\
    \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots\\
    &&0&k_2& k_1    &k_0&k_1&k_2\\
    &&0&0&k_2&k_1&k_{22}&k_{12}\\
    &&0&0&0& k_2&k_{21}&1\\
  \end{pmatrix}~,\end{aligned}$$ $k_0=1+\phi_1^2+\phi_2^2$, $k_1=-\phi_1+\phi_1\phi_2$, $k_2=-\phi_2$, $k_{12}=k_{21}=-\phi_1$, $k_{22}=1+\phi_1^2$. The matrix is defined for any $\phi_1$ and $\phi_2$.

\[fig:ar2\]

(-8,-1) circle (0pt) node\[anchor=east\] ; (-3,-1) circle (1pt) node\[anchor=east\] [$-1$]{}; (-3,1) circle (1pt) node\[anchor=east\] [$1$]{}; (-2,-2) circle (1pt) node\[anchor=north\] [$-2$]{}; (2,-2) circle (1pt) node\[anchor=north\] [$2$]{}; (0,-2) circle (1pt) node\[anchor=north\] [$0$]{}; (-3,-2) -&gt; (-3,2.5) node at (-3,2.5) \[right\] [$\phi_2$]{}; (-3,-2) -&gt; (3,-2) node at (3,-2) \[right\] [$\phi_1$]{}; (0,1) – (2,-1) – (-2,-1) – cycle; (0,1) circle (3pt) node\[anchor=south\] [$(0,1)$]{}; (2,-1) circle (3pt) node\[anchor=north\] [$(2,-1)$]{}; (-2,-1) circle (3pt) node\[anchor=north\] [$(-2,-1)$]{};

Inverses of autocovariance matrices and their generating functions 
-------------------------------------------------------------------

Let $\bfW =c \bm\Sigma^{-1}=(w_{i,j})_{i,j=0}^W$, where $\bm\Sigma$ is the autocovariance matrix of AR($p$) with some $p>0$, and $c$ is chosen so that $w_{0,0}=1$ like in and . [ Recall that the matrix $\bfW$ is banded.]{} 

Consider the relation between diagonals of $\bfW$ and their generating functions.  Denote $\bfw_k = \operatorname{diag}_k(\bfW)$ and its gf $\tsw_k(t) {\stackrel{\mathclap{\textrm{\mbox{def}}}}{=}}G_{\bfw_k}(t)$, $t\in\spC$. For $k\ge 0$, an explicit formula for $\tsw_k$ is $\tsw_k(t)= \sum_{j=0}^{W-k} w_{j,j+k} t^j$.

### Generating function of a vector of ones

Below we shall frequently use the following gf.  Let $\bfc_M=(1, \ldots, 1)^\top \in \spR^{M+1}$. Then $$\tsC_M(t) {\stackrel{\mathclap{\textrm{\mbox{def}}}}{=}}G_{\bfc_M}(t) = 1+\ldots+t^M = \frac{1-t^{M+1}}{1-t} \,.$$ The following convenient formula connects polynomials $\tsC_{M+k}(t)$ and $\tsC_M(t)$ with $k>0$: $$\begin{aligned}
\label{eq:cm}
   \tsC_{M+k}(t) &=& t^k \tsC_{M}(t) + \tsC_{k-1}(t).\end{aligned}$$

### AR(1)

Consider the AR(1) model with regression coefficient $\phi_1$. From , we have $$\tsw_1(t) = -\phi_1 \tsC_{W-1}(t)\;\;{\rm and }\;\;
  \tsw_0(t) = \tsC_{W}(t) + \phi_1^2 t \tsC_{W-2}(t).$$ Applying with $(k,M)=(1,W-1)$ and $(k,M)=(1,W-2)$, we obtain the following lemma. 

\[lem:AR1w\] For the AR(1) model , \[eq:AR1w\] \_1(t) = -\_1 \_[W-1]{}(t), \_0(t) = t \_[W-1]{}(t) + 1 + \_1\^2 (\_[W-1]{}(t)-1). 

### AR(2)

Consider the AR(2) model with regression coefficients $\phi_1$ and $\phi_2$. From , we obtain $$\begin{aligned}
  \tsw_2(t) &= -\phi_2 \tsC_{W-2}(t),\\
  \tsw_1(t) &= -\phi_1 \tsC_{W-1}(t) +\phi_1 \phi_2 t \tsC_{W-3}(t),\\
  \tsw_0(t) &= \tsC_{W}(t) + \phi_1^2 t \tsC_{W-2}(t) + \phi_2^2 t^2 \tsC_{W-4}(t). 
\end{aligned}$$

Applying with [$k=1$, $M=W-3, W-2$ and with $k=2$, $M=W-4, W-2$]{}, we obtain the following lemma. 

\[lem:AR2w\] For the AR(2) model , $$\label{eq:AR2w}
\begin{aligned}
  \tsw_2(t) &= -\phi_2 \tsC_{W-2}(t),\\
  \tsw_1(t) &= -\phi_1 (t \tsC_{W-2}(t)+1) +\phi_1 \phi_2(\tsC_{W-2}(t)-1),\\
  \tsw_0(t) &= t^2 \tsC_{W-2}(t) + t + 1 + \phi_1^2 t \tsC_{W-2}(t) + \phi_2^2 (\tsC_{W-2}(t)-(t+1)). 
\end{aligned}$$

Studying existence of solutions to the problem of blind deconvolution for the matrices proportional to inverses of covariance matrices in autoregressive models
===============================================================================================================================================================

For given square matrices $\bfA$ and $\bfB$, we denote $\tsa_j (t)= G_{\operatorname{diag}_j(\bfA)}(t)$ and $\tsb_j (t) = G_{\operatorname{diag}_j(\bfB)}(t)$.

AR(1) {#sec:ar1a}
-----

\[th:AR1\_3\_1\] Let $W\geq 2$ and the matrix $\bfW$ be defined by .  There exist symmetric matrices $\bfA=(a_{i,j})_{i,j=0}^A$ and $\bfB=(b_{i, j})_{i,j=0}^B$ with $A,B \ge 1$ such that $\bfW= \bfA \ast \bfB$, if and only if $|\phi_1|= 1$.

Assume that $\bfW= \bfA \ast \bfB$. Since $\bfW$ is 3-diagonal, in view of Corollary \[prop:p\_diag\] and the assumption of symmetry of $\bfA$ and $\bfB$, we can only consider the case when $\bfA$ is 3-diagonal and $\bfB$ is diagonal. 

From we obtain $$\begin{aligned}
\label{eq:AR1wab}
  \tsw_1(t) =  \tsa_1 (t) \tsb_0 (t) ,\;\;
  \tsw_0(t) = \tsa_0(t) \tsb_0(t), \;\; \forall t \in \spC\,.\end{aligned}$$ Since $\phi_1\neq 0$, from the left equalities in and we deduce that all the roots of $ \tsC_{W-1}(t)$ are the roots of $\tsa_1(t) \tsb_0 (t)$. Since $B\ge 1$, at least one of the roots of $ \tsC_{W-1}(t)$ is a root of $\tsb_0 (t)$. Let $t_1 \in \spC$ be such root. 

Suppose that $|\phi_1|\neq 1$. From the second equality in we have $\tsw_0(t_1)=0$ but the second equality in yields $\tsw_0(t_1)=1-\phi_1^2\neq 0$. This contradiction proves the necessity of $|\phi_1|= 1$.

Assume now $|\phi_1|= 1$ so that $\phi_1=\pm 1$. In this case, $\tsw_0(t) = (t+1) \tsC_{W-1}(t)$ and therefore, taking also into account the first equality in , the equalities become $$\begin{aligned}
 \label{eq:polyn}
  \tsa_1 (t) \tsb_0 (t) = -\phi_1 \tsC_{W-1}(t), \
  \tsa_0(t) \tsb_0(t) = (t+1) \tsC_{W-1}(t).\end{aligned}$$ Represent $\tsC_{W-1}(t)$, which is a polynomial of degree $W-1 \geq  1$, as a product of two non-zero polynomials $\tsp(t)$ and $\tsq(t)$: \[eq:productAR1\] \_[W-1]{}(t)=(t)(t) .  Here the polynomial $\tsp(t)$ can be a constant and $\tsq(t)$ has degree at least 1.  Then we can choose \[eq:productAR1a\] \_0 (t)= (t), \_0(t)=(t+1)(t) \_1 (t)= -\_1 (t) . 

Assume $|\phi_1|=1$. Let us count the number of different deconvolutions $\bfW= \bfA \ast\bfB$ assuming $a_{0,0}=b_{0,0}=1$ (for any $\bfA $ and $\bfB$ and any $\lambda \neq 0$, we have $\bfA \ast\bfB = \bfA^\prime \ast\bfB^\prime $ with $\bfA^\prime =\lambda \bfA$ and $\bfB^\prime =\bfB/\lambda $).  This is equivalent to counting the number of different splits of $\tsC_{W-1}(t)=1+t+\ldots+t^{W-1}$ into a product of polynomials $\tsp(t)$ and $\tsq(t)$ [with real coefficients]{}, where $\tsp(0)=\tsq(0)=1$, the degree of $\tsp(t)$ is arbitrary and $\tsq(t)$ has degree at least 1.  Let us show that this number of splits is $2^M-1$, where $M=\lfloor W/2 \rfloor$.

Assume first that $W-1$ is even; that is, $W-1=2M$. In this case, all roots of $\tsC_{W-1}(t)$ are complex roots of unity and therefore $\tsC_{W-1}(t)$ is a product of $M$ different quadratic forms which have no real roots.  Hence, the total number of required splits is $2^M-1$.

Assume now that $W-1$ is odd; that is, $W=2M$. Then $\tsC_{W-1}(t)$ has one real root (which is $-1$) and $2M-2$ complex ones.  Therefore $\tsC_{W-1}(t)$ is a product of $t+1$ and $M-1$ quadratic forms with no real roots.  Once again, the total number of required splits is $2^M-1$.

Note that if we additionally require, as we do in Section \[sec:ABnonnegative\], that the polynomials $\tsp(t)$ and $\tsq(t)$ in have non-negative coefficients, then the total number of eligible splits becomes $H(W)$, the number of different ordered factorizations of $W$ into primes, see [@Zhigljavsky.etal2016]. 

AR(2)
-----

Consider the AR(2) model with regression coefficients $\phi_1$ and $\phi_2$. We aim at identifying matrices $\bfA$ and $\bfB$ so that holds; that is, $\bfW= \bfA \ast\bfB$. Since $\bfW$ is 5-diagonal and in view of Corollary \[prop:p1p2\] this may only happen in the following two cases: (a) each of $\bfA$ and $\bfB$ is 3-diagonal and (b) $\bfA$ is 5-diagonal and $\bfB$ is diagonal. 

### $\bfA$ and $\bfB$ are symmetric and both matrices are 3-diagonal

\[th:AR2\_3\_3\] Let $W\ge 3$ and the matrix $\bfW $ be defined in with $\phi_2 \neq 0$. Assume that the matrices $\bfA=(a_{i,j})_{i,j=0}^A$ and $\bfB=(b_{i, j})_{i,j=0}^B$ are 3-diagonal and $A\ge 2$, $B\ge 1$. There exist such $\bfA$ and $\bfB$ with $\bfW= \bfA \ast \bfB$, if and only if either (i) $\phi_2 = -1$ and $|\phi_1|\geq 2$ or (ii) $\phi_2 = 1$ and $\phi_1=0$.

The proof of Theorem \[th:AR2\_3\_3\] is based on several lemmas. 

\[lem:th33\_1\] Under the conditions of Theorem \[th:AR2\_3\_3\], the existence of matrices $\bfA$ and $ \bfB$ such that $\bfW= \bfA \ast \bfB$, implies that the polynomial $\tsw_1^2(t) - 4\tsw_2(t) (\tsw_0(t) - 2t \tsw_2(t))$ is the square of a polynomial in $t$.

From we obtain \[eq:2AR\] \_2(t) =\_1(t) \_1(t), \_1(t) =\_0(t) \_1(t) + \_1(t) \_0(t), \_0(t) =\_0(t) \_0(t) + 2t \_1(t) \_1(t).  For brevity, we will omit the argument $t$. We have: $$\begin{aligned}
  \tsa_1 \tsb_1 = \tsw_2, \ \tsa_0 \tsb_1 + \tsa_1 \tsb_0 = \tsw_1, \  \tsa_0 \tsb_0  = \tsw_0 - 2t \tsw_2.\end{aligned}$$ Denote $\tsy = \tsa_0 \tsb_1$, $\tsz = \tsa_1 \tsb_0$. Then we obtain $$\begin{aligned}
  \tsy+\tsz = \tsw_1, \ \tsy\tsz  =  \tsw_2(\tsw_0 - 2t \tsw_2).\end{aligned}$$ This means that $\tsy$ and $\tsz$ are the roots of the quadratic equation $\tsx^2 + \tsw_1 \tsx + \tsw_2(\tsw_0 - 2t \tsw_2)  = 0$. These roots are $$\begin{aligned}
\label{eq:x}
  \tsx_{1,2} = \frac{\tsw_1\pm \sqrt{\tsw_1^2 -4\tsw_2 (\tsw_0 - 2t \tsw_2) }}{2}.\end{aligned}$$ Since the roots should be polynomials, $\tsw_1^2 - 4\tsw_2(\tsw_0 - 2t \tsw_2) $ should be a square of a polynomial in $t$ (recall that $\tsw_i$ are polynomials in $t$). 

\[lem:Pol\_in\_C\] Assume that a polynomial $\tsP_{2M}(t)$ has the form $$\tsP_{2M}(t) = (\tsP_1(t) \tsP_{M-1}(t))^2 + \tsQ_1(t) \tsP_{M-1}(t) + \tsP_{0}$$ for some [$M \ge 1$]{} (the lower indices mean polynomial degrees).  If the square root of $\tsP_{2M}(t)$ exists then it has the form $\pm\tsP_1(t) \tsP_{M-1}(t) + {\rm const}$.

Let $\tsP_1(t) = at+b$, $\tsQ_1(t) = dt + f$. Then for $\gamma  = d/(2a)$ we have $$\tsP_{2M}(t) = (\tsP_1(t) \tsP_{M-1}(t) + \gamma)^2 + g \tsP_{M-1}(t) + p_0,$$ where $g$ and $p_0$ are some constants.  Let $\tsP_{2M}(t) = \tsU_M^2(t)$. Denote $\tsV_M(t) = \tsP_1(t) \tsP_{M-1}(t) + \gamma$, $\tsD_{M-1}(t) = g \tsP_{M-1}(t) + p_0$. Then $$\tsD_{M-1}(t) = \tsU_M^2(t) - \tsV_M^2(t) = (\tsU_M(t) - \tsV_M(t))(\tsU_M(t) + \tsV_M(t)).$$ The left-hand side part in this equation is a polynomial of order $M-1$ or less but the right-hand side part is either identical zero or a polynomial of order $M$ or larger.  Therefore this equality can be valid only if $\tsU_M(t) =\pm \tsV_M(t)$.

\[lem:th33\_2\] For the matrix $\bfW $ defined in with $\phi_2 \neq 0$, the polynomial $\tsw_1^2(t) - 4\tsw_2(t) (\tsw_0(t) - 2t \tsw_2(t))$ is a polynomial square if and only if at least one of the following relations hold:\
(A) $\phi_2=-1$, (B) $\phi_2 = 1-\phi_1$, (C) $\phi_2=1+\phi_1$.

For brevity, we will omit the polynomial argument $t$. Denote $\tsC = \tsC_{W-2}(t)$.

Direct substitution using gives $$\begin{aligned}
  \tsw_1^2-4(\tsw_0 - 2t \tsw_2) \tsw_2 =
    (-\phi_1 t+\phi_1\phi_2)\tsC -\phi_1(1+\phi_2))^2 + \\
  +4\phi_2(t^2 + (\phi_1^2 + 2\phi_2)t + \phi_2^2) \tsC^2 +
  4\tsC\phi_2(t+1-\phi_2^2(t+1)).\end{aligned}$$ Consider this polynomial as a polynomial in $\tsC$. By $\tsv_i$ we denote the coefficient for $\tsC^i$, $i=0,1,2$. We have: $$\begin{aligned}
  \tsv_0&=&\phi_1^2(1+\phi_2)^2,\\
  \tsv_1&=&2(1+\phi_2)(-\phi_1^2(\phi_2-t) + 2\phi_2(t+1)(1-\phi_2)),\\
  \tsv_2&=&(\phi_1^2+4\phi_2)(t+\phi_2)^2.\end{aligned}$$ In view of Lemma \[lem:Pol\_in\_C\], the determinant $$\begin{aligned}
      \tsv_1 - 4 \tsv_0 \tsv_2 = 4(1+\phi_2)^2\phi_2(1+\phi_1-\phi_2)(1-\phi_1-\phi_2)((t+1)^2 \phi_2 + t\phi_1^2)\end{aligned}$$ should be equal to zero.  The solutions of the equation $\tsv_1 - 4 \tsv_0 \tsv_2 =0$, with respect to $\phi_2$, are: $\phi_2=0,-1, 1-\phi_1, 1+\phi_1,  -t\phi_1^2/(1+t)^2$. The root $\phi_2=0$ is inappropriate, since $\phi_2\neq0$ by the definition of AR(2).  The root $\phi_2=-t\phi_1^2/(1+t)^2$ is inappropriate as it depends on $t$. The proof is complete. 

In view of Lemmas \[lem:th33\_1\] and \[lem:th33\_2\], matrices $\bfA$ and $\bfB$ such that $\bfW= \bfA \ast \bfB$ holds may exist only in the three particular cases indicated in Lemma \[lem:th33\_2\]; that is, (A) $\phi_2=-1$, (B) $\phi_2 = 1-\phi_1$, (C) $\phi_2=1+\phi_1$. Let us consider these three cases separately. 

\(A) Assume $\phi_2 = -1$. Then $$\begin{aligned}
  \tsw_2(t) =  \tsC_{W-2}(t),\
  \tsw_1(t) = -\phi_1 \tsC_{W-2}(t)(t+1), \
  \tsw_0(t) = \tsC_{W-2}(t)(t^2 + \phi_1^2 t + 1).\end{aligned}$$ From and we then have: $$\label{eq:three_eq}
  \begin{aligned}
  \tsa_1(t) \tsb_1(t) &= \tsC_{W-2}(t), \\
  \tsa_0(t) \tsb_1(t) + \tsa_1(t) \tsb_0(t) &= -\phi_1 \tsC_{W-2}(t)(t+1), \\
  \tsa_0(t) \tsb_0(t) + 2t \tsa_1(t) \tsb_1(t) &=  \tsC_{W-2}(t)(t^2 + \phi_1^2 t + 1). 
  \end{aligned}$$ Since polynomials $\tsa_0(t)$ and $\tsb_0(t)$ have one degree higher than the polynomials $\tsa_1(t)$ and $\tsb_1(t)$ respectively, $\tsa_1(t) \tsb_1(t) = \tsC_{W-2}(t)$ and $\tsa_0(t) \tsb_0(t)$ contains $\tsC_{W-2}(t)$ as a multiplier, we obtain that $\tsa_0(t)=(\lambda_0+\lambda_1t)\tsa_1(t)$ and $\tsb_0(t)=(\mu_0+\mu_1t)\tsb_1(t)$ for some $\lambda_0,\lambda_1,\mu_0$ and $\mu_1$. Substituting this into equations and cancelling $C_{W-2}(t)$, which is a common multiplier in all equations, we obtain the following two equations for $\lambda_0,\lambda_1,\mu_0$ and $\mu_1$: $$\begin{aligned}
  \left\{
  \begin{array}{lcl}
    (\mu_0+\mu_1t)\,(\lambda_0+\lambda_1t) &=& t^2-2t+\phi_1^2t +1 \\
    (\mu_0+\mu_1t)+(\lambda_0+\lambda_1t) &=& -(t+1)\phi_1
  \end{array}
  \right.\end{aligned}$$ Equating the coefficients of the two polynomials in $t$ we find that there are no solutions for $\lambda_0,\lambda_1,\mu_0$ and $\mu_1$ when $|\phi_1|<2$. On the other hand, there are the following solutions when $|\phi_1|\geq 2$: let \[eq:z\] z\_[1]{}= z\_[2]{}= be two solutions of the equation $z^2+\phi_1 z+1=0$, then we can choose either $
\mu_0 = \lambda_1= z_1,\;\;\lambda_0 = \mu_1 = z_2
$ or $
\mu_0 = \lambda_1= z_2,\;\;\lambda_0 = \mu_1 = z_1. 
$ This gives the required expressions for $\tsa_0(t)$, $\tsa_1(t)$, $\tsb_0(t)$ and $\tsb_1(t)$, see Corollary \[cor:AR1\_3\_1ab3\]. 

\(B) Assume $\phi_2 = 1 - \phi_1$. Then the equations become $$\label{eq:aaa}
  \begin{aligned}
  \tsa_1(t) \tsb_1(t) &= -(1-\phi_1) \tsC_{W-2}(t),\\
  \tsa_0(t) \tsb_1(t) + \tsa_1(t) \tsb_0(t)  &= -\phi_1 (t \tsC_{W-2}(t)+1) +\phi_1 (1-\phi_1)(\tsC_{W-2}(t)-1),\\
 \!\!\!\!\!\!  \tsa_0(t) \tsb_0(t)\!  + \!2t \tsa_1(t) \tsb_1(t) &= t^2 \tsC_{W-2}(t) \!+\!  t\!  +\!  1\!  +\!  \phi_1^2 t \tsC_{W-2}(t) \!+\! ( 1\!-\!\phi_1)^2 (\tsC_{W-2}(t)\!-\!(t\!+\!1)). 
\end{aligned}$$ [Using the expression for the products $\tsa_0(t) \tsb_1(t)$ and $\tsa_1(t) \tsb_0(t)$, we obtain $\tsa_1 (t)\tsb_0(t)= (1-\phi_1)(t+1)\tsC_{W-2}(t)$ as one of the two roots given by .  Similar to the case (A), from the first equation in we obtain $\tsb_0(t)=-(1+t)\tsb_1(t)$. Take any root $t_1$ of $\tsa_1 (t)$ and substitute it into the second equation in .  Since the roots of $\tsa_1 (t)$ consist of the roots of $\tsC_{W-2}(t)$, we obtain $\phi_1(2-\phi_1)=0$.]{} The solution $\phi_1=0$ implies $\phi_2 = 1$ and $\phi_1=2$ gives $\phi_2 = -1$. The case $\phi_1=2,\phi_2 = -1$ gives a solution described above in the case (A).  In the case $\phi_1=0,\phi_2 = 1$ we have solutions to obtained from arbitrary splitting \[eq:AR2\_eq\] \_[W-2]{}(t)=(t)(t) of $\tsC_{W-2}(t)$ into a product of two non-zero polynomials $\tsp(t)$ and $\tsq(t)$ and setting \[eq:split\_again\]

\(C) Assume $\phi_2 = 1 + \phi_1$. The equations become $$\begin{aligned}
  \tsa_1(t) \tsb_1(t) &= -(1+\phi_1) \tsC_{W-2}(t),\\
  \tsa_0(t) \tsb_1(t) + \tsa_1(t) \tsb_0(t)  &= -\phi_1 (t \tsC_{W-2}(t)+1) +\phi_1 (1+\phi_1)(\tsC_{W-2}(t)-1),\\
  \tsa_0(t) \tsb_0(t) + 2t \tsa_1(t) \tsb_1(t) &= t^2 \tsC_{W-2}(t) + t + 1 + \phi_1^2 t \tsC_{W-2}(t) + (1+\phi_1)^2 (\tsC_{W-2}(t)-(t+1)). 
  \end{aligned}$$ One of the two solutions for $\tsa_1 (t)\tsb_0(t) $ is $\tsa_1 (t)\tsb_0(t)= \tsC_{W-2}(t+(\phi_1+1)^2)$. Similarly to the above we obtain $\phi_1(2+\phi_1)=0$. The solution $\phi_1=0$ gives $\phi_2 = 1$ and hence the same set of solutions to equations as in Case (B).  The solution $\phi_1=-2$ gives $\phi_2 = -1$ and is covered in Case (A). 

\[cor:AR1\_3\_1ab3\] Summarizing the findings in case (i) of Theorem \[th:AR2\_3\_3\], when $\phi_2=-1$, the solutions to exist when $|\phi_1|\geq 2$ and can be constructed as follows: make an arbitrary split of $\tsC_{W-2}(t)$ into a product of two non-zero polynomials $\tsp(t)$ and $\tsq(t)$, set $\tsa_1(t)=\tsp(t)$, $ \tsb_1(t)=\tsq(t)$ and {

[c]{} \_0(t)=(z\_2+z\_1t)(t)\
\_0(t)=(z\_1+z\_2t)(t)\

. { 

[c]{} \_0(t)=(z\_1+z\_2t)(t)\
\_0(t)=(z\_2+z\_1t)(t) ,\

.  where $z_1$ and $z_2$ are defined in . 

### $\bfA$ is symmetric and 5-diagonal, $\bfB$ is diagonal

\[th:AR2\_5\_1\] Let $W\geq 4$ and the matrix $\bfW $ be defined in .  There exist matrices $\bfA=(a_{i,j})_{i,j=0}^A$ and $\bfB=(b_{i, j})_{i,j=0}^B$ with $A\geq 2$ and $B \geq 2$, where $\bfA$ is 5-diagonal and $\bfB$ is diagonal, such that $\bfW= \bfA \ast \bfB$ if and only if either (a) $\phi_2=-1$ or (b) $\phi_1=0$ and $\phi_2=1$.

Assume that $\bfW= \bfA \ast \bfB$. From we obtain $$\begin{aligned}
\label{eq:ar2_diag}
  \tsw_2(t) =  \tsa_2 (t) \tsb_0 (t) ,\;\;
  \tsw_1(t) =  \tsa_1 (t) \tsb_0 (t) ,\;\;
  \tsw_0(t) = \tsa_0(t) \tsb_0(t), \;\; \forall t \in \spC\,.\end{aligned}$$ Since $\phi_2\neq 0$, from the left equalities in and we deduce that all the roots of $ \tsC_{W-2}(t)$ are the roots of $\tsa_2(t) \tsb_0 (t)$. Since by assumption $B\ge 2$, at least two of the roots of $ \tsC_{W-2}(t)$ are the roots of $\tsb_0 (t)$. Let $t_1$ and $t_2$ be two of these roots. 

Suppose that the conditions on $\phi_1$ and $\phi_2$ are not fulfilled.  From the second equality in , $\tsw_1(t_i)= 0$ but the second equality in yields $\tsw_1(t_i)=-\phi_1(1+\phi_2)$, $i=1,2$. From the third equality in $\tsw_0(t_i)= 0$ but the third equality in yields $\tsw_0(t_i)=(1-\phi_2^2)(t_i+1)$, $i=1,2$. This is possible only in the cases (a) $\phi_2=-1$ and (b) $\phi_1=0$, $\phi_2=1$. This contradiction proves the necessity of the conditions on $\phi_1$ and $\phi_2$.

Assume (a): $\phi_2 = -1$. Then $$\begin{aligned}
  \tsw_2(t) =  \tsC_{W-2}(t),\
  \tsw_1(t) = -\phi_1 (\tsC_{W-2}(t)(t+1), \
  \tsw_0(t) = \tsC_{W-2}(t)(t^2 + \phi_1^2 t + 1).\end{aligned}$$ Therefore, $$\begin{aligned}
  \tsa_0(t) \tsb_0(t) &=& \tsC_{W-2}(t)(t^2 + \phi_1^2 t + 1), \\
  \tsa_1(t) \tsb_0(t) &=& -\phi_1 (\tsC_{W-2}(t)(t+1), \\
  \tsa_2 (t) \tsb_0 (t) &=& \tsC_{W-2}(t).\end{aligned}$$ Let $\tsC_{W-2}(t)=\tsp(t)\tsq(t)$, where $\tsp(t)$ is a non-zero polynomial of any degree including 0 and $\tsq(t)$ is a polynomial of degree at least 2.  Then we can choose \[eq:ar4a\] Now assume (b): $\phi_1=0$, $\phi_2=1$. Then $$\begin{aligned}
  \tsw_2(t) = - \tsC_{W-2}(t),\
  \tsw_1(t) = 0,\
  \tsw_0(t) = (t^2+1)\tsC_{W-2}(t).\end{aligned}$$ Therefore, $$\begin{aligned}
  \tsa_0(t) \tsb_0(t) =(t^2+1)\tsC_{W-2}(t), \;\;
  \tsa_1(t) \tsb_0(t) = 0, \;\;
  \tsa_2 (t) \tsb_0 (t) = - \tsC_{W-2}(t).\end{aligned}$$ Again, let $\tsC_{W-2}(t)=\tsp(t)\tsq(t)$ with the same assumptions on $\tsp(t)$ and $\tsq(t)$. Then we can choose \[eq:ar4\]

\[rem:B2\] For technical reason, Theorem \[th:AR2\_5\_1\] does not cover the case $B=1$. This case can be treated separately as follows.  First, similarly to the discussion in Section \[sec:ar1a\], the polynomial $\tsC_{W-2}(t)$ is divisible by a polynomial $\tsq(t)=\tsb_0 (t)$ of degree 1 [with real coefficients]{} if and only if $W$ is [odd]{}; this polynomial is $\tsb_0 (t)=\lambda(1+t)$ with $\lambda \neq 0$. Consider, for [odd]{} $W$, the equalities and .  The first and third equalities in show that [$\tsa_0 (t)=\tsw_0(t)/\tsb_0 (t)$ and $\tsa_2 (t)=\tsw_2(t)/\tsb_0 (t)$ are polynomials for arbitrary values of $\phi_1$ and $\phi_2$. However, the second equality in implies that $\tsa_1 (t)=\tsw_1(t)/\tsb_0 (t)$ is a polynomial if and only if $\tsw_1(-1) = 0$, that is,]{} either $\phi_2=-1$ or $\phi_1=0$ (in the latter case, $\tsa_1 (t)=0$). 

\[rem:remainder\]The main steps in the proofs of Theorems \[th:AR1\_3\_1\] and \[th:AR2\_5\_1\] is calculation of reminders of division of $\tsw_k(t)$ by $\tsC_{W-p}(t)$, where $p=1$ and $k=0$ for AR(1) and $p=2$ and $k=0,1$ for AR(2).  Indeed, denote such a reminder as $\tsr_k(t)$ and $B$ roots of $\tsb_0 (t)$, which are also the roots of $\tsC_{W-p}(t)$, as $t_1,\ldots,t_p$ (these roots exist since $B\ge p$).  Then $\tsw_k(t_i) = \tsr_k(t_i)$ for any $i=1,\ldots,p$. If $p$ is larger than the degrees of the reminders $\tsr_k(t)$ for each $k$, then $\{t_i\}_{i=1}^p$ are the roots of $\tsw_k(t)$ if and only if the reminders $\tsr_k(t_i)$ are zero. [ This is the case of Theorem \[th:AR1\_3\_1\] and Theorem \[th:AR2\_5\_1\]]{}. 

\[rem:not\_existance\] Theorems \[th:AR1\_3\_1\], \[th:AR2\_3\_3\] and \[th:AR2\_5\_1\] show that for stationary AR(1) and AR(2) models the deconvolution $\bfW=\bfA \ast \bfB$ with $A,B \geq 2$ cannot be performed as the necessary and sufficient conditions in these theorems contradict to the stationarity conditions.  However, in view of Remark \[rem:B2\], if $W$ is [odd]{} and $B=1$ then the deconvolutions $\bfW=\bfA \ast \bfB$ exist when $\phi_1=0$ and $\phi_2$ is arbitrary. 

Construction of non-negative definite matrices $\bfA$ and $\bfB$ such that $\bfW= \bfA \ast \bfB$ {#sec:ABnonnegative}
=================================================================================================

In this section, we additionally assume that symmetric matrices $\bfA$ and $\bfB$ such that $\bfA \ast \bfB=\bfW$ are non-negative definite.  The matrix $\bfW$ is as in the previous section; that is, it is given by either or . 

AR(1) {#sec:ar1_pos}
-----

Assume that $\mathbf{W}$ has the form .  Under the conditions of Theorem \[th:AR1\_3\_1\], symmetric matrices $\bfA$ and $\bfB$ with $\bfW= \bfA \ast \bfB$ exist if and only if $|\phi_1|=1$. A general method of construction of such $\bfA$ and $\bfB$ for $\phi_1=\pm 1$ is given by formulas and at the end of the proof of Theorem \[th:AR1\_3\_1\] in terms of the generating functions of the two diagonals of $\bfA$ and one diagonal of $\bfB$ (recall that the matrix $\bfB$ is diagonal). 

In the present case, where we require matrices $\bfA$ and $\bfB$ to be non-negative definite, we need the following lemma. 

\[lem:polyn\] Let $A\geq 1$ be a positive integer and $\tsp(t)= c_0 + c_1 t + \ldots+ c_{A-2}t^{A-2}+c_{A-1}t^{A-1}$ be a polynomial of degree $A-1\geq 0$. Consider a symmetric 3-diagonal matrix $\bfA=(a_{i,j})_{i,j=0}^A$ defined by ; that is, a matrix with the gf of the main diagonal $\tsa_0(t)=(t+1)\tsp(t)$ and the gf of the first diagonal $\tsa_1 (t)= G_{\operatorname{diag}_1(\bfA)}(t)= \beta \tsp(t)$, where $\beta=\pm 1$. For this matrix and for any vector $z=(z_0, \ldots, z_A)^\top \in \mathbb{R}^{A+1}$ we have \[eq:productAR1b\] z\^z= \_[i=0]{}\^[A-1]{}c\_i(z\_i+z\_[i+1]{})\^2 . 

Since $\tsa_0(t)=(t+1)\tsp(t)$, the diagonal elements of $\bfA$ are $a_{i,i}=c_i+c_{i-1}$, where $i=0,1, \ldots, A$ and we set $c_{-1}=c_A=0.$ The elements on the first diagonal of $\bfA$ are $a_{i,i+1}= \beta c_i$ ($i=0,1, \ldots, A-1$).  We also have $a_{i,i+1}=a_{i+1,i}$ and $a_{i,j}=0$ for $|i-j|>1$. Therefore, for any $z=(z_0, \ldots, z_A)^\top $ we obtain $$\!\!z^\top \bfA z=\sum_{i,j=0}^A z_ia_{i,j}z_j=c_0z_0^2\!+\!c_{A-1}z_A^2\!+\!\sum_{i=1}^{A-1} z_i^2 (c_{i-1}\!+\!c_i)\!+\!  2\beta\sum_{i=0}^{A-1}c_i z_i z_{i+1}= \sum_{i=0}^{A-1}c_i(z_i\!+\!\beta z_{i+1})^2 \, .$$

Theorem \[th:AR1\_3\_1\] and Lemma \[lem:polyn\] with $\beta=-\phi_1$ yield the following corollary. 

\[cor:AR1\_3\_1ab\] Let $W\geq 2$ and the matrix $\bfW$ be defined by .  There exist non-negative definite symmetric matrices $\bfA=(a_{i,j})_{i,j=0}^A$ and $\bfB=(b_{i, j})_{i,j=0}^B$ with some $A,B \ge 1$ such that $\bfW= \bfA \ast \bfB$ if and only if $|\phi_1|= 1$ and both polynomials $\tsp(t)$ and $\tsq(t)$ in are non-constants and have non-negative coefficients. 

It follows from that the matrix $\bfA$ defined in Lemma \[lem:polyn\] is non-negative definite if and only if all coefficients $c_i$ of the polynomial $\tsp(t)$ are non-negative.  Since $\bfB$ is diagonal, from the first equation in we obtain that $\bfB$ is non-negative definite if and only if all coefficients of the polynomial $\tsq(t)$ are non-negative. 

Since the polynomial $\tsp(t)$ in can have zero degree (this would correspond to a $2 \times 2$ matrix $\bfA$), the split with both polynomials having non-negative coefficients, can always be made.  If we assume $A>1$, then both polynomials $\tsp(t)$ and $\tsq(t)$ in have to have degree at least one and the problem of construction of non-constant polynomials $\tsp(t)$ and $\tsq(t)$ with non-negative coefficients such that holds becomes more difficult.  This problem was studied in [@Zhigljavsky.etal2016].  Theorem 1 in [@Zhigljavsky.etal2016] states that, under the additional condition $\tsp(0)=1$, if such polynomials exist then all their coefficients are either zeros or ones.  Corollary 3 in [@Zhigljavsky.etal2016] implies that such polynomials exist if and only if $W$ is not prime.  Paper [@Zhigljavsky.etal2016] also provides different schemes of construction of such polynomials $\tsp(t)$ and $\tsq(t)$ for composite $W$.

AR(2): $\bfA$ and $\bfB$ are symmetric and both matrices are 3-diagonal
-----------------------------------------------------------------------

In view of Theorem \[th:AR2\_3\_3\] we need to consider the following two cases only: (i) $\phi_2 = -1$ and $|\phi_1|\geq 2$ and (ii) $\phi_1=0,\phi_2 = 1$.

In case (i), when $\phi_2 = -1$ and $|\phi_1|\geq 2$, the way of constructing solutions to is described in Corollary \[cor:AR1\_3\_1ab3\].  Under the additional assumption $|\phi_1|= 2$ we have for $z_1,z_2$ from : $z_1=z_2=-1$ for $\phi_1=2$ and $z_1=z_2=1$ for $\phi_1=-2$. Similarly to Corollary \[cor:AR1\_3\_1ab\], Lemma \[lem:polyn\] and Corollary \[cor:AR1\_3\_1ab3\] yield the following. 

\[cor:AR1\_3\_1ab5\] Let $W\geq 2$ and the matrix $\bfW$ be defined by with $|\phi_1|= 2$ and $\phi_2 = -1$. Make a split of $\tsC_{W-2}(t)$ into a product of two polynomials $\tsp(t)$ and $\tsq(t)$ with non-negative coefficients.  Define 3-diagonal matrices $\bfA$ and $\bfB$ by the following generating functions of their diagonals: $\tsa_0(t)=(1+t)\tsp(t)$, $ \tsb_0(t)=(1+t)\tsq(t)$, $\tsa_1(t)= \beta \tsp(t)$ and $ \tsb_1(t)=\beta \tsq(t)$, where $\beta=-\phi_1/2 = -{\rm sign}(\phi_1)$. Then both matrices $\bfA$ and $\bfB$ are non-negative definite and $\bfW= \bfA \ast \bfB$.

If $|\phi_1|>2$ it does not seem possible to find a general scheme of construction of non-negative definite matrices $\bfA$ and $\bfB$ satisfying $\bfW= \bfA \ast \bfB$.

In case (ii), when $\phi_1=0,\phi_2 = 1$, general solutions to are obtained from , an arbitrary splitting of $\tsC_{W-2}(t)$ into a product of two polynomials $\tsp(t)$ and $\tsq(t)$ and using .  Similarly to Corollary \[cor:AR1\_3\_1ab\], Lemma \[lem:polyn\] yields the following: to guarantee that $\bfA$ and $\bfB$ are non-negative definite we simply make an additional requirement that the polynomials $\tsp(t)$ and $\tsq(t)$ in have non-negative coefficients.  Lemma \[lem:polyn\] again justifies the non-negative definiteness of $\bfA$ and $\bfB$.

Similarly to the discussion at the end of Section \[sec:ar1\_pos\], we may use the results of [@Zhigljavsky.etal2016] for establishing the existence of non-constant polynomials $\tsp(t)$ and $\tsq(t)$ with non-negative coefficients in and the building schemes for the corresponding matrices $ \bfA$ and $ \bfB$ of size larger than $2\times2$. The required non-trivial split into non-constant polynomials $\tsp(t)$ and $\tsq(t)$ with non-negative coefficients exists if and only if $W-1$ is a composite number. 

The particular cases of the AR(2) model considered in this section (where the deconvolution $\bfW= \bfA \ast \bfB$ can be performed and $\bfA$ and $\bfB$ are non-negative definite 3-diagonal matrices) are exactly the cases where the pairs of parameters $(\phi_1,\phi_2)$ of the AR(2) model are at critical points of the region of stationarity of the AR(2) model, see Figure 1. 

AR(2): $\bfA$ is symmetric and 5-diagonal, $\bfB$ is diagonal
-------------------------------------------------------------

Similarly to the results above, it can be shown that a 5-diagonal symmetric matrix $\bfA$ with generating functions of the three diagonals $\tsa_2 (t)= \tsp(t)$, $\tsa_1(t)=\beta_1(t + 1)\tsp(t)$ and $\tsa_0(t)=(t^2 + \beta^2 t + 1)\tsp(t)$ is non-negative definite if the coefficients of the polynomial $\tsp(t)$ are non-negative and $|\beta|\leq 1$. This implies that, if the polynomials $\tsp(t)$ and $\tsq(t)$ have non-negative coefficients then the two constructions of Theorem \[th:AR2\_5\_1\], and with $|\phi_1|\leq 1$, lead to non-negative definite matrices $\bfA$ and $\bfB$.

Non-existence of the deconvolution $\bfW\!=\!\bfA\!\ast\!\bfB$ for a stationary AR($p$) model with general $p$ and diagonal $\bfB$
==================================================================================================================================

Consider the AR($p$) model in the form $\sum_{i=0}^p \alpha_i\xi_{n-i} = \varepsilon_n$, where $\Var \varepsilon_n=1$ and $\alpha_p\neq 0$. This notation is connected to the basic notation in the form $\xi_{n} = \sum_{i=1}^p \phi_i\xi_{n-i} + \varepsilon_n$ by simple relations $\alpha_0=1$ and $\alpha_i=-\phi_i$ for $i>0$.

Let $\bm\Sigma$ be the autocovariance matrix of this AR($p$) process.  In accordance with [@Shaman1975 p. 534(3)], the matrix $\bfW = \bm\Sigma^{-1}$ has the form of a symmetric $(2p+1)$-diagonal matrix with $$\begin{aligned}
  w_{i,j}=
  \begin{cases}
  \sum_{k=0}^{\min(i,j) - 1} \alpha_k \alpha_{k+|i-j|}\ \text{for}\ i,j = 1,\ldots p;\\
  \sum_{k=0}^{p - |i-j|} \alpha_k \alpha_{k+|i-j|}\ \text{for}\ \min(i,j)> p,\ \max(i,j)<W-p,\  |i-j|=0,\ldots, p;\\
  0,\ \text{otherwise.} 
  \end{cases}\end{aligned}$$

One of the stationarity conditions for the AR($p$) model is $|\phi_p|<1$, see e.g. Jury’s test of stability [@Jury1964 Section 3.9].  In this section, we will show that if $|\phi_p|<1$ then the deconvolution is impossible under the assumption that the matrix $\bfB$ is diagonal and has a size larger than $p\times p$.

In the same manner as before, we can express the diagonals of $\bfW$ through the generating functions $\tsC_M(t)$ of vectors $(1,\ldots,1)^\top\in \spR^M$ with $M=W-2p,W-2p+1,\ldots,W$: $$\begin{aligned}
\label{eq:ARdiag}
  \tsw_k(t) = \sum_{i=0}^{p-k} \alpha_i \alpha_{i+k}t^i \tsC_{W-2i-k},\ k=0,\ldots,p.\end{aligned}$$ For example, $\tsw_p(t) = -\phi_p \tsC_{W-p}(t)$.

The expressions for $\tsw_k(t)$ in terms of $\tsC_{W-p}(t)$ play an important role for obtaining the results for AR(1) and AR(2).  In particular, Theorems \[th:AR1\_3\_1\] and \[th:AR2\_5\_1\], where either $\bfA$ or $\bfB$ in the deconvolution $\bfW=\bfA\ast\bfB$ is diagonal, are based on the consideration of remainders of division of $\tsw_k(t)$ by $\tsC_{W-p}(t)$ for $k=0,1$ and AR(1) and $k=0,1,2$ and AR(2), see Remark \[rem:remainder\]. 

It follows from that $\tsw_p(t)$ is proportional to $\tsC_{W-p}(t)$ for any $p$. Therefore, it can be proved, similarly to the proofs of Theorems \[th:AR1\_3\_1\] and \[th:AR2\_5\_1\], that a necessary condition for the possibility of deconvolution $\bfW=\bfA\ast\bfB$, where $\bfB$ is a diagonal matrix and [$B>p$]{}, is zero remainders of division of $\tsw_k(t)$ by $\tsC_{W-p}(t)$ for $k=0,\ldots,p-1$. The proof uses the equalities $$\begin{aligned}
  \tsw_k (t) = \tsa_k(t) \tsb_0(t),\ k\leq p.\end{aligned}$$

The following lemma calculates the remainders. 

\[lem:remainder\] The remainder $\tsr_k(t)$ of the division of $\tsw_k(t)$ by $\tsC_{W-p}(t)$ for $k=0,\ldots, p$ is equal to $$\begin{aligned}
\label{eq:res}
  \tsr_k(t)=\sum_{i=0}^{p-k} \alpha_i \alpha_{i+k}(\tsC_{p-k-i-1}(t) - \tsC_{i-1}(t)).\end{aligned}$$ (Here we assume that $\tsC_{-1}=0$.)

Directly follows from and the equalities $t^i \tsC_{W-2i-k}= \tsC_{W-i-k} - \tsC_{i-1}$ and $\tsC_{W-i-k} = t^{p-(i+k)} \tsC_{W-p} + \tsC_{p-k-i-1}$, which are particular cases of . 

\[cor:tsr\] $$\begin{aligned}
  \label{eq:res_p}
  \tsr_p(t)&=&0,\\
  \label{eq:res_p1}
  \tsr_{p-1}(t) &=& \alpha_0\alpha_{p-1} - \alpha_1\alpha_{p},\\
  \label{eq:res_0}
  \tsr_0(t) &=& \sum_{m=0}^{p-1} \left(\sum_{i:\,i< \min(p/2, p-m)}(\alpha_i^2-\alpha_{p-i}^2)\right) t^m.\end{aligned}$$

The equality is readily obtained from , since $\tsC_{-1}=0$. The equality is proved by direct substitution of $k=p-1$ and $i=0, 1$ to . 

For the proof of , after substitution of $k=0$ and $i=0,\ldots,p$, the sum should be explicitly written as a polynomial in $t$. By and substituting $k=0$ we obtain $$\begin{aligned}
  \tsC_{p-i-1}(t) - \tsC_{i-1}(t) =
  \begin{cases}
  t^i \tsC_{p-2i-1}, \ i<p/2,\\
  0, \ i=p/2,\ p \mbox{\ is even},\\
  -t^{p-i} \tsC_{2i-p-1}, \ i>p/2. 
  \end{cases}\end{aligned}$$ Therefore, $$\begin{aligned}
  \tsr_0(t)=\sum_{i=0}^{\lfloor p/2\rfloor} \alpha_i^2 t^i  \tsC_{p-2i-1} - \sum_{j=\lfloor (p+1)/2\rfloor }^{p} \alpha_i^2 t^{p-j} \tsC_{2j-p-1}.\end{aligned}$$ Taking $j=p-i$, we obtain $$\begin{aligned}
  \tsr_0(t)&=&\sum_{i=0}^{\lfloor p/2\rfloor } (\alpha_i^2-\alpha_{p-i}^2) t^i \tsC_{p-2i-1} = \sum_{i=0}^{\lfloor p/2\rfloor } (\alpha_i^2-\alpha_{p-i}^2) \sum_{m=0}^{p-i-1} t^m = \\
  &=&\sum_{m=0}^{p-1} \left(\sum_{i:\,i< p/2, i+m \le p - 1)}(\alpha_i^2-\alpha_{p-i}^2)\right) t^m.\end{aligned}$$

It can be easily checked that the remainders, which have been calculated in the course of proofs of Theorems \[th:AR1\_3\_1\] and \[th:AR2\_5\_1\], can be deduced from the above formulas.  For AR(1), we have $\tsr_0(t) = 1-\phi_1^2 = \alpha_0^2 - \alpha_1^2$. For AR(2), we have $\tsr_1(t)=-\phi_1(1+\phi_2) = \alpha_0\alpha_1 - \alpha_1\alpha_2$ and $\tsr_0(t) = (1-\phi_2^2)(t+1) = (\alpha_0^2-\alpha_2^2)(t+1)$.

It follows from Corollary \[cor:tsr\] that one of the necessary conditions of existence of the decomposition $\bfW=\bfA\ast \bfB$ for the case of a diagonal $\bfB$ with $B\ge p$ is $\phi_p=\pm 1$ (the coefficient in front of $t^{p-1}$ in is equal to $\alpha_0^2 - \alpha_p^2 = 1-\phi_p^2$ and should be equal to 0).  This contradicts to $|\phi_p|<1$, a necessary condition for the stationarity of AR($p$).  Therefore, for the matrix $\bfW$ corresponding to a stationary AR($p$) model, the deconvolution cannot be performed. 

[^1]: St.Petersburg State University, Universitetskaya nab.  7/9, St.Petersburg, 199034, Russia; n.golyandina@spbu.ru

[^2]: Cardiff University, School of Mathematics, Senghennydd road, Cardiff CF24 4AG, UK; zhigljavskyaa@cardiff.ac.uk
