2305/2305.01716.md

Title: The Pseudoinverse of 𝐴=𝐶⁢𝑅 is 𝐴⁺=𝑅⁺⁢𝐶⁺ (?)

URL Source: https://arxiv.org/html/2305.01716

Markdown Content: Back to arXiv

This is experimental HTML to improve accessibility. We invite you to report rendering errors. Use Alt+Y to toggle on accessible reporting links and Alt+Shift+Y to toggle off. Learn more about this project and help improve conversions.

Why HTML? Report Issue Back to Abstract Download PDF License: arXiv.org perpetual non-exclusive license arXiv:2305.01716v3 [math.NA] 26 Mar 2024 The Pseudoinverse of 𝐴

𝐶 ⁢ 𝑅 is 𝐴 +

𝑅 + ⁢ 𝐶 + (?) Michał P. Karpowicz Gilbert Strang michal.karpowicz@nask.pl gilstrang@gmail.com NASK PIB MIT

Abstract

This paper gives three formulas for the pseudoinverse of a matrix product 𝐴

𝐶 ⁢ 𝑅 . The first is sometimes correct, the second is always correct, and the third is almost never correct. But that third randomized pseudoinverse 𝐴 𝑟 + may be very useful when 𝐴 is a very large matrix.

1.

𝐴 +

𝑅 + ⁢ 𝐶 + when 𝐴

𝐶 ⁢ 𝑅 and 𝐶 has independent columns and 𝑅 has independent rows.

2.

𝐴 +

( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + is always correct.

3.

𝐴 𝑟 +

( 𝑃 𝑇 ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ 𝑃 𝑇 ⁢ 𝐶 ⁢ 𝑅 ⁢ 𝑄 ⁢ ( 𝐶 ⁢ 𝑅 ⁢ 𝑄 ) +

𝐴 + only when rank ⁢ ( 𝑃 𝑇 ⁢ 𝐴 )

rank ⁢ ( 𝐴 ⁢ 𝑄 )

rank ⁢ ( 𝐴 ) with 𝐴

𝐶 ⁢ 𝑅 .

The statement in the title is not generally true, as the following example shows:

𝐶

[ 1
0
] ⁢ 𝑅

[ 1

1
] ⁢ ( 𝐶 ⁢ 𝑅 ) +

[ 1 ] ⁢ 𝑅 + ⁢ 𝐶 +

[ 1 2

1 2

] ⁢ [ 1

0
]

[ 1 2 ] .

Here, 𝐶 has a full row rank and 𝑅 has a full column rank. We need to have it the other way around in Theorem 1. Then Theorem 2 will give a formula for the pseudoinverse of 𝐴

𝐶 ⁢ 𝑅 that applies in every case.

When the 𝑚 by 𝑟 matrix 𝐶 has 𝑟 independent columns (full column rank  𝑟 ), and the 𝑟 by 𝑛 matrix 𝑅 has 𝑟 independent rows (full row rank 𝑟 ), the pseudoinverse 𝐶 + is the left inverse of 𝐶 , and the pseudoinverse 𝑅 + is the right inverse of 𝑅  :

𝐶 +

( 𝐶 T ⁢ 𝐶 ) − 1 ⁢ 𝐶 T ⁢  has  ⁢ 𝐶 + ⁢ 𝐶

𝐼 𝑟 and 𝑅 +

𝑅 T ⁢ ( 𝑅 ⁢ 𝑅 T ) − 1 ⁢  has  ⁢ 𝑅 ⁢ 𝑅 +

𝐼 𝑟 .

In this case, the 𝑚 by 𝑛 matrix 𝐴

𝐶 ⁢ 𝑅 will also have rank 𝑟 and the statement correctly claims that its 𝑛 by 𝑚 pseudoinverse is 𝐴 +

𝑅 + ⁢ 𝐶 + .

Theorem 1.

The pseudoinverse 𝐴 + of a product 𝐴

𝐶 ⁢ 𝑅 is the product of the pseudoinverses 𝑅 + ⁢ 𝐶 + (as for inverses) when 𝐶 has full column rank and 𝑅 has full row rank 𝑟 .

The simplest proof verifies the four Penrose identities [4] that determinethe pseudoinverse 𝐴 + of any matrix 𝐴  :

𝐴 ⁢ 𝐴 + ⁢ 𝐴

𝐴 𝐴 + ⁢ 𝐴 ⁢ 𝐴 +

𝐴 + ( 𝐴 + ⁢ 𝐴 ) T

𝐴 + ⁢ 𝐴 ( 𝐴 ⁢ 𝐴 + ) T

𝐴 ⁢ 𝐴 +

(1)

Our goal is a different proof of 𝐴 +

𝑅 + ⁢ 𝐶 + , starting from first principles. We begin with the “four fundamental subspaces” associated with any 𝑚 by 𝑛 matrix 𝐴 of rank 𝑟 . Those are the column space C and nullspace N of 𝐴 and 𝐴 T .

Note that every matrix 𝐴 gives an invertible map (Figure 1) from its row space C ⁢ ( 𝐴 T ) to its column space C ⁢ ( 𝐴 ) . If 𝒙 and 𝒚 are in the row space and 𝐴 ⁢ 𝒙

𝐴 ⁢ 𝒚 , then 𝐴 ⁢ ( 𝒙 − 𝒚 )

𝟎 . Therefore 𝒙 − 𝒚 is in the nullspace N ⁢ ( 𝐴 ) as well as the row space. So 𝒙 − 𝒚 is orthogonal to itself and 𝒙

𝒚 .

The pseudoinverse 𝐴 + in Figure 2 inverts the row space to column space map in Figure 1 when N ⁢ ( 𝐴 𝑇 )

N ⁢ ( 𝐴 + ) . If 𝒃 𝑐 and 𝒅 𝑐 are in the column space C ⁢ ( 𝐴 ) and 𝒙

𝐴 + ⁢ 𝒃 𝑐

𝐴 + ⁢ 𝒅 𝑐 , then 𝐴 + ⁢ ( 𝒃 𝑐 − 𝒅 𝑐 )

𝟎 and 𝒃 𝑐 − 𝒅 𝑐 is in the nullspace N ⁢ ( 𝐴 + ) . Therefore, if N ⁢ ( 𝐴 + )

N ⁢ ( 𝐴 𝑇 ) , then 𝒃 𝑐 − 𝒅 𝑐 is in the nullspace of 𝐴 𝑇 and the column space of 𝐴 , it is orthogonal to itself and ( 𝒃 𝑐 − 𝒅 𝑐 ) 𝑇 ⁢ ( 𝒃 𝑐 − 𝒅 𝑐 )

0 with 𝒃 𝑐

𝒅 𝑐 . For all vectors 𝒃 𝑛 in the orthogonal complement of C ⁢ ( 𝐴 ) , we have 𝐴 T ⁢ 𝒃 𝑛

𝟎 and 𝐴 + ⁢ 𝒃 𝑛

𝟎 . Theorem 1 shows why N ⁢ ( 𝐴 𝑇 )

N ⁢ ( 𝐴 + ) and 𝐴 + is the inverse map.

That upper map from the row space C ⁢ ( 𝐴 T ) to the column space C ⁢ ( 𝐴 ) is inverted by the pseudoinverse 𝐴 + in Figure 2. And the nullspace of 𝑨 + is the same as the nullspace of 𝑨 𝐓 —the orthogonal complement of C ⁢ ( 𝐴 ) . Thus 𝟏 / 𝟎

𝟎 for 𝐴 + . In the extreme case, the pseudoinverse of 𝐴

zero matrix ( 𝑚 by 𝑛 ) is 𝐴 +

zero matrix ( 𝑛 by 𝑚 ).

dim 𝒓

C ⁢ ( 𝑨 𝐓 )

dim 𝒏 − 𝒓

N ⁢ ( 𝑨 )

R 𝒏

all combinations of the rows of 𝐴 𝒙 𝒓 𝐴 ⁢ 𝒙 𝒓

𝒃 𝒄 𝒙

𝒙 𝒓 + 𝒙 𝒏 𝐴 ⁢ 𝒙

𝒃 𝒄 𝒙 𝒏 𝐴 ⁢ 𝒙 𝒏

𝟎 all vectors orthogonal to the rows dim 𝒓

C ⁢ ( 𝑨 )

dim 𝒎 − 𝒓

N ⁢ ( 𝑨 𝐓 )

R 𝒎

all combinations of the columns of 𝑨 𝒃 𝒄 all vectors orthogonal to the columns Figure 1: 𝐴 ⁢ 𝒙 𝒓

𝒃 is in the column space of 𝐴 and 𝐴 ⁢ 𝒙 𝒏

𝟎 . The complete solution to 𝐴 ⁢ 𝒙

𝒃 is 𝒙

 one  𝒙 𝒓 +  any  𝒙 𝒏 . dim 𝒓

C ⁢ ( 𝑨 𝐓 )

dim 𝒏 − 𝒓

N ⁢ ( 𝑨 )

R 𝒏

all combinations of the rows of 𝑨 (columns of 𝑨 𝐓 ) 𝒙 𝒓 𝐴 + ⁢ 𝒃 𝒄

𝒙 𝒓 𝒃

𝒃 𝒄 + 𝒃 𝒏 𝐴 + ⁢ 𝒃

𝒙 𝒓 𝒃 𝒏 𝐴 + ⁢ 𝒃 𝒏

𝟎 all vectors orthogonal to the rows of 𝑨 dim 𝒓 dim 𝒎 − 𝒓

R 𝒎

C ⁢ ( 𝑨 )

N ⁢ ( 𝑨 + )

N ⁢ ( 𝑨 𝐓 )

all combinations of the columns of 𝑨 (rows of 𝑨 𝐓 ) 𝒃 𝒄 all vectors orthogonal to the columns of 𝑨 Figure 2:The four subspaces for 𝐴 + are the four subspaces for 𝐴 T .

The proof of Theorem 1 begins with a simple Lemma.

Lemma 1.

We have 𝐂 ⁢ ( 𝐴 )

𝐂 ⁢ ( 𝐴 ⁢ 𝐵 ) if and only if rank ⁢ ( 𝐴 )

rank ⁢ ( 𝐴 ⁢ 𝐵 ) , and 𝐍 ⁢ ( 𝐵 )

𝐍 ⁢ ( 𝐴 ⁢ 𝐵 ) if and only if rank ⁢ ( 𝐵 )

rank ⁢ ( 𝐴 ⁢ 𝐵 ) .

Proof : Always 𝐂 ⁢ ( 𝐴 ) ⊃ 𝐂 ⁢ ( 𝐴 ⁢ 𝐵 ) and 𝐍 ⁢ ( 𝐴 ⁢ 𝐵 ) ⊃ 𝐍 ⁢ ( 𝐵 ) . In each pair, equality of dimensions guarantees equality of spaces. The column space can only become smaller, and the nullspace larger.

Proof of Theorem 1: We will show that 𝐍 ⁢ ( 𝐴 T ) ⊂ 𝐍 ⁢ ( 𝐴 + ) and 𝐍 ⁢ ( 𝐴 T ) ⊃ 𝐍 ⁢ ( 𝐴 + ) , and that 𝐂 ⁢ ( 𝐴 T ) ⊂ 𝐂 ⁢ ( 𝐴 + ) and 𝐂 ⁢ ( 𝐴 T ) ⊃ 𝐂 ⁢ ( 𝐴 + ) when 𝐴 +

𝑅 + ⁢ 𝐶 + .

Step 1 :  N ⁢ ( 𝐴 T ) ⊂ N ⁢ ( 𝐴 + ) . Every vector 𝒃 𝒏 in the nullspace of 𝐴 T is also in the nullspace of 𝐴 + .

If 𝐴 T ⁢ 𝒃 𝒏

0 , then 𝑅 T ⁢ 𝐶 T ⁢ 𝒃 𝒏

0 . Since 𝐶 T has full column rank, we conclude that 𝐶 T ⁢ 𝒃 𝒏

( 𝐶 T ⁢ 𝐶 ) − 1 ⁢ 𝐶 T ⁢ 𝒃 𝒏

𝐶 + ⁢ 𝒃 𝒏

0 and 𝒃 𝒏 is in the nullspace of 𝐶 + . However, by Lemma 1, we also have N ⁢ ( 𝐶 + )

N ⁢ ( 𝑅 + ⁢ 𝐶 + )

N ⁢ ( 𝐴 + ) . Every 𝒃 𝒏 in the nullspace of 𝐴 T is also in the nullspace of 𝐴 + .

Step 2 :  N ⁢ ( 𝐴 T ) ⊃ N ⁢ ( 𝐴 + ) . Every vector 𝒃 𝒏 in the nullspace of 𝐴 + is also in the nullspace of 𝐴 T .

Suppose that 𝐴 + ⁢ 𝒃 𝒏

𝑅 + ⁢ 𝐶 + ⁢ 𝒃 𝒏

𝟎 . Since 𝑅 ⁢ 𝑅 +

𝐼 𝑟 , we have 𝐴 ⁢ 𝐴 + ⁢ 𝒃 𝒏

𝐶 ⁢ 𝑅 ⁢ 𝑅 + ⁢ 𝐶 + ⁢ 𝒃 𝒏

𝐶 ⁢ ( 𝐶 T ⁢ 𝐶 ) − 1 ⁢ 𝐶 T ⁢ 𝒃 𝒏

𝟎 . Since 𝐶 ⁢ ( 𝐶 T ⁢ 𝐶 ) − 1 has full column rank, we see that 𝐶 T ⁢ 𝒃 𝒏

𝟎 , so 𝒃 𝒏 is orthogonal to every column of 𝐶 . Therefore 𝒃 𝒏 ∈ N ⁢ ( 𝐴 T ) .

Step 3 :  C ⁢ ( 𝐴 T ) ⊂ C ⁢ ( 𝐴 + ) . Every vector 𝒙 in the row space of 𝐴 is also in the column space of 𝐴 + .

We have 𝒙

𝐴 T ⁢ 𝒚

𝑅 T ⁢ 𝐶 T ⁢ 𝒚

𝑅 T ⁢ [ ( 𝑅 ⁢ 𝑅 T ) − 1 ⁢ 𝑅 ⁢ 𝑅 T ] ⁢ 𝐶 T ⁢ 𝒚

𝑅 + ⁢ 𝑅 ⁢ ( 𝑅 T ⁢ 𝐶 T ⁢ 𝒚 )

𝑅 + ⁢ 𝑅 ⁢ 𝒙 . So by Lemma 1, we conclude that 𝒙 ∈ C ⁢ ( 𝑅 + )

C ⁢ ( 𝑅 + ⁢ 𝐶 + )

C ⁢ ( 𝐴 + ) .

Step 4 :  C ⁢ ( 𝐴 T ) ⊃ C ⁢ ( 𝐴 + ) . Every vector 𝒙 in the column space of 𝐴 + is also in the row space of 𝐴 .

Given 𝒃

𝐴 ⁢ 𝒙

𝐶 ⁢ 𝑅 ⁢ 𝒙 , we have

𝒙

𝐴 + ⁢ 𝒃

𝑅 + ⁢ 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ⁢ 𝒙

𝑅 T ⁢ ( 𝑅 ⁢ 𝑅 T ) − 1 ⁢ ( 𝐶 T ⁢ 𝐶 ) − 1 ⁢ 𝐶 T ⁢ 𝐶 ⁢ 𝑅 ⁢ 𝒙

𝑅 T ⁢ ( 𝑅 ⁢ 𝑅 T ) − 1 ⁢ 𝑅 ⁢ 𝒙

So again by Lemma 1, we conclude that 𝒙 ∈ C ⁢ ( 𝑅 T )

C ⁢ ( 𝑅 T ⁢ 𝐶 T )

C ⁢ ( 𝐴 T ) .

An 𝑚 by 𝑛 matrix of rank 𝑟 has many factorizations. The simplest form of 𝐴

𝐶 ⁢ 𝑅 fills 𝐶 with the first 𝑟 independent columns of 𝐴 . Those columns are a basis for the column space of 𝐴 . Then column 𝑗 of 𝑅 specifies the combination of columns of 𝐶 that produces column 𝑗 of 𝐴 . This example has column 3 = column 1 + column 2:

𝐴

[ 1

4

5

2
3
5 ]

[ 1

4

2

3 ] ⁢ [ 1

0

1

0
1
1 ]

𝐶 ⁢ 𝑅 .

That matrix 𝑅 contains the nonzero rows of the reduced row echelon form of 𝐴 . It also reveals nullspace N ⁢ ( 𝐴 )

N ⁢ ( 𝑅 ) .

𝐴

𝐶 ⁢ 𝑅 expresses this classical “elimination by row operations” as a matrix factorization [5, 6]. It is slower and less stable numerically than the SVD, but rational 𝐴 produces rational 𝐶 and 𝑅 and 𝐶 + and 𝑅 + . The following useful formula shows that explicitly:

𝐴 +

𝑅 + ⁢ 𝐶 +

𝑅 T ⁢ ( 𝑅 ⁢ 𝑅 T ) − 1 ⁢ ( 𝐶 T ⁢ 𝐶 ) − 1 ⁢ 𝐶 T

𝑅 T ⁢ ( 𝐶 T ⁢ 𝐴 ⁢ 𝑅 T ) − 1 ⁢ 𝐶 T .

(2)

The inverses of square rational matrices 𝑅 ⁢ 𝑅 𝑇 and 𝐶 𝑇 ⁢ 𝐶 are formed by elementary operations and division by a rational determinant. Therefore, the pseudoinverse of 𝐴 is rational when 𝐴 is rational.

The ranks of 𝐴 + and 𝐴 are equal when 𝐴 + is the inverse map. Then,

𝒃

𝐴 ⁢ 𝒙 + ( 𝐼 𝑚 − 𝐴 ⁢ 𝐴 + ) ⁢ 𝒘

is a solution of 𝐴 + ⁢ 𝒃

𝒙 for arbitrary 𝒘 . We have 𝐴 + ⁢ 𝒃

𝐴 + ⁢ 𝐴 ⁢ 𝒙

𝒙 , since 𝐴 + ⁢ 𝐴 ⁢ 𝐴 +

𝐴 + when 𝐴 + and 𝐴 have equal ranks.

That is not always the case and not always necessary. Consider the rank-deficient

𝐴

[ 1

0

0

0

0
0
]

[ 1

0

0
] ⁢ [ 1
0
]

𝐶 0 ⁢ 𝑅 0 .

When we complete 𝐶 0 and 𝑅 0 to get square invertible [ 𝐶 0 , 𝐶 1 ] and [ 𝑅 0 , 𝑅 1 ] 𝑇 , then the generalized 𝐴

𝐶 ⁢ 𝑅 becomes

𝐴

[ 𝐶 0

𝐶 1

] ⁢ [ 𝐼 𝑟

0

0

0

] ⁢ [ 𝑅 0

𝑅 1
]

𝐶 ¯ ⁢ 𝑅 ¯

and its generalized inverse is

𝐺

[ 𝑅 0

𝑅 1

] − 1 ⁢ [ 𝐼 𝑟

𝑍 11

𝑍 21

𝑍 22

] ⁢ [ 𝐶 0

𝐶 1

] − 1

for arbitrary 𝑍 𝑖 ⁢ 𝑗 of proper size [8]. The first Penrose identity holds, 𝐴 ⁢ 𝐺 ⁢ 𝐴

𝐴 , but the second one gives

𝐺 ⁢ 𝐴 ⁢ 𝐺

[ 𝑅 0

𝑅 1

] − 1 ⁢ [ 𝐼 𝑟

𝑍 12

𝑍 21

𝑍 21 ⁢ 𝑍 12

] ⁢ [ 𝐶 0

𝐶 1

] − 1 .

We have 𝐺 ⁢ 𝐴 ⁢ 𝐺

𝐺 only if 𝑍 22

𝑍 21 ⁢ 𝑍 12 . Then 𝐴 and 𝐺 have equal ranks and 𝐺 is the inverse map. Otherwise, the nullspaces N ⁢ ( 𝐴 𝑇 ) and N ⁢ ( 𝐺 ) are different. For

𝐴 𝑇

[ 1

0

0

0
0
0 ]

[ 1

0
] ⁢ [ 1
0
0 ]

𝐶 2 ⁢ 𝑅 2

the nullspace N ⁢ ( 𝐴 𝑇 )

N ⁢ ( 𝑅 2 ) is spanned by ( 0 , 1 , 0 ) 𝑇 and ( 0 , 0 , 1 ) 𝑇 . For:

𝐺

[ 1

3

2

3
3
2 ]

[ 1

3

3

3

] ⁢ [ 1

0

0

0
1
2 / 3 ]

𝐶 3 ⁢ 𝑅 3 ,

we see that N ⁢ ( 𝐺 )

N ⁢ ( 𝑅 3 ) is spanned by ( 0 , − 2 / 3 , 0 ) 𝑇 . Here 𝐴 ⁢ 𝐺 ⁢ 𝐴

𝐴 , but 𝐺 ⁢ 𝐴 ⁢ 𝐺 is not equal to 𝐺 with 1

rank ⁢ ( 𝐴 ) < rank ⁢ ( 𝐺 )

2 . Also, neither 𝐴 ⁢ 𝐺 nor 𝐺 ⁢ 𝐴 gives an identity matrix. Still,

𝒙

𝐺 ⁢ 𝒃 + ( 𝐼 𝑛 − 𝐺 ⁢ 𝐴 ) ⁢ 𝒛

solves 𝐴 ⁢ 𝒙

𝐴 ⁢ 𝐺 ⁢ 𝒃 + ( 𝐴 − 𝐴 ⁢ 𝐺 ⁢ 𝐴 ) ⁢ 𝒛

𝐴 ⁢ 𝐺 ⁢ 𝒃

𝒃 for arbitrary 𝒛 .

The necessary and sufficient conditions for 𝐴 +

( 𝐶 ⁢ 𝑅 ) +

𝑅 + ⁢ 𝐶 + are surprisingly complex. Greville formulated them in [7]. The reverse order law for pseudoinverse, ( 𝐶 ⁢ 𝑅 ) +

𝑅 + ⁢ 𝐶 + , holds if and only if

𝐂 ⁢ ( 𝑅 ⁢ 𝑅 𝑇 ⁢ 𝐶 𝑇 ) ⊂ 𝐂 ⁢ ( 𝐶 𝑇 ) and 𝐂 ⁢ ( 𝐶 𝑇 ⁢ 𝐶 ⁢ 𝑅 ) ⊂ 𝐂 ⁢ ( 𝑅 ) .

(3)

Matrix 𝑅 maps 𝒙 𝑟

𝑅 𝑇 ⁢ 𝐶 𝑇 ⁢ 𝒚 from the row space C ⁢ ( 𝐴 𝑇 ) into the row space C ⁢ ( 𝐶 𝑇 ) . Then matrix 𝐶 takes 𝑅 ⁢ 𝒙 𝑟 to the column space C ⁢ ( 𝐴 ) , so we have 𝐶 ⁢ 𝑅 ⁢ 𝒙 𝑟

𝐴 ⁢ 𝒙 𝑟

𝒃 𝑐 . Matrix 𝐶 𝑇 maps 𝒃 𝑐 into the column space C ⁢ ( 𝑅 ) . Then 𝑅 𝑇 ⁢ 𝐶 𝑇 ⁢ 𝒃 𝑐 is also in the row space C ⁢ ( 𝐴 𝑇 ) . The inverse map 𝐶 + identifies 𝑅 ⁢ 𝒙 𝑟 in the column space C ⁢ ( 𝑅 ) and then 𝑅 + gives 𝒙 𝑟

𝑅 + ⁢ 𝐶 + ⁢ 𝒃 𝑐 in Figure  3. The reverse order law demands that

𝐶 + ⁢ 𝐶 ⁢ ( 𝑅 ⁢ 𝐴 𝑇 )

𝑅 ⁢ 𝐴 𝑇 and 𝑅 ⁢ 𝑅 + ⁢ ( 𝐶 𝑇 ⁢ 𝐴 )

𝐶 𝑇 ⁢ 𝐴 .

(4)

It follows that 𝐶 and 𝑅 solve the two-sided projection equation:

𝐶 + ⁢ 𝐶 ⁢ ( 𝑅 ⁢ 𝑅 𝑇 ⁢ 𝐶 𝑇 ⁢ 𝐶 ) ⁢ 𝑅 ⁢ 𝑅 +

𝑅 ⁢ 𝑅 𝑇 ⁢ 𝐶 𝑇 ⁢ 𝐶 .

(5)

For the full-rank factorization of Theorem 1 the equation holds with 𝐶 + ⁢ 𝐶

𝐼 𝑟

𝑅 ⁢ 𝑅 + .

𝑅 ⁢ 𝐂 ⁢ ( 𝐴 𝑇 )

𝐂 ⁢ ( 𝑅 ⁢ 𝑅 𝑇 ⁢ 𝐶 𝑇 ) ⊂ 𝐂 ⁢ ( 𝐶 𝑇 ) C ⁢ ( 𝐶 𝑇 ) 𝒙 𝑟 ∈ C ⁢ ( 𝑅 𝑇 ⁢ 𝐶 𝑇 ) C ⁢ ( 𝐶 ⁢ 𝑅 ) ∋ 𝒃 𝑐 C ⁢ ( 𝑅 ) 𝐶 𝑇 ⁢ 𝐂 ⁢ ( 𝐴 )

𝐂 ⁢ ( 𝐶 𝑇 ⁢ 𝐶 ⁢ 𝑅 ) ⊂ 𝐂 ⁢ ( 𝑅 ) 𝑅 ⁢ 𝒙 𝑟

𝒘 𝐶 ⁢ 𝑅 ⁢ 𝒙 𝑟

𝐴 ⁢ 𝒙 𝑟

𝒃 𝑐 𝐴 𝑇 ⁢ 𝐴 ⁢ 𝒙 𝑟

𝐴 𝑇 ⁢ 𝒃 𝑐

𝒙 𝑟

𝑅 𝑇 ⁢ ( 𝑅 ⁢ 𝑅 𝑇 ) − 1 ⁢ 𝑅 ⁢ 𝒙 𝑟

𝑅 + ⁢ 𝐶 + ⁢ 𝒃 𝑐 𝐶 𝑇 ⁢ 𝐶 ⁢ 𝑅 ⁢ 𝒙 𝑟

𝐶 𝑇 ⁢ 𝐴 ⁢ 𝒙 𝑟

𝐶 𝑇 ⁢ 𝒃 𝑐

𝑅 ⁢ 𝒙 𝑟

( 𝐶 𝑇 ⁢ 𝐶 ) − 1 ⁢ 𝐶 𝑇 ⁢ 𝒃 𝑐

𝐶 + ⁢ 𝒃 𝑐 𝑅 + 𝑅 𝐶 𝐶 +
Figure 3:Given a full rank decomposition 𝐴

𝐶 ⁢ 𝑅 , matrix 𝑅 maps C ⁢ ( 𝐴 𝑇 ) into C ⁢ ( 𝐶 𝑇 ) and matrix 𝐶 𝑇 maps C ⁢ ( 𝐴 ) into C ⁢ ( 𝑅 ) when ( 𝐶 ⁢ 𝑅 ) +

𝑅 + ⁢ 𝐶 + .
C ⁢ ( ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + )

𝑅 ⁢ 𝑅 + ⁢ C ⁢ ( 𝐶 𝑇 ) [ 10 ⁢ 𝑝 ⁢ 𝑡 ] ⁢ 𝒙 𝑟 ∈ C ⁢ ( 𝑅 𝑇 ⁢ 𝐶 𝑇 ) C ⁢ ( 𝑅 ) ∩ C ⁢ ( 𝐶 𝑇 ) C ⁢ ( 𝐶 ⁢ 𝑅 ) ∋ 𝒃 𝑐 C ⁢ ( 𝐴 𝑇 )

C ⁢ ( ( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + ) 𝑅 ⁢ 𝒙 𝑟

( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + ⁢ 𝒃 𝑐 𝒙 𝑟

( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ 𝑅 ⁢ 𝒙 𝑟
Figure 4:The pseudoinverse 𝐴 +

( 𝐶 ⁢ 𝑅 ) +

( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + decomposes into the product of the pseudoinverse of 𝑅 projected on the row space of 𝐶 𝑇 and the pseudoinverse of 𝐶 𝑇 projected on the column space of 𝑅 .

In general, the inverse map 𝐴 +

( 𝐶 ⁢ 𝑅 ) + takes 𝒃 𝑐 in the column space C ⁢ ( 𝐶 ) and projects it into 𝑅 ⁢ 𝒙 𝑟 in the part of the column space C ⁢ ( 𝑅 ) intersecting with C ⁢ ( 𝐶 𝑇 ) . That is ensured by ( 𝐶 + ⁢ 𝑅 ⁢ 𝑅 + ) + , since by the first principles

C ⁢ ( ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + )

C ⁢ ( ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) 𝑇 )

𝑅 ⁢ 𝑅 + ⁢ C ⁢ ( 𝐶 𝑇 )

𝑅 ⁢ 𝑅 + ⁢ C ⁢ ( 𝐶 + ) .

Then ( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + maps 𝑅 ⁢ 𝒙 𝑟 into the row space C ⁢ ( 𝑅 𝑇 ⁢ 𝐶 𝑇 ) . We have

C ⁢ ( ( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + )

C ⁢ ( ( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) 𝑇 )

𝑅 𝑇 ⁢ C ⁢ ( 𝐶 + ⁢ 𝐶 )

𝑅 𝑇 ⁢ C ⁢ ( 𝐶 𝑇 )

C ⁢ ( 𝑅 𝑇 ⁢ 𝐶 𝑇 ) .

Therefore, C ⁢ ( 𝑅 𝑇 ⁢ 𝐶 𝑇 )

C ⁢ ( 𝐴 + ) in Figure 4. Also, for any 𝒃 𝑛 in the nullspace of 𝑅 𝑇 ⁢ 𝐶 𝑇 we have 𝑅 ⁢ 𝑅 + ⁢ 𝐶 𝑇 ⁢ 𝒃 𝑛

𝟎 , which shows that 𝒃 𝑛 is in the nullspace

N ⁢ ( 𝑅 ⁢ 𝑅 + ⁢ 𝐶 𝑇 )

N ⁢ ( ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + ) ⊂ N ⁢ ( ( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + )

N ⁢ ( 𝐴 + ) .

Conversely, any 𝒃 𝑛 in the nullspace N ⁢ ( ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + )

𝑅 ⁢ 𝑅 + ⁢ N ⁢ ( 𝐶 𝑇 ) is also in the nullspace of N ⁢ ( 𝐶 𝑇 ) . It is orthogonal to the columns of 𝐶 spanning C ⁢ ( 𝐴 ) . Therefore, it is also in the nullspace N ⁢ ( 𝐴 𝑇 ) . That proves the following formula for 𝐴 + :

Theorem 2.

The pseudoinverse 𝐴 + of a product 𝐴

𝐶 ⁢ 𝑅 is given by the product

𝐴 +

( 𝐶 ⁢ 𝑅 ) +

( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) + .

(6)

The statement in the title of this paper is not generally true. But the statement of Theorem 2 corrects the mistake as the following example shows:

𝐶

[ 1
0
] 𝑅

[ 1

1
] 𝐶 + ⁢ 𝐶

[ 1

0

0
0
] 𝑅 ⁢ 𝑅 +

1 2 ⁢ [ 1

1

1
1
]

( 𝐶 + ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ ( 𝐶 ⁢ 𝑅 ⁢ 𝑅 + ) +

[ 1

0

] ⁢ [ 1

1
]

( 𝐶 ⁢ 𝑅 ) + .

Theorem 3 gives an even more general statement (following from [3]).

Theorem 3.

The pseudoinverse 𝐴 + of a product 𝐴

𝐶 ⁢ 𝑅 is given by the product

𝐴 +

( ( 𝑃 𝑇 ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ 𝑃 𝑇 ⁢ 𝐶 ) ⁢ ( 𝑅 ⁢ 𝑄 ⁢ ( 𝐶 ⁢ 𝑅 ⁢ 𝑄 ) + ) ,

(7)

for any 𝑃 and 𝑄 satisfying

rank ⁢ ( 𝑃 𝑇 ⁢ 𝐴 )

rank ⁢ ( 𝐴 ⁢ 𝑄 )

rank ⁢ ( 𝐴 ) .

(8)

Proof: When rank ⁢ ( 𝑃 𝑇 ⁢ 𝐴 )

rank ⁢ ( 𝐴 ⁢ 𝑄 )

rank ⁢ ( 𝐴 ) for 𝑃 and 𝑄 of proper size, then

C ⁢ ( ( 𝑃 𝑇 ⁢ 𝐴 ) 𝑇 )

C ⁢ ( ( 𝐴 ) 𝑇 ) and C ⁢ ( 𝐴 ⁢ 𝑄 )

C ⁢ ( 𝐴 ) .

In that case, ( 𝑃 𝑇 ⁢ 𝐴 ) + ⁢ ( 𝑃 𝑇 ⁢ 𝐴 )

𝐴 + ⁢ 𝐴 and ( 𝐴 ⁢ 𝑄 ) ⁢ ( 𝐴 ⁢ 𝑄 ) +

𝐴 ⁢ 𝐴 + and (7) is true:

𝐴 +

( 𝑃 𝑇 ⁢ 𝐴 ) + ⁢ 𝑃 𝑇 ⁢ 𝐴 ⁢ 𝑄 ⁢ ( 𝐴 ⁢ 𝑄 ) + .
Figure 5: Computation time and relative approximation error of the randomized 𝐴 𝑟 +

𝚛𝚙𝚒𝚗𝚟 ⁢ ( 𝐴 ) , randomized SVD-based 𝐴 𝑠 +

𝚛𝚜𝚟𝚍𝚒 ⁢ ( 𝐴 ) and direct 𝐴 +

𝚙𝚒𝚗𝚟 ⁢ ( 𝐴 ) method of calculating the pseudoinverse of 𝐴 . In the experiment, we generate a random test matrix 𝐴

𝚐𝚊𝚕𝚕𝚎𝚛𝚢 ( ′ 𝚛𝚊𝚗𝚍𝚜𝚟𝚍 ′ , 𝚗 , 𝟷 𝚎 𝟷𝟶𝟶 ) with 𝑛 ranging from 100 to 1000 . Then, we calculate the approximation 𝐴 𝑟 + taking random 𝑚 by 𝑝 matrix 𝑃 and 𝑛 by 𝑞 matrix 𝑄 (in Theorem 3) with 𝑝

𝑞

⌈ 𝛼 ⋅ 𝑛 ⌉ for 𝛼

0.4 (top) and 𝛼

0.1 (bottom). Randomized SVD-based pseudoinverse is calculated based on rank 𝑠

rank ⁢ ( 𝐴 ) approximation 𝐴 𝑠

𝑄 ⁢ 𝑈 𝑠 ⁢ Σ 𝑠 ⁢ 𝑉 𝑠 𝑇 for [ 𝑄 , ∼ ]

qr ⁢ ( 𝐴 ∗ 𝚛𝚊𝚗𝚍𝚗 ⁢ ( 𝑛 , 𝑠 ) ) .

Matrices 𝑃 and 𝑄 must be rank-preserving to reconstruct 𝐴 + . But apart from that requirement, 𝑃 and 𝑄 can be random matrices. The pseudoinverse of

𝐴

[ 1

4

5

2
3
5 ] ⁢ is equal to ⁢ 𝐴 +

1 15 ⁢ [ − 8

9

7

− 6

− 1

3

] .

Randomly selected matrices

𝑃

[ 2

2

2

1
2
2 ] and 𝑄

[ 1

1

0

2

0

0

]

preserve rank ⁢ ( 𝐴 )

rank ⁢ ( 𝑃 𝑇 ⁢ 𝐴 )

rank ⁢ ( 𝐴 ⁢ 𝑄 )

2 . Therefore,

( 𝑃 𝑇 ⁢ 𝐶 ⁢ 𝑅 ) + ⁢ 𝑃 𝑇 ⁢ 𝐶

1 3 ⁢ [ 2

− 1

− 1

2

1
1
] and 𝑅 ⁢ 𝑄 ⁢ ( 𝐶 ⁢ 𝑅 ⁢ 𝑄 ) +

1 5 ⁢ [ − 3

4

2

− 1

]

reconstruct

𝐴 +

1 3 ⁢ [ 2

− 1

− 1

2

1

1

] ⋅ 1 5 ⁢ [ − 3

4

2
− 1
]

1 15 ⁢ [ − 8

9

7

− 6

− 1

3

] .

Random sampling matrices 𝑃 and 𝑄 that are not rank-preserving produce a low-rank approximation of 𝐴 + from the samples of bases for the column space and row space of 𝐴 . Therefore, the formula in Theorem 3 describes a randomized algorithm approximating 𝐴 + :

function Arplus = rpinv(A,p,q) % rpinv: randomized pseudoinverse of A [m,n] = size(A); P = randn(m,p); Q = randn(n,q); PTA = P’A; AQ = AQ; Arplus = pinv(PTA)PTAQ*pinv(AQ); end

When 𝑃 and 𝑄 are small ( 𝑚 by 𝑝 and 𝑛 by 𝑞 matrices), it is more time-efficient to compute 𝐴 𝑟 + using two pseudoinverses, ( 𝑃 𝑇 ⁢ 𝐴 ) + and ( 𝐴 ⁢ 𝑄 ) + , than to calculate 𝐴 + directly. Also, that approach may lead to smaller relative errors (under the circumstances to be investigated) than the randomized SVD method while maintaining similar time efficiency. Figure 5 demonstrates these points by comparing each method.

We have given three formulas for the pseudoinverse of a matrix product 𝐴

𝐶 ⁢ 𝑅 and derived them from the four fundamental subspaces of 𝐴 . Every matrix 𝐴 gives an invertible map from its row space to its column space. The pseudoinverse 𝐴 + inverts the row space to the column space map when the nullspace of 𝐴 𝑇 and 𝐴 + match. The first formula in Theorem 1 is correct if 𝐶 has independent columns and 𝑅 has independent rows or when Greville’s conditions hold. The second in Theorem 2 is always correct. The third in Theorem 3 is correct when the sampling matrices 𝑃 and 𝑄 preserve rank. Otherwise, it is not correct but potentially very useful, especially for large 𝐴 .

References [1] ↑ Adi Ben-Israel and Thomas N.E. Greville, Generalized Inverses: Theory and Applications.Springer( 2003 ). [2] ↑ Keaton Hamm and Longxiu Huang, Perspectives on CUR Decompositions.Applied and Computational Harmonic Analysis, 𝟒𝟖 ( 2020 ) 1088 – 1099 . [3] ↑ Michał P. Karpowicz, A Theory of Meta-factorization.arXiv : 2111.14385 ( 2021 ). [4] ↑ Roger Penrose, A Generalized Inverse for Matrices.MathematicalProceedings of the Cambridge Philosophical Society, 𝟓𝟏 ( 1955 ) 406 – 413 . [5] ↑ Gilbert Strang and Daniel Drucker, Three Matrix Factorizations from the Steps of Elimination.Analysis and Applications, 𝟐𝟎 ( 2022 ) 1147 – 1157 . [6] ↑ Gilbert Strang, Introduction to Linear Algebra, 𝟔 th edition ( 2023 ),Wellesley-Cambridge Press. [7] ↑ Thomas N.E. Greville, Note on the Generalized Inverse of a Matrix Product,SIAM Review, 𝟖 ( 1966 ) 518 – 521 . [8] ↑ George Marsaglia and George Styan, Equalities and inequalities for ranks of matrices,Linear and Multilinear Algebra, 𝟑 ( 1974 ) 269 – 292 . Report Issue Report Issue for Selection Generated by L A T E xml Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" button. Open a report feedback form via keyboard, use "Ctrl + ?". Make a text selection and click the "Report Issue for Selection" button near your cursor. You can use Alt+Y to toggle on and Alt+Shift+Y to toggle off accessible reporting links at each section.

Our team has already identified the following issues. We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion, and welcome developer contributions.