6
$\begingroup$

I've been trying to crack this problem for days but I can't find a way around it. Given a set of unique N points $X = {x_1,..x,N}, x_i \in R^3$, the associated sinc-distance matrix $S \in R^{n\times n}$ is $S(i,j) = sin(|x_i-x_j|)/(|x_i-x_j|)$. My question is if this matrix is positive semidefinite.

I've ran numerical tests and the matrix always appears PSD, but I haven't been able to prove it formally.

Things I've tried:

  • Try to prove it using minors and so: no luck, sinc's are difficult to work with in order to simplify the form of the determinants.
  • Try proving that $\forall y$, $y^TSy\geq 0$, that ends up being $\sum_i^N \sum_j^N y_i y_j sin(|x_i-x_j|)/(|x_i-x_j|) \geq 0$. No luck either. My intuition is that the triangle inequality for distances has to play a role somewhere in it, but can't find it.
  • Try a constructive approach. We know that for the N=2 case, the matrix is PD, as the diagonal elements are 1 (sinc of 0) and the non-diagonal are $<1$, so the matrix is strictly diagonally dominant (also the determinant and trace are both positive, so $S \succ 0$. Then prove that adding an element to the set doesn't make the resulting matrix indefinite. I've tried using Schur complements for this task but no luck yet.
  • Also for any set $X$, we can multiply all elements by a scalar $\alpha$. As $\alpha$ goes to 0, all the elements in the set also go to 0 and $S \to \vec{1} \vec{1}^T$, which is PSD rank 1. As $\alpha$ goes to infinity, so do the points and so do the distances, so $S \to I$. So changing $\alpha$, the matrix moves in a 1D curve in the group $\mathcal{S}$ of symmetric matrices and the curve starts in the boundary of the cone of PSD matrices and ends in the middle of the cone, so it seems natural that it doesn't leave the cone, but I can't prove it.

Any help would be greatly appreciated! Looking forward to the discussion!

Thanks!

$\endgroup$
2
$\begingroup$

In the arXiv paper "Schoenberg matrices of radial positive definite functions and Riesz sequences in $L^2(\mathbb{R}^n)$" by L. Golinskii, M. Malamud and L. Oridoroga, Definition 1.1 states

Let $n \in \mathbb{N}$. A real-valued and continuous function $f$ on $\mathbb{R}_+ = [0,\infty)$ is called a radial positive definite function, if for an arbitrary finite set $\{x_1,\ldots,x_m\}$, $x_k \in \mathbb{R}^n$, and $\{\xi_1,\ldots,\xi_m\} \in \mathbb{C}^m$ $$\sum_{k,j = 1}^{n}f(|x_k-x_j|)\xi_k\overline{\xi}_j \ge 0.$$

Note that this definition is equivalent to saying that the matrix $S \in \mathbb{R}^{m \times m}$ defined by $S(k,j) = f(\|x_k-x_j\|)$ is positive semidefinite for any choice of points $x_1,\ldots,x_m \in \mathbb{R}^n$.

Also, Theorem 1.2 states the following:

A function $f \in \Phi_n$, $f(0) = 1$ if and only if there exists a probability measure $\nu$ on $\mathbb{R}_+$ such that $$f(r) = \int_{0}^{\infty}\Omega_n(rt)\nu(dt), ~~~~ r \in \mathbb{R}_+$$ where $$\Omega_n(s) := \Gamma(q+1)\left(\dfrac{2}{s}\right)^qJ_q(s) = \sum_{j = 0}^{\infty}\dfrac{\Gamma(q+1)}{j!\Gamma(j+q+1)}\left(-\dfrac{s^2}{4}\right)^j, ~~~~ q = \dfrac{n}{2}-1,$$ $J_q$ is the Bessel function of the first kind and order $q$.

(In their paper $\Phi_n$ denotes the set of radial positive definite functions on $\mathbb{R}^n$.)

Theorem 1 in "Metric Spaces and Completely Monotone Functions" by I. J. Schoenberg gives the proof of this result.

By applying this theorem for $n = 3$ and $\nu = \delta_1$, you get that $f(r) = \Omega_3(r) = \dfrac{\sin r}{r}$ is a radial positive definite function in $\mathbb{R}^3$. In other words, for any choice of $m$ points $x_1,\ldots,x_m \in \mathbb{R}^3$, the matrix $S \in \mathbb{R}^{m \times m}$ defined by $S(k,j) = \dfrac{\sin(\|x_k-x_j\|)}{\|x_k-x_j\|}$ is positive semidefinite.


It should be clear that if you choose $m$ points $x_1,\ldots,x_m$ in $\mathbb{R}$ or $\mathbb{R}^2$, then $S$ is still guaranteed to be positive semidefinite. However, that is not the case if the points are chosen in $\mathbb{R}^n$ where $n \ge 4$. joriki's answer gives a nice counterexample for $n \ge 5$. Here is an ugly counterexample (found by randomly generating points in MATLAB) with $6$ points in $\mathbb{R}^4$:

$x_1 = (-0.7,0.8,-0.3,-0.4)$

$x_2 = (0.8,-0.8,-0.9,0.7)$

$x_3 = (-0.1,0.0,0.1,-0.1)$

$x_4 = (-0.8,-0.7,-0.1,0.2)$

$x_5 = (0.2,-0.2,0.5,-0.9)$

$x_6 = (0.4,0.8,0.8,0.9)$

You can check that the $6 \times 6$ sinc distance matrix $S$ for these points has an eigenvalue of $\approx -0.0024103$, and thus, $S$ is not positive semi definite.

$\endgroup$
  • $\begingroup$ Thanks for this! I came up with a different proof by construction, but this formalism you laid out might be more useful for analogous problems that do not share the structure that I exploit in my proof. $\endgroup$ – Biel Roig-Solvas Mar 1 '17 at 18:00
  • $\begingroup$ Basically, defining a density in $R^3$ $\rho(x) = \sum_1^N y_i \delta(x-x_i)$, computing its Fourier Transform $A(X)$ and then performing an angular integration of $A(X)^* A(X)$ in spherical coordinates yields $\sum_i^N \sum_j^N y_i y_j sin(|x_i-x_j|)/(|x_i-x_j|)$, and its non-negativity comes from being an integration of a non-negative quantity $A(X)^* A(X)$, which proves the positive-definitiness of the Sinc-Distance matrix. Thanks again Jimmy! $\endgroup$ – Biel Roig-Solvas Mar 1 '17 at 18:00
4
$\begingroup$

No, the matrix is not necessarily positive definite. For any $k$, there's a simplex of $k+1$ points in $\mathbb R^k$ all at distance $\frac{3\pi}2$ from each other. The corresponding matrix has $1$ on the diagonal and $-2/(3\pi)$ elsewhere, and its eigenvalues are $1+2/(3\pi)$ and $1-2k/(3\pi)$, so for $k\gt\frac{3\pi}2\lt5$ the matrix is indefinite.

$\endgroup$
  • $\begingroup$ True!! Thank you joriki! The case I'm interested in is $R^3$, do you have any intuition about that? (I've already edited the question). $\endgroup$ – Biel Roig-Solvas Feb 26 '16 at 0:03
  • $\begingroup$ @Grubo: It's hard to say. For $\mathbb R^4$, I would have said that it should still be possible to arrange enough "negativity", but for $\mathbb R^3$ it may well be that you can't. Certainly the counterexample for $\mathbb R^5$ shows that a proof will have to go into detail and can't just use general properties of the $\operatorname{sinc}$ function. $\endgroup$ – joriki Feb 26 '16 at 0:29
  • 1
    $\begingroup$ really nice!!!!. I am curious to know how you came to this solution? $\endgroup$ – dineshdileep Feb 26 '16 at 5:44
  • $\begingroup$ @dineshdileep: I'm afraid I don't have a whole lot to say about that. I wanted as many negative values off the diagonal as possible, and I realized that with a simplex I can make them all equal. $\endgroup$ – joriki Feb 26 '16 at 7:51
