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.

  • $\begingroup$ 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? $\endgroup$ – Uchiha Oct 27 '15 at 12:25
  • $\begingroup$ Interestingly, the positive definiteness is not needed anywhere in the argument, so it was a red herring? $\endgroup$ – Suvrit Oct 27 '15 at 13:38
  • $\begingroup$ @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. $\endgroup$ – Uchiha Oct 27 '15 at 15:26
  • $\begingroup$ @Suvrit It does not use but it only works in the fixed m large k regime. $\endgroup$ – Uchiha Oct 27 '15 at 16:10
  • $\begingroup$ @Ray ah, I skipped reading the "sufficiently large $k$..." $\endgroup$ – 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)))

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.


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.