# Is it possible to prove that the off-diagonal blocks of the Cauchy matrix have numerical rank $O(\log n)$?

Suppose we have a $n\times n$ Cauchy matrix of which the $ij$-th entry is given by: $$A_{ij} = \frac{1}{a_i - b_j}$$ the assumption is that the distance between $\{a_i\}$ and $\{b_j\}$ is greater some positive constant, for example: $$a_k = e^{i\frac{(2k+1)\pi}{n}}, \quad b_k = e^{i\frac{2k\pi}{n}}$$ then we have $\displaystyle \min_{i,j} |a_i - b_j|\geq O(\sin(\pi/n))$, and we want to prove something like the off diagonal entries can be represented by: $$\frac{1}{a_i - b_j} = \sum^{O(\log(n))}_{k=1} C_k + O(\varepsilon)$$ Is this possible? or there is another type of rank bound for Cauchy matrix?

• Does this question relate to low-separation rank approximations of operators, like the work done by Beylkin and Mohlenkamp? – Geoff Oxberry Feb 14 '12 at 20:02
• Would this question more suitable for the math.stackexchange.com site? It seems more of a theoretical question in linear algebra rather than a computational one... – Paul Feb 14 '12 at 20:15
• @Paul: The thought crossed my mind. First, I want to see if a connection to numerical methods can be made before we discuss migrating. – Geoff Oxberry Feb 14 '12 at 20:26
• @Paul Thanks for the comment, the Cauchy or Cauchy like matrices arise from various computational problems, such as solving displacement equation, and computationally, as Jack Poulson said, Ming Gu claimed the bound is $O(\log(n))$ but he never proved it, I am just curious about the theory behind this numerical linear algebra problem. – Shuhao Cao Feb 14 '12 at 20:46
• I agree that something is wrong there. Judging from the question, Shuhao wanted something like $A \approx \sum_{k=1}^{O(\log n)} u_kv_k^*$, where the approximation is accurate up to an entrywise error of $\mathcal{O}(\epsilon)$. – alext87 Oct 1 '16 at 14:17

I know there has been a significant delay here. I also hope that it is not inappropriate to advertise personal work in this situation. I am making an exception to my usual policy because of the time frame.

The short answer to your question is: "yes" if $a_i$'s and $b_i$'s are real. (For complex $a_i$'s and $b_i$'s it is still true in practice, but more thinking is required)

Bernhard Beckermann and I just submitted a paper [1] that shows that if $AX-XB = F$ with $A$ and $B$ normal matrices, then the singular values of $X$ can be bounded as $$\sigma_{1+\nu k}(X) \leq Z_k(\sigma(A),\sigma(B))\|X\|_2, \qquad \nu = {\rm rank}(F),$$ where $\sigma(A)$ and $\sigma(B)$ are the spectra of $A$ and $B$, respectively, and $Z_k(E,F)$ is the so-called Zolotarev number. More precisely, $$Z_k(E,F) = \inf_{r\in\mathcal{R}_{k,k}} \frac{\sup_{z\in E}|r(z)|}{\inf_{z\in F}|r(z)|},$$ where $\mathcal{R}_{k,k}$ is the space of degree $(k,k)$ rational functions. This is called the third Zolotarev problem.

In the case of the Cauchy matrix, let $A = {\rm diag}(a_1,\ldots,a_n)$ and $B = {\rm diag}(b_1,\ldots,b_n)$ then $$AC - CB = \begin{bmatrix}1\\\vdots\\1 \end{bmatrix}\begin{bmatrix}1&\cdots&1 \end{bmatrix}.$$ Hence, $\nu=1$ and $$\sigma_{1+k}(C) \leq Z_k([a_1,\ldots,a_n],[b_1,\ldots,b_n])\|C\|_2.$$ Unfortunately, discrete Zolotarev number (like above) are very difficult to bound.

If we make the additional assumption (which is appropriate for off-diagonal blocks) that $[a_1,\ldots,a_n]\subseteq [a,b]$ and $[b_1,\ldots,b_n]\subseteq [c,d]$, where $[a,b]$ and $[c,d]$ are disjoint intervals, then $$\sigma_{1+k}(C) \leq Z_k([a,b],[c,d])\|C\|_2.$$ In Corollary 7 of [1], we showed that this leads to the singular value bounds $$\sigma_{1+k}(C) \leq 4\left[{\rm exp}\left(\frac{\pi^2}{2\log(16\gamma)}\right)\right]^{-2k}\|C\|_2,$$ where $\gamma$ is the absolute value of the cross-ratio of $a$, $b$, $c$, and $d$. Namely, $$\gamma = \frac{|c-a|\,|d-b|}{|c-b|\,|d-a|}.$$ This gives you a bound on the numerical rank of $C$ as $${\rm rank}_\epsilon(C) \leq \Bigg\lceil \frac{\log(16\gamma)\log(4/\epsilon)}{\pi^2}\Bigg\rceil = \mathcal{O}(\log\gamma \log(1/\epsilon)).$$ For a case where $\gamma = \mathcal{O}(n)$ and a $\log(n)$ term appears see the Hilbert matrix: https://mathoverflow.net/questions/137059/the-singular-values-of-the-hilbert-matrix/251187

Edit: In your case the $a_i$'s and $b_i$'s are complex valued. This is more tricky and more related to Section 5.1 of [1].

This is perhaps dodging your question, but why do you want to insist on low-rank off-diagonal blocks? Displacement structure is also data-sparse and allows for stable quadratic-complexity factorization algorithms. There is also a nice survey paper on the subject.

Ming Gu gave a talk which uses Hierarchically Semi-Separable (HSS) matrices to compress the Cauchy-like matrices which arise from a Fourier transform of Toeplitz matrices, resulting in an $O(n \log n)$ approximate solution, but I'm not certain if the compression technique will work for general Cauchy matrices.

• Ming Gu also used this property of off-diagonal blocks having a $O(\log(n))$ rank to get that $O(n \log(n))$ complexity, rather than using the displacement rank. Here I am just curious how did he get this $O(\log(n))$ rank theoretically, but he never mentioned any proof in his paper, merely a numerical result. – Shuhao Cao Feb 14 '12 at 20:52
• @Jon: If you look at the seventh slide of his talk, you can see that there is a very special structure to the Cauchy matrix: $a_i = \omega^{2i}$, and $b_j = \omega^{2i+1}$, indexing from zero. – Jack Poulson Feb 14 '12 at 20:56
• The Cauchy matrix is the same matrix as I pointed out there. I also tested some random Cauchy matrix, and found that the singular value decays very quickly for off-diagonal block part. Ming Gu chose this matrix because he used 1 and -1 when he transformed the toeplitz matrix into Cauchy-like matrix using the displacement equation. By doing this he could maximize the minimal value of the denominators of the entries for the Cauchy matrix, and enhance the stability of the numerical computation. – Shuhao Cao Feb 14 '12 at 21:13
• @Jon: Ah, good point. $\omega := \exp(i \pi / n)$. I would have to think more; maybe plotting the singular vectors would help... – Jack Poulson Feb 14 '12 at 21:21