2
$\begingroup$

Here is another approach (still incomplete).

For $x_{1}, ..., x_{N} \in \mathbb{R}^{d}$, let $\parallel . \parallel_{d}$ denote the $d$-dimensional norm. We have $S(i,j) = \frac{\sin\left(\parallel x_{i} - x_{j} \parallel_{d}\right)}{\parallel x_{i} - x_{j} \parallel_{d}} = \displaystyle\prod_{k=1}^{\infty}\cos\left(\frac{\parallel x_{i} - x_{j} \parallel_{d}}{2^{k}}\right)$, where the last equality is due to Viete (see eq. (18) here). Due to Schur product theorem, answering the OP's question is then equivalent to answer whether the matrix $C_{k}(i,j) = \cos\left(\frac{\parallel x_{i} - x_{j} \parallel_{d}}{2^{k}}\right)$, where $k$ is a fixed natural number, is positive semidefinite or not. The previous sentence is, in turn, same as asking whether $\cos(.)$ is a positive semidefinite radial function or not. It is easy to verify that the answer is yes for $d=1$. Sometime back, I remember seeing that for higher $d$ the answer is generally not true, as joriki pointed out, following some integral transform results due to I.J. Schoenberg, but I don't seem to find the exact reference for the cosine result now. Somebody more familiar with radial basis functions and approximation theory literature may help here to pinpoint the result.

$\endgroup$
  • $\begingroup$ Though incomplete, this is really informative!!. $\endgroup$ – dineshdileep Mar 2 '16 at 7:32

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.