Projections in a Normed Linear Space and a Generalization of the Pseudo-Inverse Citation Erdelsky, Philip John (1969) Projections in a Normed Linear Space and a Generalization of the Pseudo-Inverse. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/8GD7-M707. https://resolver.caltech.edu/CaltechTHESIS:02122014-075908297 Abstract The concept of a "projection function" in a finite-dimensional real or complex normed linear space H (the function P M which carries every element into the closest element of a given subspace M) is set forth and examined. If dim M = dim H - 1, then P M is linear. If P N is linear for all k-dimensional subspaces N, where 1 ≤ k < dim M, then P M is linear. The projective bound Q, defined to be the supremum of the operator norm of P M for all subspaces, is in the range 1 ≤ Q < 2, and these limits are the best possible. For norms with Q = 1, P M is always linear, and a characterization of those norms is given. If H also has an inner product (defined independently of the norm), so that a dual norm can be defined, then when P M is linear its adjoint P M H is the projection on (kernel P M ) ⊥ by the dual norm. The projective bounds of a norm and its dual are equal. The notion of a pseudo-inverse F + of a linear transformation F is extended to non-Euclidean norms. The distance from F to the set of linear transformations G of lower rank (in the sense of the operator norm ∥F - G∥) is c/∥F + ∥, where c = 1 if the range of F fills its space, and 1 ≤ c < Q otherwise. The norms on both domain and range spaces have Q = 1 if and only if (F + ) + = F for every F. This condition is also sufficient to prove that we have (F + ) H = (F H ) + , where the latter pseudo-inverse is taken using dual norms. In all results, the real and complex cases are handled in a completely parallel fashion. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) ; Pseudo-Inverse, Approximation Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Todd, John Thesis Committee: Bohnenblust, Henri Frederic (chair) Apostol, Tom M. Ryser, Herbert J. Todd, John Defense Date: 1 January 1969 Funders: Funding Agency Grant Number NSF Graduate Research Fellowship UNSPECIFIED Record Number: CaltechTHESIS:02122014-075908297 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:02122014-075908297 DOI: 10.7907/8GD7-M707 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 8069 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 12 Feb 2014 17:10 Last Modified: 26 Apr 2024 23:13 Thesis Files Preview PDF - Final Version See Usage Policy. 5MB Repository Staff Only: item control page

