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?
Tell me more
×
Computational Science Stack Exchange is a question and answer site for
scientists using computers to solve scientific problems. It's 100% free, no registration required.
|
|
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. |
|||||||||
|
