5
$\begingroup$

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

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
10
  • $\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, 2015 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, 2015 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, 2015 at 15:26
  • $\begingroup$ @Suvrit It does not use but it only works in the fixed m large k regime. $\endgroup$
    – Uchiha
    Oct 27, 2015 at 16:10
  • $\begingroup$ @Ray ah, I skipped reading the "sufficiently large $k$..." $\endgroup$
    – Suvrit
    Oct 27, 2015 at 17:34
0
$\begingroup$

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.

$\endgroup$

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.