A generalization of the Moore-Penrose inverse related to matrix subspaces of C(nxm)

A generalization of the Moore-Penrose inverse related to matrix subspaces of Cn×mI Antonio Su´arez, Luis Gonz´alez∗ Department of Mathematics, University of Las Palmas de Gran Canaria, 35017 Las Palmas de Gran Canaria, Spain Abstract A natural generalization of the classical Moore-Penrose inverse is presented. The so-called S-Moore-Penrose inverse of a m×ncomplex matrix A, denoted by A† S, is defined for any linear subspace Sof the matrix vector space Cn×m. The S-Moore-Penrose inverse A† Sis characterized using either the singular value decomposition or (for the nonsingular square case) the orthogonal complements with respect to the Frobenius inner product. These results are applied to the preconditioning of linear systems based on Frobenius norm minimization and to the linearly constrained linear least squares problem. Keywords: Moore-Penrose inverse; Frobenius norm; S-Moore-Penrose inverse; Approximate inverse preconditioning; Constrained least squares problem 1. Introduction Let Cm×n(Rm×n) denote the set of all m×ncomplex (real) matrices. Throughout this paper, the notations AT,A∗,A−1,r(A) and tr (A) stand for the transpose, conjugate transpose, inverse, rank and trace of matrix A, respectively. The general reciprocal was described by E. H. Moore in 1920 [1] and independently rediscovered by R. Penrose in 1955 [2], and it is nowadays called the Moore-Penrose inverse. The Moore-Penrose inverse of a matrix A∈Cm×n(sometimes referred to as the pseudoinverse of A) is the unique IShort running title: A generalization of the Moore-Penrose inverse ∗Corresponding author. Email address: [email protected] (Luis Gonz´alez) Preprint submitted to Applied Mathematics and Computation November 4, 2013 matrix A†∈Cn×msatisfying the four Penrose equations AA†A=A, A†AA†=A†,AA†∗=AA†,A†A∗=A†A. (1.1) For more details on the Moore-Penrose inverse, see [3]. The pseudoinverse has been widely studied during the last decades from both theoretical and computational points of view. Some of the most recent works can be found, e.g., in [4, 5, 6, 7, 8, 9, 10] and in the references contained therein. As is well-known, the Moore-Penrose inverse A†can be alternatively defined as the unique matrix that gives the minimum Frobenius norm among all solutions to any of the matrix minimization problems min M∈Cn×mkMA −InkF,(1.2) min M∈Cn×mkAM −ImkF,(1.3) where Indenotes the identity matrix of order nand k·kFstands for the matrix Frobenius norm. Also, the pseudoinverse of Acan be defined via a limiting process as [11] A†= lim δ→0A∗(AA∗+δIm)−1= lim δ→0(A∗A+δIn)−1A∗ and by the explicit algebraic expression [3] A†=C∗(CC∗)−1(B∗B)−1B∗ based on the full rank factorization A=BC, B ∈Cm×r, C ∈Cr×n, r (A) = r(B) = r(C) = r. In particular, if A∈Cm×nhas full row rank (full column rank, respectively) then A†is simply the unique solution to problem (1.2) (to problem (1.3), respectively), given by the respective explicit expressions [3] A†=(i)A∗(AA∗)−1iff r(A) = m, (ii) (A∗A)−1A∗iff r(A) = n, (1.4) so that A†is a right inverse (left inverse, respectively) of Aif r(A) = m (r(A) = n, respectively). 2 A natural generalization of the Moore-Penrose inverse, the so-called left or right S-Moore-Penrose inverse, arises simply by taking in Equations (1.2) or (1.3), respectively, the minimum over an arbitrary matrix subspace Sof Cn×m, instead of over the whole matrix space Cn×m. This is the starting point of this paper, that has been organized as follows. In Section 2, we define the S-Moore-Penrose inverse and we provide an explicit expression based on the singular value decomposition (SVD) of matrix A, as well as an alternative expression for the nonsingular case, in terms of the orthogonal complements with respect to the Frobenius inner product. Next, in Section 3 we apply these results to the preconditioning of linear systems based on Frobenius norm minimization and to the linear least squares problem subject to some linear restrictions. Finally, in Section 4 we present our conclusions. 2. The S-Moore-Penrose inverse Equations (1.2) and (1.3), regarding the least squares characterization of the Moore-Penrose inverse, can be generalized as follows. Definition 2.1. Let A∈Cm×nand let Sbe a linear subspace of Cn×m. Then (i) The left Moore-Penrose inverse of Awith respect to Sor, for short, the left S-Moore-Penrose inverse of A, denoted by A† S,l, is the minimum Frobenius norm solution to the matrix minimization problem min M∈SkMA −InkF.(2.1) (ii) The right Moore-Penrose inverse of Awith respect to Sor, for short, the right S-Moore-Penrose inverse of A, denoted by A† S,r, is the minimum Frobenius norm solution to the matrix minimization problem min M∈SkAM −ImkF.(2.2) Remark 2.1. Note that for S=Cn×m, the left and right S-Moore-Penrose inverses become the Moore-Penrose inverse. That is, the left and right SMoore-Penrose inverses generalizes the definition, via the matrix minimization problems (1.2) and (1.3), respectively, of the classical pseudoinverse. 3 Moreover, when A∈Cn×nis nonsingular and A−1∈Sthen the left and right S-Moore-Penrose inverses are just the inverse. Briefly: A† Cn×m,l =A†=A† Cn×m,r and A† S,l =A−1=A† S,r for all Ss.t. A−1∈S. Remark 2.2. In particular, if matrix Ahas full row rank, (full column rank, respectively) then it has right inverses, (left inverses, respectively). Thus, due to the uniqueness of the orthogonal projection of the identity matrix In(Im, respectively) onto the matrix subspace SA ⊆Cn×n(AS ⊆Cm×m, respectively), we conclude that, for these special cases, Definition 2.1 simply affirms that A† S,l (A† S,r, respectively) is just the unique solution to problem (2.1) (to problem (2.2), respectively). The following simple example illustrates this fact. Example 2.1. For n=m= 2 and A=1 1 2 0 , S =span 1 0 0 0 =α0 0 0 α∈C , on one hand, we have A† S,lA−I2 2 F= min M∈SkMA −I2k2 F= min α∈C|α−1|2+|α|2+ 1, so that A† S,l =1 20 0 0 ,A† S,lA−I2F=3 2 and on the other hand, we have AA† S,r −I2 2 F= min M∈SkAM −I2k2 F= min α∈C|α−1|2+|2α|2+ 1, so that A† S,r =1 50 0 0 ,AA† S,r −I2F=9 5. Remark 2.3. Example 2.1 illustrates three basic differences between the Moore-Penrose and the S-Moore-Penrose inverses. First, we have that, in general, A† S,l 6=A† S,r. Second, neither A† S,l, nor A† S,r satisfies, in general, none of the Penrose equations (1.1). Finally, although matrix Ahas full rank, neither A† S,l is a left inverse, nor A† S,r is a right inverse of matrix A. 4 Throughout this paper we address only the case of the right S-MoorePenrose inverse A† S,r, but analogous results can be obtained for the left SMoore-Penrose inverse A† S,l. Next theorem provides us with an explicit expression for A† S,r from an SVD of matrix A. Theorem 2.1. Let A∈Cm×nand let Sbe a linear subspace of Cn×m. Let A=UΣV∗be an SVD of matrix A. Then A† S,r =VΣ† V∗SU,rU∗and AA† S,r −ImF=ΣΣ† V∗SU,r −ImF.(2.3) Moreover, A†−A† S,rF=Σ†−Σ† V∗SU,rF.(2.4) Proof. For all M∈S, we have N=V∗MU ∈V∗SU and M=V NU∗. Using the invariance property of the Frobenius norm under multiplication by unitary matrices, we get Af M−ImF= min M∈SkAM −ImkF= min N∈V∗SU kUΣV∗V NU∗−ImkF = min N∈V∗SU kU(ΣN−Im)U∗kF= min N∈V∗SU kΣN−ImkF =Σe N−ImF,(2.5) that is, e N∈V∗SU is a solution to the matrix minimization problem min N∈V∗SU kΣN−ImkF(2.6) if and only if f M=Ve NU∗∈Sis a solution to problem (2.2). Now, let e Nbe any solution to problem (2.6). Since Σ† V∗SU,r is the minimum Frobenius norm solution to problem (2.6), we have Σ† V∗SU,rF≤e NF and then, using again the fact that the Frobenius norm is unitarily invariant, we have VΣ† V∗SU,rU∗F≤Ve NU∗Ffor any solution e Nto problem (2.6),i.e., 5 VΣ† V∗SU,rU∗F≤f MFfor any solution f Mto problem (2.2). This proves that the minimum Frobenius norm solution A† S,r to problem (2.2) is VΣ† V∗SU,rU∗, and the right-hand equality of Equation (2.3) immediately follows from Equation (2.5). Finally, Equation (2.4) immediately follows using the well-known expression A†=VΣ†U∗and the left-hand equality of Equation (2.3), that is, A†−A† S,rF=VΣ†U∗−VΣ† V∗SU,rU∗F=Σ†−Σ† V∗SU,rF. Remark 2.4. Formula (2.3) for the right S-Moore-Penrose inverse generalizes the usual expression for the Moore-Penrose inverse in terms of an SVD of A, since (see Remark 2.1) S=Cn×m⇒V∗SU =Cn×m⇒A†=A† S,r =VΣ† V∗SU,rU∗=VΣ†U∗. For nonsingular square matrices, the next theorem provides an expression for A† S,r involving the orthogonal complement of subspace S(denoted, as usual, by S⊥) with respect to the Frobenius inner product h· ,·iF. This expression generalizes Equation (1.4)-(ii). Theorem 2.2. Let A∈Cn×nwith r(A) = nand let Sbe a linear subspace of Cn×n. Then A† S,r = (A∗A)−1(A∗+Q),for some Q∈S⊥.(2.7) Proof. Since AA† S,r is the orthogonal projection of the identity matrix onto the subspace AS, we have AA† S,r −In∈(AS)⊥.(2.8) Now, for all M∈Sand for all N∈S⊥we have AM, A−1∗NF=tr AMN∗A−1=tr A−1AMN∗=hM, NiF= 0 and this proves the inclusion (A−1)∗S⊥⊆(AS)⊥. Moreover, since Aand (A−1)∗are nonsingular, we have dim (AS)⊥=n2−dim (AS) = n2−dim (S) = dim S⊥= dim A−1∗S⊥ 6 and this proves the set equality (AS)⊥=A−1∗S⊥.(2.9) Finally, using Equations (2.8) and (2.9), we get AA† S,r −In=A−1∗Q, for some Q∈S⊥,i.e., A† S,r = (A∗A)−1(A∗+Q),for some Q∈S⊥. An example where Theorem 2.2 can be applied is given in the next corollary. Corollary 2.1. Let A∈Cn×nwith r(A) = n. Let s∈Cn− {0}and let [0/s]be the annihilator subspace of sin Cn×n, i.e., [0/s] = M∈Cn×n|Ms = 0}. Then A† [0/s],r =A−1In− ksk−2 2ss∗,(2.10) where k·k2stands for the usual vector Euclidean norm. Proof. Using Equation (2.7) for S= [0/s], we have A† [0/s],r = (A∗A)−1(A∗+Q),for some Q∈[0/s]⊥ and since the orthogonal complement of the annihilator subspace [0/s] is given by [12] [0/s]⊥={vs∗|v∈Cn}, we get A† [0/s],r = (A∗A)−1(A∗+vs∗),for some v∈Cn.(2.11) Multiplying both sides of Equation (2.11) by vector s, we get A† [0/s],rs= (A∗A)−1(A∗+vs∗)s and, since A† [0/s],r ∈[0/s], we get 0 = (A∗+vs∗)s⇒v=−1 ksk2 2 A∗s and substituting vby its above expression in Equation (2.11), we get A† [0/s],r = (A∗A)−1 A∗−1 ksk2 2 A∗ss∗!=A−1In− ksk−2 2ss∗. 7 Remark 2.5. Writing Equation (2.10) as A† [0/s],r =A†In−ss∗ s∗s, we have a representation of the left S-Moore-Penrose inverse of A(Sbeing the annihilator subspace [0/s] of s) as the product of the Moore-Penrose inverse of Aand the elementary annihilator In−ss∗ s∗sof vector s. Regarding the full column rank case (A∈Cm×n, r (A) = n), let us mention that, in addition to formulas (2.3) and (2.7), other explicit expressions for A† S,r -more appropriate for computational purposescan be given using an arbitrary basis of subspace S. The basic idea simply consists of expressing the orthogonal projection AA† S,r of Imonto the subspace AS by its expansion with respect to an orthonormal basis of AS (after using the Gram-Schmidt orthonormalization procedure, if necessary). These expressions have been developed in [13] for the special case of real n×nnonsingular matrices, and they have been applied to the preconditioning of large linear systems and illustrated with some numerical experiments corresponding to real-world cases. The next two lemmas state some spectral properties of the matrix product AA† S,r that will be used in the next section. Lemma 2.1. Let A∈Cm×nand let Sbe a linear subspace of Cn×m. Then AA† S,r −Im 2 F=m−tr AA† S,r,(2.12) AA† S,r 2 F=tr AA† S,r.(2.13) Proof. Using the fact that AA† S,r is the orthogonal projection of the identity onto the matrix subspace AS, we have DAA† S,r −Im, AMEF= 0,for all M∈S and, in particular, for M=A† S,r we have DAA† S,r −Im, AA† S,rEF= 0 8 and then we get, on one hand, AA† S,r −Im 2 F=DAA† S,r −Im, AA† S,rEF+DIm−AA† S,r, ImEF =m−tr AA† S,r and, on the other hand, AA† S,r 2 F=DAA† S,r, AA† S,rEF=DAA† S,r, ImEF=tr AA† S,r. Lemma 2.2. Let A∈Cm×nand let Sbe a linear subspace of Cn×m. Let {λi}m i=1 and {σi}m i=1 be the sets of eigenvalues and singular values, respectively, of matrix AA† S,r arranged, as usual, in nonincreasing order of their modules. Then m X i=1 σ2 i= m X i=1 λi≤m. (2.14) Proof. Taking into account that AA† S,r 2 F=tr AA† S,r AA† S,r∗= m X i=1 σ2 i, tr AA† S,r= m X i=1 λi and using Equations (2.12) and (2.13), the proof is concluded.  3. Applications 3.1. Applications to preconditioning In numerical linear algebra, the convergence of the iterative Krylov methods [14, 15, 16] used for solving the linear system Ax =b, A ∈Rn×n, A nonsingular, x, b ∈Rn×1(3.1) can be improved by transforming it into the right preconditioned system AMy =b, x =My. (3.2) The approximate inverse preconditioning (3.2) of system (3.1) is performed in order to get a preconditioned matrix AM as close as possible to 9 4. Concluding remarks The left and right S-Moore-Penrose inverses, A† S,l and A† S,r, extend the idea of the standard inverse from nonsingular square matrices not only to rectangular and singular square matrices (as the Moore-Penrose inverse does), but also to invertible matrices, themselves, by considering a subspace Sof Cn×mnot containing A−1. Restricted to the right case, we have expressed A† S,r using either an SVD of Aor (for the nonsingular case) the orthogonal complements with respect to the Frobenius inner product. A† S,r can be seen as an useful alternative to A†: It provides us with a computationally feasible approximate inverse preconditioner for large linear systems (in contrast to the unfeasible computation of A†=A−1), and it also provides the minimum norm solution A† SP,rbto the least squares problem subject to homogeneous linear constraints (in contrast to the minimum norm solution A†bto the unconstrained least squares problem). The behavior of the S-Moore-Penrose inverse with respect to both theoretical results and other applications, already known for the Moore-Penrose inverse, can be considered for future researches. Acknowledgment. This work was partially supported by Ministerio de Ciencia e Innovaci´on (Spain) and FEDER through Grant contract: CGL200806003-C03-01/CLI. References [1] E. H. Moore, On the reciprocal of the general algebraic matrix. Bull. Amer. Math. Soc. 26:394-395 (1920). [2] R. Penrose, A generalized inverse for matrices. Proc. Cambridge Philos. Soc. 51:406-413 (1955). [3] A. Ben-Israel, T. N. E. Greville, Generalized Inverses: Theory and Applications, 2nd. Ed. Springer-Verlag, NewYork, 2003. [4] J. K. Baksalary, O. M. Baksalary, Particular formulae for the MoorePenrose inverse of a columnwise partitioned matrix. Linear Algebra Appl. 421:16-23 (2007). 16 [5] T. Britz, D. D. Olesky, P. van den Driessche, The Moore-Penrose inverse of matrices with an acyclic bipartite graph. Linear Algebra Appl. 390:4760 (2004). [6] M. A. Rakha, On the Moore-Penrose generalized inverse matrix. Appl. Math. Comput. 158:185-200 (2004). [7] Y. Tian, Using rank formulas to characterize equalities for MoorePenrose inverses of matrix products. Appl. Math. Comput. 147:581-600 (2004). [8] Y. Tian, Approximation and continuity of Moore-Penrose inverses of orthogonal row block matrices. Appl. Math. Comput. (2008), doi: 10.1016/j.amc.2008.10.027, to appear. [9] F. Toutounian, A. Ataei, A new method for computing MoorePenrose inverse matrices. J. Comput. Appl. Math. (2008), doi: 10.1016/j.cam.2008.10.008, to appear. [10] X. Zhang, J. Cai, Y. Wei, Interval iterative methods for computing Moore-Penrose inverse. Appl. Math. Comput. 183:522-532 (2006). [11] G. H. Golub, C. F. Van Loan, Matrix Computations, 3rd Ed. Johns Hopkins Press, Baltimore, USA, 1996. [12] A. Griewank, A short proof of the Dennis-Schnabel theorem. BIT 22:252-256 (1982). [13] G. Montero, L. Gonz´alez, E. Fl´orez, M. D. Garc´ıa, A. Su´arez, Approximate inverse computation using Frobenius inner product. Numer. Linear Algebra Appl. 9:239-247 (2002). [14] O. Axelsson, Iterative Solution Methods. Cambridge University Press, Cambridge, MA, 1994. [15] A. Greenbaum, Iterative Methods for Solving Linear Systems. Frontiers Appl. Math., SIAM, Vol. 17, Philadelphia, PA, 1997. [16] Y. Saad, Iterative Methods for Sparse Linear Systems. PWS Publishing Co., Boston, MA, 1996. 17 [17] R. A. Horn, C.R. Johnson, Matrix Analysis. Cambridge University Press, Cambridge, MA, 1985. [18] L. Gonz´alez, Orthogonal projections of the identity: Spectral analysis and applications to approximate inverse preconditioning. SIAM Rev. 48:66-75 (2006). [19] R. Penrose, On best approximate solutions of linear matrix equations. Proc. Cambridge Philos. Soc. 52:17-19 (1956). [20] A. Ben-Israel, The Moore of the Moore-Penrose inverse. Electron. J. Linear Algebra 9:150-157 (2002). 18