Take invertible matrix $A$, and set a diagonal entry of $A$ to $\infty$. Can we use $A^{-1}$ to find the pseudo inverse of this new matrix?

47 Views Asked by At

Consider having $A$, with $A^{-1}$ previously calculated.

Say I apply a rank 1 update on $A$ using $v = (\infty,0,0,0,0)$: $${B} = vv^T A $$

Clearly A is no longer invertible, but the pseudo inverse still exists.

We can apply the sherman morrison formula ${\displaystyle \left(A+vv^{\textsf {T}}\right)^{-1}=A^{-1}-{A^{-1}vv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}v}.}$

However, the denominator here is obviously not well defined.

Is there another route to efficiently calculate the pseudo inverse of $B$?

We have the standard formula for inverting 2x2 block matrices, i.e for S invertible,

$$A=\begin{bmatrix} C &D \\ E&F \end{bmatrix} $$ If $C^{-1}$ or $F^{-1}$ exist, then we can compute $S^{-1}$. In our case, $F^{-1}$ must exist so we can write

$$B=\begin{bmatrix} \infty &D \\ E&F \end{bmatrix} $$ $$B^{-1}=\begin{bmatrix} 0 &0 \\ 0&F^{-1} \end{bmatrix} $$

However, we would like to be able to calculate $B^{-1}$ without first computing $F^{-1}$ - in general the index of the value that is set to $\infty$ is not known, so this would still require computing the inverse of a $(n-1)\times(n-1)$ matrix.

1

There are 1 best solutions below

0
On

Computation of the above:

Let $v = (k,0,0)$ for simplicity

Then we can calculate: $1+v^TA^{-1}v^T$ = $1+k^2A^{-1}_{11}$

$$ A^{-1}v v^T A^{-1} =(v^TA^{-T})^{T}v^T A^{-1} = k^2\cdot B\cdot D,\text{ where} $$

$$ D = \cdot \begin{bmatrix} Row_1(A) \\ 0 \\ ... \\ 0 \end{bmatrix}, $$ $$ B = \cdot \begin{bmatrix} Col_1(A) & 0 & \ldots & 0 \\ \end{bmatrix} $$

i.e $D_{ij} = \begin{cases} A_{ij},& \text{if } j=1 \\ 0, & \text{otherwise} \end{cases},$ $B_{ij} = \begin{cases} A_{ij},& \text{if } i=1 \\ 0, & \text{otherwise} \end{cases}$

Then

$$(A+vv^T)^{-1} =A^{-1} - \frac{k^2}{1+k^2A^{-1}_{11}} BD $$

Now, as $k\to+\infty$, the fraction tends to $1/A^{-1}_{11}$.