PROJECTIONS IN A NORMED LINEAR SPACE AND A GENE..B.ALIZATION OF THE PSEUDO-INVERSE Thesis by Philip John Erdelsky In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1969 ii , ACKNOWLEDGEMENT The work leading to this thesis vms carried out under n National Science Founda tion Graduato Fellowship. iii ABSTRACT The concept of a ''projection function" in a finite-dimensional real or comple::r norrned line.ar space H (the function PM 1rhich carries every element int o the closest eleruen·t of a given subspace M} is set forth and examined. If dim M == dim R - 1, then PM is li near • . If PN i s linear for all k-dimensional subspaces N, where 1 ~ k < dim M, then PM is linear. The projective bound Q, defined to be the supremum of the operator norm of PM fo r all sub!:lpaces, is in the r ange 1 ~ Q < 2, and these limits are the best possible. Q = 1, For norms with PM is always linear, and a characterization of those norms is given. If H also has an inner product (defined independent ly of the norm), so that a dual norm can be defined, then when P is li.near H L 11 its adjoint PM is the p r ojection on (kernel PM) by the dual norm. The projective boun ds of a norm and its dual are equal. The notion of a p seudo-inverse F+ of a linea r transformation F is extended to non-Euclidean norms. The distance from F to the set of linear transf ormati ons G of lower rank (in the sense of the operator norm IIF - G II ) is fi Us its space, and c /!IF+ II, 1 ~ c ~ Q where c., 1 if the range of F otherwise. The norms on both domain and range spaces have Q~ 1 if and only if every F. (F+)+ z F for This condition is also sufficient to prove that we have (F +)H = (FH)+, where the. 1atter p seudo-inverse is taken using dual norms. In all results, the real and comp lex cases are handle d in a. completely parallel f ashion. iv CONTENTS PAGE CHA.PI'ER TITLE I Preliminary Definitions and Results • • • • • • 1 II Definition of the Projection Function ••••• 5 III Basic Properties of the Projection Function IV Linearity of the Projection Functioll V The Projective Bound VI Projective Norms VII VIII 7 ..... 9 • • • • • • • • • • • • • 11 • • • • • • • • • • • • • • • 14 . . . . . . . . . . . 18 The Generalized Reciprocal . . . . . . . . . . 23 Dual Norms and Projection References ..... • • • • • • • • • • • 31 1 CHAPTER I PRELIMINARY DEFINITIONS AND RESULTS Let H be an n-dimensiono.l real or complex Hilbert space, lrhere n n is a. positive integer. The elements x,y of H may be thought of n as column vectors, and the inner product (x,y) may be thought of as Ei: For the fundamental properties of H , see any 1 n standard text (e. g., Ha.lmos). The real and complex cases will be hand led in a completely parallel fashion, although most treatments of this subject handle the real case only, or handle the two cases separately. The term "scalar" will therefo re be used to denote either a. real or a. complex number. A function F : H -.> H , m n where H m and II n have the same scalar field, is called homogeneous if it is continuous and for every x E H and every scalar c. m called linear if F( c:x: ) = c F(x) The homogeneous function F is F(x+y) = F(x)+F(y) fo·r all x,yEH. . m A real-valued function IX. on H is called a. norm if n cx.(x) > 0, cx(cx) = lciiX.(x) x, y f: H and every s ca. lar c. m and <X(x+ y) ~ O<(x) + e<.(y) x/: 0 ~ for all We shall need the follo,ring concepts from convexity theory {see also Householder pp. 38-45). A set of the form B == { x £: Hn l O<(x) ~ c} , where ex is a norm and c is a. positive constant, is called an equilibrated convex body. Since ~(x) inf { b 1 b > o, B and c determine ~ uniquely. It is sometimes convenient, especially 2 in illustrations, to use an equilibrated convex body to a norm (see Fig. 1). A k-dl.mensional ~ (sometimes called a linear manifold) in Hn is a subset of the form the set (that is, u+M {u+xlxE:MJ ), where M is a k-dimensional subspace of li • n u' E u + M, then clearly If u + M= u' + M. An (n- 1)- dimensional flat is called Fig. I. An equilibrated convex body B and e. support hyperplane at u in real H • 2 a. h:ype rp lane. .For v / o, a. set of the fo rm ixE:Hn \ (v,x)= 1) is the hyperplane [v/(v,v)] + {v}l., Conversely, if the hyperplane u + M does not contain not contain 0. the point 0, then it is equal to the set u = ul + u2, which do es u 1 E. M~ u 2 EM and ~ X EHn \ (v, x )= 1} v ::: u /(u ,u }. 2 2 2 ' where A hyperp hme u + M such that ex( u) =- c and cx(x) :} c for all x f u + M is called a. support hyperpl a ne for B at u, where B is the equi librated convex body described previously. l.et Theorem 1. 1 convex body. cx(x) ~ O<(u) B = {x E:-Hn \ O<(x} ~ O<(u)} Let u+N be a. flat of dimens ion for every X~ u + N. plane u+ M for B at u such that Proof. (See Fig. 1.) If H n be an equilibrated ~n-1 such tha t Then there exists a support hyperu+ N c u+M. is a. real Hilbert space, convexity theory will supply the proof (for exa mple, see Eggleston ·p. 19). If H n is complex, then Hn with the new inner product ne(x,y) is a 2n-dimensional re a l Hilbert space,~ is still a norm, and u + N is a flat of dimension ~ 2n-l. Hence there is a support hyper- plane u + M' for B at u in this ne1r space such that Moreover, we can write u + N c: u + M'. 3 u + M' c:: { X t Hn \ Re ( V, X) = 1l for some v~H. n Since Re(v,u) = 1, Then (v,u')= 1 (v,u} /. 0 and we can define u' = u/ (v,u). and hence u' is on the support hyperplane u+Y'. Therefore ~ et.(u) I( v, u) \ ~ 1. which i mp lies tho.t tho.t C)((u') l(v,u)\ Since Re( v, u) = 1, this imp lies ( v' u) = 1. Therefore, consider the set Hilbert space. u+M. t~~.( u) "" Since ( v, u) = 1, { :x: f Hn I (v, x) = 1 J in the original this set c e.n be represented as It is a support hyperplane forB at u because xfu+M => X t U + U 1 ::) ()( (X) ~ ()( ( U) • Now let :x: be an arbitrary element of u + N. hence Re( v, x) = 1. We can express x as + x' X= u x E: u + M1 and Then ·'IYhere x' EN. Then 1 and hence Re(v,x' )= 0 Im(v,x')"" 0 ( v, x') = 1 Re(v,x) = Re(v,u) + Re(v,x') for all x' f N. also, and and = x € u + M. ( v, x 1 ) = 0. Therefore Consequently 1 + Re(v,x'), Re(v,-ix') = ( v, x) = (v, u) + u + N c. u + M, This shows that 1rhich com- pletes the proof. For the special cas e dim N = O, we have the follo~~ng im- portant result. Corollary 1.2 An equilibrated convex body has at least one support hyperplane at each boundary point. The norm of a homo geneous function m ~ Hn F' H norm ~ on Hn and the norm ~ on Hm is defined by induced by the = O«.(F(x)) s'}.~o_ X1'1 (!.( :X ) ... sup O<(F(x) ). p(x)=l The supremum is actua lly attained for some nonzero x, since the set \x E: Hm \ ~(x) r: 1! · is compact. If that is, F: H -+ H m n is linear, FH will represent the adjoint of F, H (F(x), y) = (x,F (y)) for all. x E Hm' y €: Hn. 5 CHAPTER II DEFINITION OF THE PROJECTION FUNCTION A norm ex: on H is c a lled strictly conve x if n ~ · oc(x) e<(cx+ (1-c )y) for all scalars c implies that x= y. convex body B == [ x \ e<(x) ~ 1} , 0< = C<(y) In terms of the equilibrated is strictly convex if every one- dimens iona l flat whi ch does not meet the interior of B meets B in only one point. Let M b e a subspace of Hn and let x E Hn. The ;erojection of x ont o M by cx is the element YE M ·which is closest to x, i.e., such that cx(y- x) i nf { 0< ( z - X) = l z E M} • (1) The exi stence and uniqueness of the projection are established by the following "theorem (see also Meinardus p. 2, Kothe p. 347 ). Theorem 2.1 l€t o< be a strictly convex norm on H, let M be a n subspace of H , and let x E: II • n Then there is a unique y E: M which n satisfies (1). Proof. Consider the set M' = \ z EM \ ex( z) > 2 O<.(x)} • all zeM', e<(x)+cx{z-x) ~ O<(z) > 2 cx(x); • ex( 0- x), and the infimum in ( 1) is not approached on M'. hence For <X(z-x) > <X(x) Since M- M' is compact , the infimum in ( 1) is attained for some y eM. Now let y' e AI be such tha t scalars c, cy+ ( 1- c )y' E: M cx(y'- x) = oc{y- x). Then for all and hence ex( c(y-x) + ( 1-c )(y•-x) ) = cx( cy+ ( 1-c )y' - x ) ~ oc(y-:x) = cx{y'-x). 6 Since ex is strictly convex, The function y- x = y'- X I y' = y. PM,cx. which carries x into it.s projection on M by ~ is called the project.ion function. notat.ion and Henceforth, whenever t.he PAl,cx. is used, it. "is presumed that ~ is strict.ly convex and M is a subspace of IIn or other appropriate Hi !bert space. confusion result.s, the shorter forma P11 and P may be used. Where no 7 CHAPI'ER III BASIC PROPERTIES OF THE PROJECTION FUNCTION The follo1dng theorem shows that the projection function is "almost linear". Theorem 3.1 P(x)+y if Proof. The function P is homogeneous, and .M,O< yEM. Assume, for purpos e of contradiction, that P is disThen there wi 11 be a sequence continuous at x. and lim 1-i>......., . ,..,... P(x.1 ) ~P(xi)] is unbounded. \Jc.) 1 such that X == or else P(x+ y} = z j P(:x), However, the boundedness is implicit in the proof of Theorem 2.1. By the definition of P, we have «{P(x.)- x.) ~ 1 for every i. 'X(P(x)- x. ) 1 1 Take limits as i-.> DO to obtain ex( z- x) which implies that ~ C<(P(x}- :x), z == P{x), a contradiction. Now let P{ x) == u. Then oc{ u- x) ~ ex{ s- :x) for all s E: lf, and for any nonzero scalar c, oc{cu- c:x) = lc\ cx{u- x) ~ \c\ C<{s- :x) == o<(cs- ex), which imp lies that «( cu- c.x) ~ O<(s- ex) have P(cx)= cu. For C= 0 for all s E-M. this result is trivial. Hence we 8 Now let y E-M. We have cx(P(x)- x) ~ <X{s- x), (X(P(x) + y- .( x + y)) ~ D<(s + y- (x+ y)) for all s E-M. Since s-:- y also runs over all of M, the last inequality implies that, P(x+ y) = P( x ) + y. Theorem 3.2 PM(y) = 0 ''here Proof. Every x E-H n and We have [J can be expressed uniqu ely as Furthermore, z E-M. x .,. y+ z, then = y+ z, z = PM(x). x = (x - P(x)) + P(x), and by Theorem 3. 1, P(x- P( x )) = P( x )- P( x ) = 0, so the representation exists. have X If we P(x) = P(y) + z = z, so the representation is unique. Theorem 3. 3 Proof. If For every p r oj ection function Let x b e such that and IIP\I<X« = cx.(P( x )) P(x)= 0, the resu lt is trivial. 1 = O<(x) = 11 PII 01 1X which imply that l\P , rxi\O<cx <. 2. 11 and cx.( x )= 1. If not, then <X( 0- x) > O<(P(x)- x) = cx(P(x)) ~ cx{P(x)- x) + cx(x), 1\Pl\o:<X <. 2. It will be shown later (Chapter 5) that this inequality is the best possible. 9 CHAPrER IV LINEARITY OF THE PROJECTION FUNCTION The projection function is not linear for every norm and subspace. For example, consider the norm 0< on real n given by 3 and determine kernel PM,cx.' where M is the one-dimensional subspace spanned by y~ {y ,y ,y ). Minimizing cx(x- cy) over all real c by 1 2 3 ordinary variational techniques gives the re su lt = which is not a. subspace for all y. Hence P M,cx is not linea r for all y. This example suggests the follo1ri.ng characterization of linearity. Theorem 4.1 kernel P 11 ·~ P is linear if and only if M,O<. is a subspace. ' Proof. Let The function The necessity of the stated condition is obvious. x,ye. H n and decompose them as according to Theorem 3.2. x~ x' + P(x), Y= y' + P(y), Then by Theorem 3.1, P(x+y} = P(x' +y' +P(x)+P(y)) = P(x' +y') + P(x) + P(y). Since x',y' ~kernel P, x' + y' E kernel P, and P(x+ y) ... P(x) + P(y). {l Hence P is linear. Theorem 4.2 I f dim M ~ n-1, then PM o< is linear. ' Proof. Theorem 3. 2, Let xE:Hn-M' y € kernel P. multiples of y. andlet y=x-P(x). Theny.JOandby Let L be the subspace of all scalar Then it is clear that L c: kernel P, since by 10 Theorem 3•1 P{cy) = cP{y) == 0 Now let z e kernel P. for all scalars c. Since dim M= n-1, H is a direct sum n of 11 and L, and z = z + z , 1rhere z e L and z E: M. By Theorem 3. 1, 1 1 2 2 P(z) = P(z )+ z = z • But P(z)= 0; hence z = 0 and z= z 1 E: L. 1 2 2 2 Therefore L= kern e l P and P is linear by Theorem 4. 1. Theorem 4. 3 If PM <X is linea r for all r-dimensi onal subspaces ' M, where r ? 1, th en it is linear for all subspaces of higher dimension. Proof. Let N be a subspace with dim N > r, purpose of contradiction, that PN is not linear . and assume, for Then by Theorem 4. 1 its kernel is not closed under addition, i.e., there exist two elements xi' x 2 of kerne 1 PN such that PN(x 1 + x ) = 2 y /= o. Now choos e an r-dimensional subspace M of N which contains y. Then x ,x E kernel P.M' 1 2 the hypothesis. but P (x1 + x ) 11 2 = y /. 0, 1rhich violates 0 11 CHAPl'ER V THE PROJECTiVE BOUND The real number Q{~) defined by Q{<X) sup M is c a lled the project ive bou11;,d. of <X. The following theorem shows that the supremum i s finite, and that for 1 ~ k ~ n - 1 the supremum is attained for some Ic- dirnen sional subspace M. Theorem 5.1 The sets of real numbers = { cx(PM O((x)) ' I oc(:x ) = 1, M is k-dimensional} fork= 1,2, ••• ,n-1 are identica l. Further more, Skis bounded and contains its supremum Q(<X). Proof. Suppose c ESk; we must sholr that c E":Sj for any j= 1,2, ••• ,n-l. For some k-dimensional subspace M and some x EH , n c = 0(,( y)' y = PM(x), e<(x) = 1. If y= x, then c = 1 and e E S. is easily shown. J If y.j, x, then c<(z- x) ~O<(y- x) for all z EM, i.e., we have c<( z) ~ ~( y- x) for all z €: y- x + M. By Theorem 1. 1 there is a support hyperplane y-x+N for the equilibrated convex body {z!oc(z)~O<(y-x)} at y- x, such that y- x+ M c y- x+ N, tha t is, M C.N. any j-dimensional subspace of N which contains y. Let L be Then 0<( z) >.- O<(y-x) for all z E y- x + L, that is, ~( z- x) ~ cx(y- x) for all z E-L. y = PL(x) and c E Sj. Hence 12 Therefore, all the Sk are equal, and we need to prove the second assertion only for s 1 • Theorem 3.3 shows that s 1 is bounded. Then either s 1 contains its supremum or there would be two sequences {xi' and { yi\ ~(x.) = ~(y.} = 1 1 such that for all i, and 1 lim i-> oO ~( PL. (xi) ) = (1) Q(cx), 1 where L. is the subspace spe.nned by y.. 1 By taking o.ppropriate sub- 1 sequences, we can also require that lim i-> 00 x. = x, lim i->OO y.1 = 1 lim i-+ 00 y, PL (x.) . l. (2) 1 ,.... = (3) If L is the subspace spanned by y, then clea rly wE L. No·w· let z ~ L; then z= cy for some scalar c. By the definition of PL , i <X( x i - cyi ) ~ ex( xi -PL. (xi) ) 1 for every i. Taking limits as i -> 0() , Since z EL was arbitrary, W= PL(x). we have OC(x- z) ~ O<(x- w). From (2), <x(x)= 1; from (1) and (3), cx(v)= Q(O<); hence Q(e<) ~s 1 • From Theorem 3.3, we have CorollarY 5.2 For any strictly convex norm ex, The upper limit is approached for strictly convex norms which B 13 [t I O<.(~-xl:: 1] y = PM(x) approximate the "maximum norm" 0( on real H given by 2 ex (See Fig. 2.) e<(x) ~ 1 or..{y) ~ 2 The lower limit is attained by the norms described in the next chapter. XI Fig. 2. A strictly convex norm ~for which Q(~) is close to 2. 14 CHAPI'ER VI PROJECTIVE NORMS A strictly convex norm projective norm. IX on H for 'rhich Q(O() = 1 is called a. The inner produc: norm (x,x)i is projective, a.nd so are the "elliptical" norms (x,T(x))t, where T is a positivedefinite self-adjoint linea r transformation of H • later we shall n give examples of non-elliptical projective norms on real H • 2 For spaces of dimension three or higher, all projective norms a.re elliptical, both in the real case (I~Irutani) and in the complex ca.se (Bohnenblust). Lemma 6.1 Suppose ex is a projective norm, PM,o< is linear, and N c:: kerne l PM ex ' ' By Theorem 3.1, M = kerne l PN <X then Proof. Suppose x <: 11 and y E: N. The definitions of 0\(x) for all y E: N. PM(x+ y) = x. II PM 1\cr-o< and Q(c<) and the first hypothesis give ~ 1\PMI\0(~ o<(x+ y) ~ Q(cx) cx(x+ y) Hence that is, PN(x) = O, = O<(x+ y) x E: kernel PN. Now suppose x E kernel PN and 'rrite X=< x + x , where xi E-M and x 2 E: N. 1 2 PN(xi) + x 2 • By Theorem 3. 1, 0 = By the previous paragraph, Lemma 6. 2 PN(x) = PN(x 1 ) = 0. Hence x :. 0 and x= xi E :M. 2 If ~ is a. projective norm, then p li,O<. is linear for all subspa.ces M of H • n Proof. By Theorem 4.3, it is sufficient to prove PM is linear if M is one-dimensional. Let u be a nonzero element of lf, and let u + N be a support 15 hyperplane for the equilibrated convex body { x E Hn \ cx(x) ~ cx.(u}} at u. oc.(x)~O<(u) Then every x EN. Since forevery Hence xEu+N, u E: kernel PN. tha.tis, cx(x+u}~cx(u) By Theorem 4.2, PN is linear. dim N = n-1, dim kerne 1 PN == 1, and therefore N "" kernel PM By Lemma 6.1, for M == kerne 1 PN. and hence PM is linear by an appli- cation of Theore~ 4.1. i s linear and Suppose Lemma 6.3 M == kernel P N,oc. Proof. Theu <) = I. M = kernel PN' let x E Hn be arbitrary and First. assume x 1 + x , where x 1 e M and x 2 E N. Then the application 2 to xl + x2 gives an ide ntity. of both sides of PM + PN == I express it as X= PM + PN = I. If so x € kernel PN. Nov assume X + PN(x) = :x:, x e Iternel PN' PM(x) = x then Theore m 6.4 X E:M, then PM(x) On the other hand, if we have D and x eM. Let oc. be a. projective norm. for every subspace M of Iln' and if = M PN(x) = -1- N = kerne 1 P Then P M,cx is linear then M,tle.' kernel P.._1 ~.,ex I. and Proof. This follows directly from Lemmas 6.1, 6.2 and 6.3. Theorem 6.5 subspace M of H , n where Suppose P M,C1.. 1 ~ k ~ n- I, and for every k-dimensional is linear and either p li "" kernel N,e< or, equivalently, N = kernel PM,OI.• Then ~ is projective. Proof. 0 PM~+ PN <X. ' ' = I, ( 1} Assume, for purpose of contradiction, that Q{cx) > 1. Then there wi 11 be a k-dimensional subspace M and x, y E H n such that 16 y O<(y) = Clearly y /: x. Let = PM(x), IIPMIIt~-t~- o<(x) ·= Q(cx) O((x) > O<(x). N = I{ erne 1 PU. 0 f. y- x t N, (2) By Theorem 3. 2 and ( 2), £X(x) c cx(y- (y-x )) < D<(y) By Lennna 6.3 the two conditions in (1) are equivalent. (3) We use the latter condition and a pp ly both sides of it to y, obtaining the relation y + PN(y) = y, or PN(y) c O, which contradict s {3). fl We can now exhibit examples of non-elliptical projective norms on real H • 2 Consider the norm o<(xl' x 2 ) = where ( lx 11P + lx2 \p )1/p ( l X 1 I q + lx2 I q ) 1/q { 1 1 - + - = 1. p q We shall show that 0<. satisfies the hypotheses of Theorem 6.5 with k= 1. By Theorem 4. 2, PM « is ' linear for all one- dimensi onal subspaces M. Following the notation of Theorem 6.5, we let u span M and let v span N = kerne 1 P~.1 • By examination of the unit b a ll (see Fig. 3. Example of a nonelliptical projective norm. Fig. 3 ), we see that i f u = ( 1, 0) or (0,1), then the hypotheses of Theorem 6.5 are satisfied. In other cas es, u and v are in adjacent quadrants, and we can also demand, without loss of generality, that u 1 = v 1 = 1. 17 Since v E kerne 1 PM' 0< ( v + cu) is minimal for c -= 0. For sufficiently small c, v+ cu is in the same quadrant with v. Hence if v is in the first quadrant, (4) (The same ar~tment can be used, mutatis mutandis, if v is in the fourth quadrant.) We can minimize (4) by differentiating to c. (O<.(v+cu))P 'nth respect Since the minimum occurs at C= 0, this gives Since u and v are in adjacent quadrants, sgn u 2 sgn v = - 1, and 2 hence This gives v, which spans w== ( l,rr ) 2 N = I'ernel PM. We compute (note p+q = pq) which spans kerne 1 PN. 1 Jw21 ~ ( ,:21) which shows that q-1 M = kernel PN. Similarly, 1re find the = ::: 18 CHAPTER VII DUAL NORMS AJ-."'D PROJECT! ON If ex is n norm on Hn' the du o. l norm O(D is defined by \(x,y)\ cx(y) If uf. 0 and vis such tha t l xI {v,x)= 1} for the equilibra t ed conve x body i s a support hyperplnne ~ x \ cx( x ) ~ O<(u)} calle d a dua l of u vrith r e spect to e<. at u, then v is Corolla ry 1.2 shows tha t e a ch nonze ro u h a s at leas t one dual. We s ha ll ne e d some elementary r e sults about the dua l norm and the dual. If uf. 0 and v is a dua l of u with r espect to ex, Propos ition 7.1 then cxD(v) = 1/~(u) and u is a dual of v with res pect to O<D. esis, I 0, {v, x/(v,x)) = 1. Therefore, by hypothex( x/(v,x) ) = cx(x} /I ("'· ,x)\ ~ ()((u), tha t is, Proof. For (v,x) l(v,x)l cx(x) 1 cx(u) which holds even for (v,x) = 0, and with equality for x= u. fore There- cxD(v) = 1/~(u). Now assume (u,x)= I. "" sup y/.0 Then \(x,y)\ cx(y) l(x,u)l cx(u) = and hence u is a dual of v with respect t.o ~· Corollary 7. 2 For all x E Hn' . O(DD(x) = O<(x). 1 cx(u) (j 19 Proof. Let. y be a dual of x with respect. to ex (if x/ 0). O{(x) = 1/ocD(y). Then But. x is also a dual of y wit.~ respect to IXD' and hence CXDD(x) = 1/0<D(y). () We can also apply Proposition 7.1 to show tha t. if u and v are duals, then they give equality in the generalized IWlder inequality I()( (u )cxD( v )I ~ 1. This fact is sometimes used to define duals. Propos ition 7.3 If CXD is strictly convex, then every nonzero u has a unique dun. l w-ith respect to ex. Proof . Let. v and v be duals of u with respect. to ex. 1 2 (v ,u) = (v ,u} = 1 and for any scalar c, 1 2 Then \ c(vpn) + (1-c) (v ,u) \ 2 O((u) = 1 = o<(u) u Since «n is strictly convex, v 1 == v • 2 Theorem 7 •1 to cx.. First. a.ssUllle v E M1 and v is a dual of u with respect. Then for any x ~ M, (v,u-x} = (v,u}- (v,x} = 1; hence cx(u-x) ~ cx(u) and u E kernel P. Now assume u f kerne 1 P. Then Then u ~kernel P if and only M,e< .1. if there is a dual v of u wi t.h respect to 0< such that. v (: M • Proof. Suppose u/ O. ()((u+x)~«(u) for all x(:M. By Theorem 1.1, there is a support. hyperplane {xI (v,x)= 1} for the body { x I oc:(x} ~ 0<( u)} at. u which contains the flat. u + M. By definition, v is a Fig. 4. Illustration of the proof of Theorem 7.4. 20 Also, for every x EM, u + x is on the dual of u with respect to ~. (v,u) + {v,x) = 1. hyperplane, that is, Since · (v,u) ... l, (v,x)=O n and v E MJ.. Theorem 7.5 Suppose ~ and ~D are both strictly convex, p is M,~ linear, and = kernel p :MJ. = kernel p N then and h ence M,or. (1) l. N '«n P 4 is linear. N 'O<.D Proof. By Proposi-tion 7., 4, for every v E: H n there is a unique dual u with respect to cxD' and v is the unique dual of u with respect to~. By Theorem 7.4, v t: kernel PN1 ,cxD <.=> By a second application of Theorem 7 .4, N= kernel PM ex. • u E N. u EN< > v ~!I J.., since These two equivalences prove (1). ' Theorem 7.6 Suppose ~ and cxD are both strictly convex, PM,« is linear, and N ,.. kernel P M,OI. p l. then = N ,e<.D Proof. By Theorem 7.5, ( PM ex. ) P J. is linear. N 'cx.D n PNJ. 0( ' H ' x,y~H to show that for arbitrary 0 0 D , (y) - (PM cx. )H(y)) ' It is sufficient 21 (2) = x= x + x , 1 2 1 y E. N , y ~ Ml.. 1 2 easily. Let where x 1 EM, x Theorem 4. 2, Y= y 1 + y , where 2 g If ()(. e.nd CXD are both strictly convex, Q(oc:) = Q(ocD). Let M b e an (n- 1)- di mens iona l subspace of H Q(O<) = IIPM,()(\\OI.OP that EN, and let Then, by using Theorem 7. 5, ( 2) can be demonstrated Theorem 7. 7 Proof. 2 PM,Q(.. and let N = kernel PM,~. is linear , and by Theorem 7. 6, n such Then by PNt,ocD = (PM,~ )H. Hence = e<D( ( PM<l'.)H(x) ) :{o 1:: = sup x,y;to = sup y~O <XD(x) \(x, PMe<(y))\ o<D(x) CX'.( y) ( o]y) ~ \ (x, PM,e<( y}) \ O(D(x) ) cx(PAi,O( ( y)) Q(oc). sup y/:o cx(y) To establish the reverse inequality Q(~) ~ Q(ocD)' interchange the roles of 0( and O<n· Theorem 7.8 a If ex is a projective norm, then ~Dis strictly convex. Proof. Let v 1 and v 2 be two vect~rs such that O<D( cvl + (l-c)v2 ) ~ O<D(vl) = 1XD(v2) (3) 22 for all scalars c. We must prove that v 1 =v2 • If v 1 =v result is trivial; therefore "-e asswne v 1 ~ 0 /= v • 2 2 =o, this \cv +(1-c)v I cis a scalar) is a. flat contain1 2 and such tha t· x E K =) CX"D(x) ~ cxD(v 1 ) by (3). By The set K ing v c and v 1 2 Theorem 1. I, there is a support hyperplane { x I (u, x ) = 1} contain- ing K. Then u is a dual of both v 1 and v hence v 1 and N= \v o.nd v 2 )l.; with respect to cxD' and 2 are both duals of u 1\'"ith resp e ct to ex. I..et 11= tv }J_ 1 2 then by Theorem 7.4, u €I,erne l PM,o< and uE kernel PN,0(· Since the Icerne l s are one-dimensional, both are equal to the subspe,c e L spanned by u. By Theorem 6.4, are linearly dependent, and U::: N= kern e l PL,o:.• v 1 = bv 2 Hence v for some scalar b. and v 1 2 We substi- tute into (3) to obtain ()(D ( ((b-l)c + l)v \ (b-l)c + 1\ ~ 1 Hence and v 1 =v 2• 2 ) for all scalars c, 1rhi ch imp lies that b = 1 Therefore t<D is strictly convex . Theorems 7.7 and 7.8 together give Corollary 7.9 If o<. is a projective norm, so is O(D. 23 CHAPrER VI I I THE GENERALIZED RECIPROCAL Suppose th~t throughout this chapter ~ is a strictly convex norm on H , ~ is a strictly convex norm on Hm' n F : II -> II m n is a linear function, R = range F, K = kernel F. Then let x EH be · arbi tre.ry, y E: Hm be such that n x' -= y - PK,~(y), F(y) = PR,c<(x), that is, the point on the flat y+ K which is closest to the origin. Fig. 5. The geometric definition of the generalized reciprocal of a linear function. 24 Now x' is independent of the choice of y, for a different choice of y would merely give another point on the flat y+ K. Therefore, there is a well-defined function F+o<p vhich carries x into x'. It is called the generalized reciprocal ofF with respect to~ andp. ~bere the norms are understood, the notation F+ will be used instead. If ex. and (3 are the inner product norms, then F+ is the MoorePenrose reciprocal of F. Many properties of the. Moore-Penrose reciprocal are specializations of the properties which we are about to derive. (See also Ben-Israel.) The following properties of F+ are consequences of the defi- · nition: (i) F+ is a homoge11eous function, (i-i) if PR ex and PK,~ (iii) kernel F+ = kernel PR cx ' (iv) range F (v) F+F = (vi) FF+ ' + : p ' ' kernel PK,P = I are linear, so is F+ ' K,cx. ' ' (vii) PR,f3 F+ . if 1S linear, (viii) if F is nonsingular, (ix) for nonzero scalars c, rank F + = rank F, Properties (i) and (ii) are obvious. If tion). If and x' /= 0. then then x'= 0 (following our previous nota- x E kernel PR ,o< , x f. kerne 1 PR,O<., then the flat Y+ K does not contain 0, Hence we have (iii). By Theorem 3.1, PK ~(x') = PK,~(y-PK ~(y)) = 0. z = y- PK,f (y) for some y, and 7 7 z = F+(F(y)). If PK ~{z)= 0 7 Hence we have 25 property (iv ). To evaluate z - PK,p(z) F+(F(z)) we can use Y= z. Then F+(F(z)) = and ,.,..e have {v). F(F+(x)) = F(x') = F(y- PK,~ {y)) = F(y) By the definition, = PR 0<. (x), and we have (vi). ' If F+ is linea r, then by (v) PK,P is linear . By (iv) 're have rank F+ :a dim kernel PK,,6 = m- dim K = rank F, "Vrhich proves (vii). Properties (vii i) and (i :x: ) are obvious. ~roperties (v), (vi) and (vii) can be used as an alternate definition of F+ in some cases, as the followin g theorem shows. Theorem 8. 1 If G: H -> II n m is a. linear function such that GF "" (1) = (2) FG rank G = rank F , then G = F + • Proof. . Let x E R; then x = ~( y) for some y E H , and m G(x) ~ G(F(y)) = (I- PK,p ){y) = F+(F(y)) = F+(x), (3) by (1) and property {v). For any v E H , n by (3) with X= PR,~(w) and the definition ofF+. have range F+ c range G. Therefore, we The projection functionB in (1) and (2) are linear, and hence F+ is linear by property (ii ). Then by 26 rank F + = rank F = rank G. property {vii) and hypothesis, fore range F + = range G. There- Then F+(x)=O by property (iii), Now let xEkernel PROC.. G(x) ~ range G = range p+,' .and by (2), F(G(x)) Hence G(x) ~K also. PR ~(x) - ' = 0. Since by property (iv) and Theorem 3.2, range F+ and K have only 0 in common, G( x) = 0 = F+(x). Since R and kernel PR,OC together span Hn' the fact that Tre have G(x) = F+(x) for x on these two sets shows that G= F+. Lemma 8.2 [] IfM and N are subspaces of H and dim N ~ dim M, n x E- N (I kerne l PM • then there is at least one nonzero '()( Proof. ~ X E- N I (x, X) == 1 3 • Let S be the sphere M. a continuous mapping from S to Then p gives By the Borsuk-Ulam Theorem (see P(x) = P( -x). Spanier, p. 266 ), there is e.n xES such that Since Pis a homogeneous function, P(x)= 0. Theorem 8. 3 If F: H m ~ H n is a linear function of positive rank, then 1 ~in£ tliG\\e<p \r ank(F+G ) < rankF~ b t\F+I\~p 2 < (4) where b = 1 if rank F = n, and b = Q(cx) otherwise. Proof. Suppose ra.nk(F + G) <.. rank F; dim kerne l(F + G) By Lemma. 8.2, there is a. nonzero then > dim K. x E':- kernel(F+ G), i.e., 27 F(x} + G(x) = F+( G(x)), -F+(F(x)) such that x E kernel PK,« •. = o, Then by property {v), (5) F+(F(x)) = x, o.nd (5) becomes -x = F+(G(x} ), wlli ch yi e lds and establishe s the first ine quality in (4). No'r let y,{ 0 be such that f3(l!.,+{y)) z and let = \IF+II(3C( C((y), (6) , (7) PR o<(y}. = From the definition of F+ we have Also, «(z) ~ \\PR ~~~~tl.~(y) ~ Q(O<) 1X{y). ' we haveR= H, z= y and cx.(z)=O<(y). n O<.(z) where b is as in (4). ~ In the case where rank F= n lienee b cx(y), (9) Then (6), (8) and (9) together yield ( 10) Now let w 1 = F+(z); clearly w v 1 E- range F+ = kernel PK,~· Hence 1 .f 0. Then by property (iv) PK,p(w 1 ) = 0, that is, p(w) ~ ~(v 1 ) for all v in p(w + v) ~ p .(w 1 ) for all v E: K, that is, the flat w +K. 1 By Theorem 1.1, there is a. support hyperplane for 1 28 i "" Hm \ ~ ( w) ~ 13 ( w 1) 1 e.t w 1 which the equilibrated convex body contains w 1 + K. {wl This hyperp'la.ne can be written a..s m + c w. L' 1 i=2 . w , \r , ••• , 1rm 2 3 where No1r let t c2, c3, ... ' c m ( 11) scalars} , span e. subspace which includes K. G: ll -> H m 1 be the linear function for which n ( 12) = o, ( 13) i= 2,3, ••• ,m. w , w , ••• , wm span all of K, (13) implies that (F+G)(w):: 0 3 2 for all wE K. Also, for vrl' ,.,..hich does not belong to K, ..,.-e have, Since by (12), property (vi) and (7), PR C<(z)- z = 0. ' re.nk.(E' + G) <. rank F • Therefore, ( 14) For some nonzero w Eli , which ve can write as m 1r = d.,... ' 1 1 we have = • = 0 we would have an a.bsurdi ty, .since G /= 0 by ( 12). 1 we can divide: by ld \ to obtain 1 If d Therefore, ex( z) = • The denominator is the norm of a. point on the support hyperplane { 11); Hence by (10) 11 G \\~f ~ t~~.(z) 0(( z) b • ( 15) 29 The second inequality in (4) then follows from (14) and (15). I The third inequality in (4) £ollovs from Corollary 5.2. In the case where F is nonsingular, (4) reduces to inf \ II G \\Ol~ \ F + G singular 1 1 = This result has also been proyed by others (see also Franck p. 1297, Kahan p. 775, and Maitre p. Theorem 8.4 ~no). A necessary and sufficient condition that (F+)+=F for every F is that ~and ~be projective norms. Proof. If ex. and (3 are projective norms, then all projections are linear by Theorem 6.4, and by property (ii ), so is F+. Let + + R' =range F and K' =kernel F • Then by Theorem 6.4 and properties (iii ) , ( i v), ( v) and (vi ) , I - PK,p ' = Also, rank F+ =rank F by property (vii); hence F= (F+)+ by Theorem 8. 1. Conversely, if (F+)+ = F, then .I - PK,(3 I ' and ~and ~ are projective norms by Theorem 6.5. Theorem 8.5 If ·CX. and p are projective norms, then = ( 16) 30 Proof. By properties {vi) and {v), and by Theorem 6. 4, FF+ = p R,OI.. = I - PM,cx.' F+F = By Theorem 6.4, I - p K, p ... PN,~ ' R = kernel PM, ~X Theorem 7.8, ~D end and M== kernel p N = kernel PK,{J K = kernel PN,p. Pn are strictly convex. R,O< ' ' By Then by Theorem 7.5, and Since R J. == kernel F H and Kl = range F H, ( 16 ) follows by Theorem 8.1, with G replaced by (F+)H and F replaced by FH. It is conjectured that (16) is true even i f 0< and pare not projective norms. 31 REFERENCES Ben-Israel, A. and A. Charles. eralized inverses. Bohnenblus~, Frederic. J. SIAM 11, 667-699 (1963). A cha.ra c~erization of complex Hilberl spaces. Por~ugalia.e Ma~hema.tica 3, Eggleston, H.G. Convexity. Franck, M. Pierre. Contributions ~o ~he ~heory of gen- 103-109 ( 1942). Cambridge U. Press, New York, 1958. Sur la. meilleure approximation d'une matrice donnee par une ma.trice si11guliere. C .R. Aca.d. Sci. 253, 1297-1298 ( 1961). Halmos, Paul H.. Finite dimens ional vector spaces. Princeton U. Press , Princeton, 1947. Householde r, Alston s. The the ory of matrices in numerical analysis. Blais de 11, New York, 1965. w. Knhan, Numerical linear algebra. Can. Math. Dull. 9, 757-801 ( 1961 ). Ka.kutani, S. Some characterizations of Euclidean spaces. Jap. J. of Math. 16, 93-97 ( 1939 }. Kothe, G. Topologische lineare Raume I. Springer-Verlag, Berlin, 1960. Maitre, Jean-Fra.n~ois and Nguyen Huu Vinh. 1 d une matrice Evaluation de la. distance a !'ensemble des ma~rices de rang r. C.R. Aca.d. Sci. 262, 910-912 (1966). Meina.rdus, Gunter. Approxima~ion of functions: methods ( ~r. larry L. Schumaker). 1967. ~heory and numerical Springer-Verlag, New York, 32 Spanier, Edwin II. 1966. Algebraic topology. McGraw-Hill, San Francisco,