Normalized Frobenius condition number of the orthogonal projections of the identity

Normalized Frobenius condition number of the orthogonal projections of the identity ✩ Antonio Su´arez, Luis Gonz´alez∗ Department of Mathematics, University of Las Palmas de Gran Canaria, 35017 Las Palmas de Gran Canaria, Spain Abstract This paper deals with the orthogonal projection (in the Frobenius sense) AN of the identity matrix Ionto the matrix subspace AS (A∈Rn×n,Sbeing an arbitrary subspace of Rn×n). Lower and upper bounds on the normalized Frobenius condition number of matrix AN are given. Furthermore, for every matrix subspace S⊂Rn×n, a new index bκF(A, S), which generalizes the normalized Frobenius condition number of matrix A, is defined and analyzed. Keywords: Frobenius norm minimization; Orthogonal projections; Frobenius condition number 2000 MSC: 15A60, 15A12, 15A45 1. Introduction Throughout this paper, ATand tr (A) denote, as usual, the transpose and the trace of matrix A∈Rn×n, while Idenotes the identity matrix of order n. Let h·,·iFand k·kFdenote the Frobenius inner product and matrix norm, defined on the matrix space Rn×n. In the following, the terms orthogonality, angle and cosine will be used in the sense of the Frobenius inner product. The symbols κF(·) and bκF(·) stand for the classical and for the normalized Frobenius condition numbers, respectively, i.e., for every nonsingular n×n real matrix M κF(M) = kMkF M−1 F,bκF(M) = 1 nkMkF M−1 F. ✩Short running title: Normalized Frobenius condition number ∗Corresponding author. Email address: [email protected] (Luis Gonz´alez) Preprint submitted to Journal of Mathematical Analysis and ApplicationsOctober 16, 2012 *Manuscript Let us recall that the solution of the linear system Ax =b, A ∈Rn×n, x, b ∈Rn(Anonsingular and sparse) (1.1) is usually performed by iterative methods based on Krylov subspaces (see, e.g., [1, 2]). To improve the convergence of these Krylov methods, system (1.1) can be preconditioned with an adequate preconditioning nonsingular matrix N, transforming it into any of the equivalent systems [3] NAx =Nb, ANy =b, x =Ny, the so-called left and right preconditioned systems, respectively. In this paper, we address only the case of the right-hand side preconditioned matrices AN (analogous results can be obtained for the left-hand side preconditioned matrices NA). Often, the preconditioning of system (1.1) is performed in order to get a preconditioned matrix AN as close as possible to the identity in some sense. The preconditioner Nis called an approximate inverse of A. The closeness of AN to Imay be measured by using a suitable matrix norm like, for instance, the Frobenius norm [3]. In this way, the best preconditioner N(with respect to the Frobenius norm) of system (1.1) in an arbitrary subspace Sof Rn×ncan be obtained by minimizing the residual Frobenius norm kAM −IkFover the subspace S. That is, the best preconditioner Nof system (1.1) in subspace Sis the solution to the minimization problem; see, e.g., [4] min M∈SkAM −IkF=kAN −IkF.(1.2) Although some of the results presented in this paper are also valid for the case that the solution Nto problem (1.2) is singular, from now on, we assume that matrix N(and thus also matrix AN) is a nonsingular matrix. Taking advantage of the Frobenius inner product in Rn×n, the matrix AN defined by Eq. (1.2) can be obtained as the orthogonal projection of the identity onto the subspace AS. The solution Nto problem (1.2) will be referred to as the “optimal” preconditioner of system (1.1) (or as the “best” approximate inverse of matrix A) in the subspace S. In the following, the preconditioning of a linear system with the optimal preconditioner Ndefined by problem (1.2)), will be referred to as the “optimal preconditioning” of 2 system (1.1) in subspace S. In [5], the solution Nto problem (1.2) is called the S-Moore-Penrose inverse of matrix A, and it is theoretically analyzed as a natural generalization of the classical Moore-Penrose inverse. We must highlight here that the purpose of this paper is purely theoretical, and the relation between problem (1.2) and the preconditioning problem is also analyzed here from a theoretical point of view, and not looking for numerical or computational immediate approaches. In particular, the terms “optimal preconditioner” or ‘best approximate inverse” are used in the sense of formula (1.2), and not in any other sense of these expressions. Regarding the above mentioned connection between the Frobenius norm and the art of preconditioning, in [6] the authors consider the following equality kAQ −Ik2 F=√n−kAQkF2+ 2√nkAQkF(1 −cos (AQ, I)) to present an interesting geometrical analysis of the practical difficulties for building accurate approximate inverses Qwith a prescribed sparsity pattern. Moreover, in [6, 7, 8], some geometrical properties and bounds on the Frobenius condition number for positive definite matrices are derived. In this paper we address the analysis of the normalized Frobenius condition number to a different case, namely for the orthogonal projections AN of the identity onto the matrix subspaces AS. The following are the main goals and the organization of this paper. First, in Section 2, we provide some inequalities for the normalized Frobenius condition number bκF(AN) of matrix AN. Second, in Section 3, a new index bκF(A, S) is introduced as a natural generalization of the normalized Frobenius condition number bκF(A) of matrix A. The new index bκF(A, S) (referred to as the S-normalized Frobenius condition number of A) is closely related to the optimal preconditioner Nin the subspace S, and it is compared with kAN −IkF. Finally, some concluding remarks are given in Section 4. 2. Normalized Frobenius condition number of matrix AN In this section, we present some upper and lower bounds on the normalized Frobenius condition number bκF(AN) of the orthogonal projection AN defined by Eq. (1.2). The fact that the Frobenius condition number of the n×nidentity matrix Iis κF(I) = n, implies that, with respect to this condition number, the 3 identity matrix becomes more and more ill-conditioned as nincreases (i.e., κF(I)→ ∞ as n→ ∞). This makes the classical Frobenius condition number κF(·) inadequate as a measure of the conditioning of a linear system of equations [9]. For this reason, instead of using the classical Frobenius condition number κF(·), throughout this paper we use a more meaningful measure, based on the normalized Frobenius norm 1 √nkMkF=r1 ntr (MMT), and henceforth referred to as the normalized Frobenius condition number. This normalized measure of conditioning is denoted by bκF(·), and defined for all nonsingular n×nreal matrix Mas bκF(M) = 1 nkMkF M−1 F=1 nκF(M).(2.1) Now, from Eq. (2.1) it is obvious that bκF(I) = 1, and also that bκF(M) = 1 nkMkF M−1 F≥1 n MM−1 F=1 nkIkF=√n n, i.e., for all nonsingular matrix M∈Rn×n, we have bκF(M)≥√n n.(2.2) The following lemma provides us with lower and upper bounds on the normalized Frobenius condition number bκF(AN) of the orthogonal projection AN, involving its largest and its smallest singular value. From now on, we denote by {σi}n i=1 the set of singular values of matrix AN arranged, as usual, in nonincreasing order, i.e., σ1≥σ2≥...≥σn>0. Lemma 2.1. Let A∈Rn×nbe nonsingular and let Sbe a linear subspace of Rn×n. Let Nbe the solution to problem (1.2). Then σ1 n≤σ1 nσn≤bκF(AN)≤σ1 σn <√n σn . 4 Proof. Denote by k·k2and by κ2(·) the spectral matrix norm and the spectral condition number, respectively. Using the well-known relations between the spectral and the Frobenius matrix norms [10] k·k2≤ k·kF≤√nk·k2, we get 1 nκ2(AN)≤bκF(AN)≤κ2(AN), i.e., σ1 nσn≤bκF(AN)≤σ1 σn . Now, on one hand, taking into account the following property of the orthogonal projection AN; see, e.g., [4, 11] 0≤ kANk2 F=tr(AN)≤n, (2.3) we get σ2 1< n X i=1 σ2 i=kANk2 F≤n⇒σ1<√n. On the other hand, we use the following fact derived in [11]: The smallest singular value of the orthogonal projection AN of the identity onto the subspace AS is never greater than 1, i.e., 0< σn≤1. Hence, we get σ1 n≤σ1 nσn≤bκF(AN)≤σ1 σn <√n σn . The following lemma provides lower and upper bounds on the normalized Frobenius condition number bκF(AN) of the orthogonal projection AN, involving the Frobenius norms of both matrix AN and its inverse. Lemma 2.2. Let A∈Rn×nbe nonsingular and let Sbe a linear subspace of Rn×n. Let Nbe the solution to problem (1.2). Then 1 nkANkF≤bκF(AN)≤√n n (AN)−1 F. 5 Proof. To prove the left-hand inequality, it suffices to use Eqs. (2.2) and (2.3) bκF(AN)≥√n n≥kANkF n. To prove the right-hand inequality, we use again Eq. (2.3) bκF(AN) = 1 nkANkF (AN)−1 F≤√n n (AN)−1 F. Remark 2.1. By the way, from the right-hand side inequality in Lemma 2.2 and from Eq. (2.2) we derive the following relationship between the Frobenius norms of the inverses of matrices Aand its best approximate inverse N.  A−1 F N−1 F≥ (AN)−1 F≥√nbκF(AN)≥1⇒ A−1 F N−1 F≥1. 3. The index b κF(A, S) In this section, a new index bκF(A, S), closely related to the optimal preconditioning in the subspace S, is defined and compared with the normalized Frobenius condition number of matrix A. For this purpose, our starting point is the following upper bound on the cosine of the angle between the orthogonal projection AN and the identity; see [6, 12] and Eq. (2.3) cos (AN, I) = hAN, IiF kANkFkIkF =tr (AN) kANkF√n=ptr (AN) √n =kANkF √n≤kAkFkNkF √n= 1 nkAkFkNkF √n/n .(3.1) This suggests the following definition. Definition 3.1. Let A∈Rn×nbe nonsingular and let Sbe a linear subspace of Rn×n. Let Nbe solution to problem (1.2). Then the S-normalized Frobenius condition number of matrix Ais defined by bκF(A, S) = 1 nkAkFkNkF. 6 The S-normalized Frobenius condition number bκF(A, S) of matrix A, can be seen as the optimal (right)approximate normalized Frobenius condition number of matrix Ain S, since matrix Nis the optimal (right) approximate inverse of matrix Ain subspace S. Obviously, the S-normalized Frobenius condition number of matrix A generalizes its normalized Frobenius condition number, that is (see Eq. (2.1)), S∋A−1⇒N=A−1⇒bκF(A, S) = 1 nkAkFkNkF =1 nkAkF A−1 F=bκF(A), e.g., bκFA, Rn×n=bκFA, span A−1=bκF(A). Remark 3.1. Note that Definition 3.1 can be extended to any complex matrix A∈Cm×n, by considering a subspace S⊂Cn×mand, in fact, obtaining right and left S-normalized Frobenius condition numbers, respectively associated to the solutions Nand N′of the minimization problems min M∈SkAM −ImkF=kAN −ImkF,min M∈SkMA −InkF=kN′A−InkF. However, as already mentioned, in this paper we restrict our study (and thus Definition 3.1) to the case of the (right) minimization problem (1.2), associated to the right preconditioning matrix Nof a linear system Ax =b (A∈Rn×n,Anonsingular). 3.1. Lower bounds on bκF(A, S) The following theorem provides different lower bounds on bκF(A, S). Theorem 3.1. Let A∈Rn×nbe nonsingular and let Sbe a linear subspace of Rn×n. Let Nbe the solution to problem (1.2). Then (i)1 n|hA, NiF| ≤ bκF(A, S). (ii)√n ncos (AN, I) = √tr(AN) n=kANkF n≤bκF(A, S). (iii)tr(AN ) n√n≤bκF(A, S). (iv)2 n2tr (A)tr (N)−1 n|hA, NiF| ≤ bκF(A, S). 7 (v)tr(A)tr(N) n2≤bκF(A, S). (vi)1 kA−1kFkN−1kF≤bκF(A, S). Proof. (i) It suffices to use the Cauchy-Schwarz inequality. (ii) Using Eq. (3.1), the proof is straightforward. (iii) It suffices to use Eq. (3.1) 1≥cos (AN, I) = tr (AN) kANkF√n≥tr (AN) kAkFkNkF√n=tr (AN) bκF(A, S)n√n. (iv) Using the well-known Buzano’s inequality (an extension of the CauchySchwarz inequality in an inner product space) |ha, xi·hx, bi| ≤ 1 2(kakkbk+|ha, bi|)kxk2 for the Frobenius inner product and for a=A, x =I, b =N, we get tr (A)tr (N) = hA, IiF·hN, IiF≤ |hA, IiF·hI, NiF| ≤1 2(kAkFkNkF+|hA, NiF|)kIk2 F =n 2(kAkFkNkF+|hA, NiF|) =n2 2bκF(A, S) + 1 n|hA, NiF|. (v) Using (iv) and (i), we get bκF(A, S)≥2 n2tr (A)tr (N)−1 n|hA, NiF| ≥ 2 n2tr (A)tr (N)−bκF(A, S) ⇒bκF(A, S)≥tr (A)tr (N) n2. (vi) Using Eq. (2.2), we get bκF(A, S) A−1 F N−1 F=1 nkAkFkNkF A−1 F N−1 F =n1 nkAkF A−1 F1 nkNkF N−1 F =nbκF(A)bκF(N)≥n√n n √n n= 1. 8 The following two corollaries give lower bounds on bκF(A, S) for special cases of matrices Aand N. Corollary 3.1. Let A∈Rn×nbe nonsingular and let Sbe a linear subspace of Rn×n. Let Nbe the solution to problem (1.2). Suppose that matrix Aor matrix N(or both)are symmetric. Then (i)kANk2 F n=tr(AN ) n≤bκF(A, S). (ii)2 n2tr (A)tr (N)−1≤bκF(A, S). Proof. (i) Using Theorem 3.1-(i) and Eq. (2.3), we get bκF(A, S)≥1 n|hA, NiF|=1 ntr ATN=1 ntr ANT =1 n|tr (AN)|=1 ntr (AN) = 1 nkANk2 F. (ii) Using Theorem 3.1-(iv) and Eq. (2.3), we get bκF(A, S)≥2 n2tr (A)tr (N)−1 n|hA, NiF|=2 n2tr (A)tr (N)−1 ntr ATN =2 n2tr (A)tr (N)−1 ntr ANT=2 n2tr (A)tr (N)−1 n|tr (AN)| =2 n2tr (A)tr (N)−1 ntr (AN)≥2 n2tr (A)tr (N)−1. Corollary 3.2. Let A∈Rn×nbe nonsingular and let Sbe a linear subspace of Rn×n. Let Nbe the solution to problem (1.2). Suppose that matrix AN is symmetric and positive definite. Then 1 n≤bκF(A, S). Proof. The proof is straightforward using Theorem 3.1-(ii) and the fact that since the orthogonal projection AN is symmetric and positive definite then cos (AN, I)≥1 √n; see [12].  9