# Prediction with positive weights?

Consider a covariance function (positive definite function) on $\mathbb{Z}$: $$\gamma(k)=(1+|k|)^{-\alpha},\quad \alpha>0.$$ It is guaranteed to be positive definite by Polya's criterion (monotonicity and convexity). Consider matrices $$\Sigma_1=[\gamma(i-j)]_{1\le i,j\le m},\quad \Sigma_2=[\gamma(k+i-j)]_{1\le i,j\le m},\quad m>0,~k\ge 0.$$ Show that all entries of $\Sigma_1^{-1}\Sigma_2$ are nonnegative.

Remark: I checked it numerically for different $k$, $m$ and $\alpha$. A weaker statement involving large enough $k\asymp m^{1+\epsilon}$, where $\epsilon>0$ is arbitrarily small, is also of great interest. A further question is to identify general conditions on a positive definite $\gamma(k)$ which fulfills the preceding requirement.

Remark: The problem can be reinterpreted in terms of linear prediction of stationary time series $\{X(n)\}$ whose covariance function is $\gamma(k)$. It is the same as to show that the linear predictor $\hat{X}(k)=\sum_{j=1}^m c_jX(j)$ which minimizes the mean square error $E |X(k)- \hat{X}(k)|^2$ satisfies $c_j\ge 0$.

Let's rephrase the question in terms of geometry. Write $$v_n = (\gamma(n),\gamma(n-1),\ldots,\gamma(n-m+1))^T.$$

Then the columns of $\Sigma_1$ are just $v_0,\ldots, v_{m-1}$ and the columns of $\Sigma_2$ are $v_k, v_{k+1},\ldots, v_{k+m-1}$. Thus the columns of $M = \Sigma_1 ^{-1} \Sigma_2$ are just the coefficients by which each $v_{k+j}$ can be (uniquely) represented as a linear combination of the basis $v_0,\ldots,v_{m-1}$.

For $M = \Sigma_1 ^{-1} \Sigma_2$ to have all entries nonnegative for all $k$ is to say that each $v_k, k\in \mathbb{N}$ is representable as a nonnegative linear combination of $v_0,\ldots,v_{m-1}$.

Looking at $v_i$ as points in $\mathbb{R}^m$, the statement of the question is equivalent to saying that when we take the sequence $v_0, v_1, \ldots,$ of points, the first $m$ points together with $0$ form the convex hull of the entire sequence. We can think of the first $m$ points as forming a "convex cone" with the origin, within which all of the other points must lie in a spiral towards zero.

Using this picture we can see for any fixed $m$, all sufficiently large $k$ work. That's because $v_n/\|v_n\|\rightarrow \frac{1}{\sqrt{m}}\cdot(1,1,\ldots,1)$, and the all $1$'s vector lies in the cone. It shouldn't be difficult to give an effective bound on how large $k$ has to be from this argument.

• Thank you for your nice insight! Indeed I noticed that the positiveness holds for $m$ fixed and large $k$. Ideally I need it for large enough $k\asymp m^{1+\epsilon}$, where $\epsilon>0$ is an arbitrarily small number. Do you think the potential argument works in this regime? – Uchiha Oct 27 '15 at 12:25
• Interestingly, the positive definiteness is not needed anywhere in the argument, so it was a red herring? – Suvrit Oct 27 '15 at 13:38
• @Suvrit In fact without positive definiteness, with $\Sigma_2$ given by a random matrix with every entry close to 1, this seems to fail numerically. – Uchiha Oct 27 '15 at 15:26
• @Suvrit It does not use but it only works in the fixed m large k regime. – Uchiha Oct 27 '15 at 16:10
• @Ray ah, I skipped reading the "sufficiently large $k$..." – Suvrit Oct 27 '15 at 17:34

10 December: My semester just ended and I got to think more about this problem. This is still a work in progress, but I thought I'd share my findings.

Starting from where @Xiaoyu left, we want to prove that $\mathbf{1} = (1, \ldots, 1)^T$ lies in the convex cone spanned by $v_0, \ldots, v_{m-1}$. Let's first establish that $\Sigma_1$ simply being symmetric positive definite Topelitz is not enough.

Let $M = \begin{bmatrix}1 & 2& 5\\ 2 & 1& 2\\ 5& 2& 1\\\end{bmatrix}$

Let $\Sigma_1 = \text{sqrtm}(M^2) = \begin{bmatrix} 5.0464 & 1.8543 & 1.0464\\ 1.8543 & 1.457 & 1.8543\\ 1.0464 & 1.8543 & 5.0464\end{bmatrix}$

$\Sigma_1$ is toeplitz, symmetric, PD but $\Sigma_1^{-1} \mathbf{1} = (-0.19868\ 1.1921\ -0.19868)^T$. This means that the values in $\Sigma_1 = [\gamma_\alpha(i-j)]_{ij}$ need to be taken into account to prove that $\mathbf{1}$ lies in the convex cone.

Numerical calculations strongly suggest though that this should be true

>> f = @(k, alpha) all(((1 + toeplitz(0:k-1)).^-alpha)\ones(k,1)> eps);
>> all(arrayfun(@(alpha) f(100, alpha), 0.1:0.1:5)))
1


So far I have only been able to prove this in the trivial case when $\alpha=1$. The interesting case when $\alpha \ne 1$ is still open. Applying Farkas lemma changes the problem to proving that $\nexists y \in \mathbb{R}^n: \Sigma_1y \ge 0 ,\, \mathbf{1}^Ty < 0$ which I dont see, how it would be useful.