2
$\begingroup$

(Note: I have asked this question before on math.stackexchangecom, but it wasn't answered, so I am trying again here).

The question is pretty much in the title; $X$ is an $n\times r$ matrix with $n>r$, and of course I am asking for the limit in $\epsilon \rightarrow 0$.

The interesting case is the case in which there are some zeroes on the diagonal of $\Delta$; if there aren’t any, it is straightforward.

I am interested both by a nice expression of the limit and by a way to compute it numerically without rounding issues.

I am aware that the limit is proportional to the comatrix of $X'\Lambda X$ where $\Lambda$ is obtained by replacing the zeroes on the diagonal of $\Delta$ by ones, and other entries by $0$, but I am hoping for something much better. Considering the $QR$ decomposition of $X$ seems a good starting point but I wasn’t able to go anywhere from this.

Example

With $X = \left[\begin{matrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{matrix}\right]$ and $\Delta = \left[\begin{matrix} 8 & 0& 0\\ 0& 2 &0 \\ 0& 0& \varepsilon \end{matrix}\right]$ it is easy to see that $$ (X' \Delta^{-1} X) = \left[\begin{matrix} 5/8 + 1/\varepsilon & 9/8 + 3/\varepsilon \\ 9/8 + 3/\varepsilon & 17/8 + 9/\varepsilon\end{matrix}\right] $$ and its determinant is $1/\varepsilon + 1/16$, hence the limit in $\varepsilon =0$ is $$\left[\begin{matrix} 9 & -3 \\ -3 & 1 \\ \end{matrix}\right].$$

$\endgroup$
2
  • $\begingroup$ Your example doesn't seem to match the description. You speak of $\Delta + \varepsilon I$, but then you use as $\Delta$ a diagonal matrix that already contains a $\varepsilon$. $\endgroup$ May 9, 2017 at 7:38
  • 1
    $\begingroup$ @FedericoPoloni It is easy to modify the example to match the description, just use a $(8+\varepsilon, 2 + \varepsilon, \epsilon)$ diagonal instead. It just makes the computation more complex without changing the limit. $\endgroup$
    – Elvis
    May 9, 2017 at 7:46

1 Answer 1

2
$\begingroup$

By the properties of Schur complements, your limit should be the $(1,1)$ block of $$ \begin{bmatrix} 0 & X'\\ X & -\Delta \end{bmatrix}^{-1}. $$ (when it is invertible). Not sure if this counts as "much better". It also depends on what you are trying to do with it -- numerical computation? You need a closed formula in a proof?

Added remark: matrices of this kind are sometimes called "saddle-point matrices" and appear often in quadratic optimization.

$\endgroup$
4
  • $\begingroup$ Great, it took me a few minutes but I finally understood. Very nice answer, thanks! This won’t settle the problem of computing it efficiently, but at least it gives me an understanding of what’s going on. I’ll wait a while before accepting your answer, in case someone comes with something even better. $\endgroup$
    – Elvis
    May 9, 2017 at 8:01
  • 1
    $\begingroup$ @Elvis I don't think you will find significant shortcuts. Computing that Schur complement is at the basis of some preconditioning techniques for saddle-point matrices, and is a studied problem: see Section 5 of Benzi-Golub-Liesen's Numerical solution of saddle point problems. In some settings, it may even be better to go through a linear system with that $2\times 2$ block matrix, since you can then use sparse matrix technology. If you mean "compute" as in scientific computing, you should consider asking a question on scicomp.stackexchange, adding more detail. $\endgroup$ May 9, 2017 at 8:14
  • $\begingroup$ Yes, I meant "compute" as in scientific computing, however in practice I can (and should) avoid this situation, I don’t really need it. I just met it and my curiosity was piqued. $\endgroup$
    – Elvis
    May 9, 2017 at 8:20
  • 1
    $\begingroup$ TL;DR version of my suggestions for computing it: (1) I imagine you need to compute $M^{-1}v$ for this matrix $M$ and some vector/matrix $v$, so don't use an explicit inverse if you can avoid it. (2) If $n$ is below 100-1000, form that $2\times2$ block matrix and solve a system with RHS [v;0]. (3) If $n$ is about 10,000 and $r$ is small, do the same but with a direct solver for sparse matrices (e.g. Matlab's `\`). (4) If it's even larger, use an iterative method (e.g. GMRES), look for preconditioners in the BGL paper and/or contact a numerical analysis person. $\endgroup$ May 9, 2017 at 8:30

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.