3
$\begingroup$

Suppose we define $A^{*}$ of positive definite $A=X'X$ using following two steps:

  1. let $B=A^{-1}$
  2. scale columns of $B$ to obtain a matrix with $1$'s on the diagonal

For the case of singular $A$, we could use a tiny amount of Tikhonov regularization: $A^*=\lim_{\epsilon\to 0}(A+\epsilon I)^*$

Is there a name of this operation, or a way to compute it efficiently? Regularized inverse is efficient, but what to use for $\epsilon$?

Replacing regularized inverse with pseudo-inverse in step 1. gives a dramatically different result.

For instance, if we define $A=X'X$ with

$$X=\left( \begin{array}{ccc} 2 & -2 & 2 \\ -1 & 1 & 1 \\ -2 & -2 & 1 \\ 1 & 1 & 3 \\ \end{array} \right)$$

Then $(X'X)^{*}$ seems to be

$$\left( \begin{array}{cccc} 1 & \frac{1}{2} & -\frac{7}{4} & -\frac{7}{8} \\ 2 & 1 & -\frac{7}{2} & -\frac{7}{4} \\ -\frac{4}{7} & -\frac{2}{7} & 1 & \frac{1}{2} \\ -\frac{8}{7} & -\frac{4}{7} & 2 & 1 \\ \end{array} \right)$$

Motivation: empirically this operation seems give a way to obtain least-squares fitted coefficients of an autoregressive model of x, $x\approx Bx$ with diagonal of $B$ restricted to be 0's: $$B=I-(X'X)^*$$

Checks in colab

Edited with answer

The formula for non-singular version

$$B=(X'X)^{-1} (\text{zero_off_diagonal}[(X'X)^{-1}])^{-1}$$

where "zero_off_diagonal" sets all off-diagonal entries to zero.

Formula for singular version

$$P=I-X^\dagger X\\ B=P(\text{zero_off_diagonal}(P))^{-1}$$

notebook

$\endgroup$

1 Answer 1

3
$\begingroup$

$ \def\m#1{\left[\begin{array}{r}#1\end{array}\right]} \def\e{\epsilon} \def\qiq{\quad\implies\quad} \def\LR#1{\left(#1\right)} \def\Diag#1{\operatorname{Diag}\left(#1\right)} $Construct the orthoprojector $\LR{P^T=P=P^2}$ for the nullspace of $X$ $$\eqalign{ P &= {I-X^+X} \qiq XP=0 \qquad\qquad\quad \\ }$$ and use it to construct the function $$\eqalign{ D &= \Diag{P} \qiq \LR{X^TX}^* &= P D^{-1} \\ }$$ Calculating a pseudoinverse is more reliable than approximating a limit with an arbitrary $\e$.

Although there is a limit expression for the pseudoinverse, it's numerically unstable $$\eqalign{ X^+ = \lim_{\e\to 0}\LR{X^TX+\e I}^{-1}X^T \\\\ }$$


In terms of the motivating model, note that $$\eqalign{ B \;=\; I-\LR{X^TX}^* \;=\; \LR{D-P} D^{-1} \\ }$$

Update

Exact (rational) calculations for the pseudoinverse and the orthoprojector yield $$\eqalign{ X^+ &= \frac{1}{650}\m{ 114 & -122 & 40 \\ -97 & 81 & 80 \\ -158 & -116 & 70 \\ 9 & 93 & 140} \\ P &= \frac{1}{325}\m{ 49 & 98 & -28 & -56 \\ 98 & 196 & -56 & -112 \\ -28 & -56 & 16 & 32 \\ -56 & -112 & 32 & 64 } }$$ resulting in $$\eqalign{ D^{-1} &= \m{ \frac{325}{49} & 0 & 0 & 0 \\ 0 & \frac{325}{196} & 0 & 0 \\ 0 & 0 & \frac{325}{16} & 0 \\ 0 & 0 & 0 & \frac{325}{64} } \\ PD^{-1} &= \m{ 1 & \frac{1}{2} & -\frac{7}{4} & -\frac{7}{8} \\ 2 & 1 & -\frac{7}{2} & -\frac{7}{4} \\ -\frac{4}{7} & -\frac{2}{7} & 1 & \frac{1}{2} \\ -\frac{8}{7} & -\frac{4}{7} & 2 & 1 } }$$

$\endgroup$
7
  • $\begingroup$ using "pseudo-inverse" in formula above actually gives a dramatically different result, added details. I'm guessing pseudoinverse gives the limit A+eps, but what's needed is to take limit (A+eps)/diag(A+eps), these two "eps" don't allow you to factor out the limit $\endgroup$ Jun 22 at 23:10
  • 1
    $\begingroup$ @YaroslavBulatov I updated the answer with calculations using rational arithmetic. Even performing the calculation in IEEE double precision, the result is within $10^{-15}$ of the rational result. $\endgroup$
    – greg
    Jun 22 at 23:58
  • $\begingroup$ thanks, I misunderstood your earlier reply, that indeed works! $\endgroup$ Jun 23 at 1:28
  • $\begingroup$ BTW, one thing I noticed is that while the original approach is unstable when matrix is close to singular, this approach fails when matrix is close to non-singular. IE, for that example $X$, if you add a column of values close to 0, then result will be far from coefficients estimated by fitting models directly $\endgroup$ Jun 23 at 18:49
  • $\begingroup$ Here's what I mean -- take a 4x4 data matrix of rank-3 with the last row all 0's. Orthoprojection method works fine. Now replace last row with tiny random values, orthoprojection method gives near-random results -- colab.research.google.com/drive/… $\endgroup$ Jun 23 at 19:37

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.