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

Improve this question
$\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$
    – Federico Poloni
    Commented 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
    Commented May 9, 2017 at 7:46

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Federico Poloni
    Commented 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
    Commented 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$
    – Federico Poloni
    Commented May 9, 2017 at 8:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .