Fundamental Convex Euclidean Geometry
`and its Applications
`
`Jon Dattorro
`
`June 2003
`
`c° 2001 Jon Dattorro, all rights reserved.
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`for Jennie Columba
`
`♦
`
`Antonio
`
`♦
`
`♦
`
`and Sze Wan
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`Sooner or later just like the world first day,
`Sooner or later we learn to throw the past away.
`−Gordon Sumner
`
`Preface
`
`Philosophy in Ph.D., to some these pages may seem stark; quite the con-
`trary... Very few places in life is it possible to achieve a glimpse of perfection,
`e.g., musical performance, sports,...
`Why do this... purpose is belief will make life better for others in some re-
`spect, reflects hope for the future. Passion...art...what we leave behind...life
`is short... do this regardless
`
`-Jon Dattorro, Stanford 2003
`
`i
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`G?     ?     ?         ?
`
`
`
`ii
`il
`
`Ericsson Exhibit 1123
`ERICSSONv. ETRI
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`Acknowledgements
`
`Reflecting on help given me all along the way, I am awed by my debt of
`gratitude:
`
`Anthony, Teppo Aatola, Bob Adams, Chuck Bagnaschi, Jeffrey Barish, Keith
`Barr, Steven Bass, David Beausejour, Leonard Bellin, Dave Berners, Barry
`Blesser, Stephen Boyd, Merril Bradshaw, Gary Brooks, Jack Brown, Patti
`Brown, Joe Bryan, Barb Burk, John Calderone, Kathryn Cal´ı, Terri Carter,
`Reginald Centracchio, Bonnie Charvez, Michael Chille, Jan Chomysin, John
`Cioffi, Sandra, Josie, and Freddy Colletta, Judy Copice, Kathy and Rita
`Copley, Gary Corsini, Domenico, Yvonne, Christine, and John D’Attoro,
`Cosmo Dellagrotta, Robin DeLuca, Lou D’Orsaneo, Tom Destefano, Peggy
`Donatelli, Jeannie Duguay, Pozzi Escot, Terry Fayer, Maryam Fazel, Carol
`Feola, Valery and Evelyn Ferrullo, Martin Fischer...(Brown U.), Salvatore
`Fransosi, Stanley Freedman, Tony Garnett, Ed Gauthier, Jeanette Genovese,
`Emilia Giglio, Chae Teok Goh, Gene Golub, Tricia Goodrich, Heather Graham,
`Robert Gray, David Griesinger, Robert Haas, George Heath et al..., Roy
`Hendrickson, Martin Henry, Mar Hershenson, Haitham Hindi, Evan Holland,
`Leland Jackson, Rene Jaeger, Joakim Jalden, Sung Dae Jun, Max Kamenetsky,
`Seymore Kass..., Patricia Keefe, James Koch, Paul Kruger, Helen Kung,
`Kurzweil..., Mike Ladra, Lynn Lamberis, Paul Lansky, Karen Law, Francis
`Lee, Scott Levine, Hal Lipset, Nando Lopez-Lezcano, Pat Macdonald, Ed
`Mahler, Sylvia and David Martinelli, Joyce, Al, and Tilly Menchini, Lisa
`McFall, Ginny Magee, Jamie Jacobs May, Paul and Angelia McLean, Teresa
`Meng, Tom Metcalf, Andy Moorer, Denise Murphy, Walter Murray, John
`O’Donnell, Ray Ouellette, Sal Pandozzi, Bob Peretti, Manny Pokotilow,
`Timothy Rapa, Doris Rapisardi, Katharina Reissing, Myron Romanul, Marvin
`Rous, Antonetta and Carlo Russo, Eric Safire, Anthony, Susan, and Esther
`Scorpio, John Senior, Robin Silver, Josh, Richard, and Jeremy Singer, Terry
`Stancil, Timothy Stilson, Brigitte Strain, John Strawn, Albert Siu-Toung,
`David Taraborelli, Robin Tepper, Susan Thomas, Stavros Toumpis, Georgette
`Trezvant, Jack, Dan, Stella, and Rebecca Tuttle, Maryanne Uccello, Joe
`Votta, Julia Wade, Shelley Marged Weber, Jennifer Westerlind, Bernard
`Widrow, Todd Wilson, WinEdt, George and MaryAnn Young, Donna and
`Joe Zagami
`
`iii
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`1 INTRODUCTION
`
`1 Introduction
`
`1
`
`There will be a virtual flood of applications with the realization that many
`problems hitherto believed non-convex can be transformed or relaxed into
`convexity. example, LMI books [1] [2].
`
`Circuit design: analog/digital filter synthesis [3], chip design [4, §4.7],
`[Barcelona], economics [5] [6] [7] ...
`
`[4, §4.3] [8] discuss the relaxation of NP-hard combinatorial problems by
`semidefinite programming. antenna array design, structural mechanics, med-
`ical imaging, ...
`
`Convex geometry and linear algebra are inextricably bonded...
`
`Summarize what lies ahead...
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`2
`
`2 Essential convexity theorems, definitions
`
`There is relatively less published pertaining to matrix -valued convex sets and
`functions. We present only a few pertinent results; purposely abbreviated.
`We assume the reader to be comfortable with chapters 2 and 3 from [9],
`while familiar with chapters 4 and 5 there. The essential references are [10]
`[9] [11]. The reader is referred to [12] [13] [14] [15] [16] (in that order) for a
`more comprehensive treatment of convexity.
`
`2.1 Sets
`Definition. Convex set. A set C is convex iff for all Y , Z ∈ C and
`0≤ µ≤ 1,
`µ Y + (1 − µ)Z ∈ C
`(1)
`
`⋄
`
`Under that defining constraint on µ , the linear sum in (1) is called a
`convex combination of Y and Z . If Y and Z are points in Euclidean space
`Rn or Rm×n, then (1) represents the closed line segment joining them. All
`line segments are thereby convex sets; so are all affine sets (§3.1.1), any ray
`(§3.4.2), halfspace (§3.2.1), hyperplane (§3.2.2), and subspace.1 Apparent
`from the definition, a convex set is a connected set. [18, §3.4,§3.5]
`Example. Orthant: the name given to a higher-dimensional generaliza-
`tion of the term quadrant from the classical Cartesian partition of R2. The
`
`orthant Rni- for example, identifies the region in Rn whose members’ sole neg-
`ative coordinate is their ith (analog to quadrant II or IV). The most common
`+ or Rn×n
`is the nonnegative orthant Rn
`(I) to which membership denotes all
`+
`nonnegative vector- or matrix-entries respectively. The nonpositive orthant
`- or Rn×n
`Rn
`(III) denotes all negative or zero entries. Orthant convexity is
`-
`easily verified by definition (1).2
`¤
`
`1A nonempty subset of a vector space Rn is called a subspace if every vector of the form
`αx + βy , for α,β∈ R , is in the subset whenever x and y are both in the subset. [5, §2.3]
`A subspace contains the origin, by definition, and is a convex set. Any subspace that
`does not constitute the whole vector space is called a proper subspace; for example, any
`hyperplane through the origin. The vector space is itself a subspace, [17, §2.1] inclusively,
`although not proper.
`2We will later learn that all orthants are self-dual simplicial cones. (§3.6.2)
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`3
`
`Theorem. Intersection. [9, §2] [11, §2] The intersection of an arbitrary
`⋄
`collection of convex sets is convex.
`Theorem. Image, Inverse image. [11, §3] [9, §2] Let f be a mapping
`from Rp×k to Rm×n.
`• The image of a convex set C under any affine function
`f (C) = {f (X) | X ∈ C} ⊆ Rm×n
`
`(2)
`
`is convex.
`
`• The inverse image of a convex set F ,
`f−1(F ) = {X | f (X)∈F} ⊆ Rp×k
`a single or many-valued mapping, under any affine function f is convex.
`⋄
`Each converse of this two-part theorem is generally not true; id est, given
`f affine, a convex image f (C) does not imply that set C is convex, and
`neither does a convex inverse image f−1(F ) imply that set F is convex. A
`counter-example is easy to visualize when the affine function is an orthogonal
`projector [19] [5]:
`
`(3)
`
`Corollary. Projection on subspace. [11, §3] The orthogonal projection
`⋄
`of a convex set on a subspace is another convex set.
`The corollary is true more generally for projection on hyperplanes. [14, §6.6]
`Again, the converse is not true. Shadows, for example, are umbral projections
`that can be convex when the object providing the shade is not.
`
`2.1.1 Vectorized matrix inner product
`
`Euclidean space Rn comes equipped with a vector inner product
`
`< y , z > = yTz
`
`(4)
`
`that is linear. The vector inner product for matrices is calculated just as it
`is for vectors by first transforming a matrix in Rp×k to a vector in Rpk by
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`4
`
`concatenating its columns in the natural order. For lack of a better term, we
`shall call that transformation vectorization. For example, the vectorization
`of Y = [y1 y2 · · · yk]∈ Rp×k is [20] [21]
`vec Y ∆=
`
`
`∈ Rpk
`
`
`
`y1
`y2
`...
`yk
`
`(5)
`
`Then the vectorized-matrix inner product is the trace of the matrix inner
`product; for Z ∈ Rp×k, [9, §2] [10, §0.3.1] [22, §8] [23, §2.2]
`< Y , Z > ∆= tr(Y TZ) = vecT Y vec Z
`
`(6)
`
`where
`
`(7)
`
`tr(Y TZ) = tr(Z Y T ) = tr(Y Z T ) = tr(Z T Y ) = 1T(Y ◦ Z)1
`and where ◦ denotes the Hadamard product3 of matrices [24] [25, §1.1.4].
`For example, consider any particular vectors v and w and take any ele-
`ment C1 from a matrix-valued set in Rp×k. Then the vector inner product of
`C1 with vwT is
`< vwT , C1 > = vTC1w = tr(wvTC1) = 1T¡(vwT )◦ C1¢ 1
`Example. Application of the image theorem. Suppose the set C ⊆ Rp×k
`is convex. Then for any particular vectors v∈ Rp and w∈ Rk, the set of vector
`inner products
`ℜ ∆= vTCw = < vwT , C > ⊆ R
`
`(8)
`
`(9)
`
`is convex. This result is a consequence of the image theorem. Yet it is easy
`to show directly that a convex combination of inner products from ℜ remains
`an element of ℜ .
`To verify that, take any two elements C1 and C2 from the convex matrix-
`valued set C , and then form the vector inner products (9) that are two
`3The Hadamard product is a simple entry-wise product of corresponding entries from
`two matrices of like size; id est, not necessarily square.
`
`¤
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`5
`
`elements of ℜ by definition. Now make a convex combination of those inner
`products; videlicet, for 0≤ µ≤ 1,
`µ < vwT , C1 > + (1 − µ) < vwT , C2 > = < vwT , µ C1 + (1 − µ)C2 > (10)
`The two sides are equivalent by linearity of the inner product. The right-hand
`side remains a vector inner product of vwT with an element µ C1 + (1 − µ)C2
`from the convex set C ; hence belongs to ℜ . Since that holds true for any
`two elements from ℜ , then it must be a convex set.
`More generally, vwT may be replaced with any particular matrix Z ∈ Rp×k
`while convexity of the set < Z , C > ⊆ R persists. Further, replacing v and
`w with any particular respective matrices V and W of dimension compatible
`with C , the set V TCW is convex because it is a linear mapping of C .
`2.1.1.1 Frobenius. When Z = Y in (6), the Frobenius norm is resultant;
`
`¨
`
`
`
`2 = < Y , Y > = tr(Y T Y ) = Xi, j
`kY k2F = k vec Y k2
`
`Y 2
`
`ij = Xi
`
`λ(Y T Y )i = Xi
`
`σ(Y )2
`i
`
`(11)
`where λ(Y T Y )i is the ith eigenvalue of Y T Y , and σ(Y )i is the ith singular
`value of Y . When Y is normal, σ(Y ) =|λ(Y )| , thus
`F = Xi
`λ(Y )2
`kY k2
`i
`
`(12)
`
`Because the metrics are equivalent
`
`kX− Y k2F = k vec X− vec Y k2
`2
`and because vectorization (5) is a linear bijective map, vector space Rp×k is
`isometrically isomorphic with Rpk in the Frobenius sense.4
`
`(13)
`
`4An isometric isomorphism is a linear bijective mapping (one-to-one and onto
`[17, App.A1.2]) that preserves distance.
`For example,
`the orthonormal operator
`Q : Rn → Rn, where Q ∈ Rn×n is an orthogonal matrix (§C.6), is an isometric isomor-
`phism. Yet the isometric operator T : R2 → R3, where
`0 
`T =
`1
`0
`0
`1
`
`
`0
`and R(T ) ∆= R3, is injective but not surjective [17, §1.6].
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`6
`
`2.1.2 Symmetric matrices
`
`Definition. Symmetric subspace. Define a subspace of RM×M : the set
`of all symmetric M×M matrices;
`SM ∆= ©A = AT ∈ RM×Mª
`This subspace of symmetric matrices SM is isomorphic [17, §2.8-8,§3.2-2]5
`[26] with the vector space RM (M +1)/2 whose dimension is the number of
`free variables in a symmetric M × M matrix. The orthogonal complement
`[19] [5] of SM is SM⊥ the subspace of all antisymmetric matrices; id est,
`SM ⊕ SM⊥ = RM×M .
`⋄
`Indeed, any square matrix A∈ RM×M can be written as the sum of its sym-
`metric and antisymmetric parts: respectively, A = (A + AT )/2 + (A − AT )/2.
`The symmetric part is orthogonal in RM 2
`to the antisymmetric part; videlicet,
`tr¡(AT + A)(A − AT )¢ = 0
`
`(14)
`
`(15)
`
`
`
`YMM
`
`
`
`Then because the metrics become equivalent,
`
`kX− Y k2F = k svec X− svec Y k2
`5An isomorphism of a vector space is a transformation equivalent to a linear bijective
`mapping. The image and inverse image under the transformation operator are then called
`isomorphic vector spaces.
`
`2
`
`(17)
`
`When a matrix is symmetric in SM , the vectorization transformation (5)
`to RM 2
`is identical although we may instead visualize in subspace RM (M +1)/2
`which remains isomorphic but not isometric. Lack of isometry is a spatial
`distortion due now to a disparity in metric between RM 2
`and RM (M +1)/2. To
`visualize in RM (M +1)/2, we must make a correction: For Y = [Yij] ∈ SM ,
`Y11√2Y12
`Y22√2Y13√2Y23
`Y33...
`
`svec Y ∆=
`
`∈ RM (M +1)/2
`
`(16)
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`7
`
`for X ∈ SM , and because symmetric vectorization (16) is a linear bijective
`mapping, svec is an isometric isomorphism on the symmetric matrix sub-
`space; in other words, SM is isometrically isomorphic with RM (M +1)/2 in the
`Frobenius sense under the transformation svec .
`
`2.1.2.1 Hollow matrices
`Definition. Symmetric hollow subspace. [27] Define a subspace of SM :
`the set of all symmetric M×M matrices having zero main-diagonal;
`∆= ©A ∈ SM | δ(A) = 0ª
`SM
`δ
`where δ(A) isolates the main diagonal of A (§C.5). This subspace of symmet-
`ric hollow matrices is isomorphic with subspace RM (M−1)/2. The orthogonal
`is SM⊥δ
`complement of SM
`the subspace of all antisymmetric matrices having
`δ
`δ ⊕ SM⊥δ = RM×M .
`main diagonal δ(A)∈ RM ; id est, SM
`⋄
`Any matrix A∈ RM×M can be written as the sum of its symmetric hollow
`and antisymmetric antihollow parts: respectively,
`
`(18)
`
`A =µ 1
`
`2
`
`(A + AT ) − δ2(A)¶ + µ 1
`
`2
`
`(A − AT ) + δ2(A)¶
`
`(19)
`
`The symmetric hollow part is orthogonal in RM 2
`hollow part; videlicet,
`
`to the antisymmetric anti-
`
`trµµ 1
`
`2
`
`(A + AT ) − δ2(A)¶µ 1
`
`2
`
`(A − AT ) + δ2(A)¶¶ = 0
`
`(20)
`
`SM and SM
`δ are convex sets.
`
`2.1.3 PSD cone
`
`Definition. Positive semidefinite (PSD) cone. The set of all symmetric
`positive semidefinite matrices of particular dimension M ×M is called the
`positive semidefinite cone:
`
`SM
`+
`
`∆= ©A ∈ SM | A º 0ª
`
`(21)
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`8
`
`It is a unique immutable non-polyhedral closed pointed nonempty convex
`cone in the subspace of symmetric matrices SM . The positive definite ma-
`trices comprise the cone interior.
`
`int SM
`
`+ = ©A ∈ SM | A ≻ 0ª
`
`(22)
`
`⋄
`
`∂ S2
`+
`
`
`
`· α ββ γ ¸
`
`β
`
`γ
`
`α
`
`Figure 1: Truncated boundary of PSD cone in S2 plotted in isomorphic R3 ;
`courtesy, Alexandre W. d’Aspremont. Plotted is a 0-contour of the mini-
`mum eigenvalue (564). The geometry is not as simple in higher dimensions
`[13, §II.12], although for real matrices the PSD cone is self-dual [28, §II]
`(§3.6).
`
`We call the set K a convex cone iff (§3.4.2)
`Γ1 , Γ2 ∈ K ⇒ ζ Γ1 + ξ Γ2 ∈ K for all ζ , ξ ≥ 0
`The set of all positive semidefinite matrices forms a convex cone because any
`pair satisfies definition (23); [24, §7.1] videlicet, for all ζ1 , ζ2 ≥ 0 ,
`ζ1 A1 + ζ2 A2 º 0
`A1 º 0 , A2 º 0
`ζ1 A1 + ζ2 A2 ∈ SM ⇐
`A1 ∈ SM , A2 ∈ SM
`
`(23)
`
`(24)
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`9
`
`Observe the notation Aº 0 ; meaning,6 the symmetric part of A (§C.2) be-
`longs to the positive semidefinite cone in the subspace of symmetric matrices,
`while A≻ 0 denotes membership to that cone’s interior. (§3.6.1.1)
`The convex cone SM
`+ is more easily visualized in the isomorphic vector
`space RM (M +1)/2 whose dimension is the number of free variables in a sym-
`metric M×M matrix. When M = 2 the PSD cone is semi-infinite in expanse
`in R3, having boundary illustrated in Figure 1. When M = 3 the PSD cone
`is six-dimensional, and so on.
`
`2.1.3.1 PSD cone boundary. To construct the PSD cone, we resort
`to the basic definition of positive semidefiniteness for A ∈ SM ;7 A º 0 ⇔
`yTA y ≥ 0 for all y∈ RM. The PSD cone is formed by the intersection of
`an infinite number of halfspaces specified by the basic definition, hence it is
`closed [28, §II]; the PSD cone contains its boundary.
`Reader pg.15...
`To see the halfspaces, imagine for each particular y the product yTAy is a
`linear function of the matrix entries... show for M=2...
`
`need the following for EDM boundary arguments...
`
`• For all y, [sic] yTAy = 0 defines boundary...
`• yTAy proportional to coefficient of projection on PSD cone. (Appendix)
`• coefficient proportional to eigenvalue when...
`• Hence 0 eigenvalue indicates A on boundary.
`PSD cone in Figure 1 is strictly convex. define...
`In higher dimensions, that is no longer true. [29, §II.A]
`All the positive semidefinite matrices having at least one 0 eigenvalue
`reside on the boundary of the PSD cone in any dimension. The boundary is
`delimited by all the supporting hyperplanes defined by that scalar inequality.
`
`6For matrices, the notation A º B denotes comparison on SM with respect to the
`positive semidefinite cone; id est, A º B ⇔ A − B ∈ SN
`+ . For vectors, a º b denotes
`comparison on RM with respect to the nonnegative orthant, while ≥ is reserved for scalar
`comparison on the real line with respect to the nonnegative real line as in aT y ≥ b .
`7Because yTA y = yTAT y , A is almost always assumed symmetric. [24, §7.1]
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`10
`
`Conversely, boundary is composed of all matrices whose rank is less than full.
`
`By the proper-cone boundary theorem in §3.4.3, there exist rays having
`base 0 through the boundary of the PSD cone of any dimension.
`
`Prove that the direction of every ray on the boundary is an exposed di-
`rection.
`
`Exposed directions of any convex set are a dense subset [11] of all extreme
`directions?
`β
`
`In Figure 1, the only matrix having two 0 eigenvalues lies at the origin.
`
`0
`
`0.5
`
`γ
`
`1
`
`1
`
`0.75
`0.75
`
`0.5
`0.5
`
`0.25
`0.25
`
`0
`0
`
`-1
`
`α
`
`-0.5
`
`0
`
`0.5
`
`1
`
`Figure 2: Truncated boundary (tiled) of PSD cone in isomorphic R3 sliced
`by a plane through the origin. (Looking downward from behind with respect
`to Figure 1.) The intersection of the plane with the PSD cone contains two
`rays whose directions are extreme with respect to either the intersection or
`the PSD cone.
`
`extreme combination
`It follows from the extremes theorem (§3.4.4) that any element of a convex set
`may be expressed as a linear combination of its extreme elements. Symmetric
`rank-one matrices constitute all the extreme directions of the PSD cone.
`[28, §III] [30, §6] For example, any (symmetric) positive semidefinite matrix
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`11
`
`can be expressed as a conic combination of symmetric rank-one matrices; that
`follows from diagonalization. If we limit consideration to bounded positive
`semidefinite matrices A such that tr A = 1, then any matrix from that set
`may be expressed as a convex combination of symmetric rank-one matrices.
`
`2.1.3.2 Polyhedral cones within
`Definition. Set slice. We define a slice of a set C as the intersection
`of C with a (two-dimensional) plane. When C is convex, the slice remains
`convex by the intersection theorem (§2.1).
`⋄
`
`slice dissection
`
`The PSD cone of any dimension comprises an infinite number of two-dimen-
`sional polyhedral cones revealed by slicing it with any plane through the
`origin. The extreme directions (§3.4.4) of those polyhedral cones must be
`extreme directions of the PSD cone. [11, §18]
`Indeed, any slice through the origin of the PSD cone is a polyhedral cone
`having two extreme directions. We sketched rays corresponding to a few
`arbitrarily chosen slices in Figure 3. Conversely, in Figure 3, any two rays
`sketched are extreme directions of some slice through the origin. The rays
`shown emanating from the origin all lie along the boundary of the PSD cone
`and along the relative boundary of the corresponding polyhedral cone. Hence
`the extreme directions of the polyhedral cones are also extreme directions of
`the PSD cone, and vice versa.
`By (23) it follows that there exist rays emanating from the origin which
`travel along the boundary of the PSD cone of any dimension, because each
`of those rays corresponds to an extreme direction of some polyhedral cone
`made by slicing the PSD cone using a plane through the origin.
`
`Alternate construction of PSD cone is the convex hull of all the extreme
`directions and the origin, by the extremes theorem in §3.4.4.
`
`2.1.3.3 Hyperplanes hinged on PSD cone.
`for this section. From Sweep.nb,
`Show that all symmetric rank-one 3x3 and 2x2 and all symmetric positive
`semidefinite rank-two 3x3 matrices can be described by matrix on pg.141
`of Nascence notebook. Plot a three-dimensional slice of the surface of the
`
`(23) is the inspiration
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`12
`
`γ
`
`α
`
`β
`
`Figure 3: Truncated drawing of the PSD cone in isomorphic R3 showing some
`arbitrary rays, lining the boundary, corresponding to extreme directions yyT .
`(Peering over the top with respect to Figure 1.) Only in this dimension is
`the entire boundary constituted by extreme directions.
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`13
`
`six-dimensional PSD cone for particular s1 and s3; it is described completely
`by the nullspace of the hinge equations pg.140 ibidem
`
`Want to sweep rays corresponding to extreme directions of PSD cone,
`NOT its boundary.
`
`Extreme directions DO NOT constitute the boundary of the PSD cone
`except for the 2x2 case. We know this from a fundamental definition of
`positive semidefiniteness yTAy ≥ 0; id est,
`
`+ = {A ∈ Sm | < yyT, A > ≥ 0, y ∈ Rm}Sm
`defines the positive semidefinite cone; it is an intersection of halfspaces in the
`variable A∈ Rm(m+1)/2. All singular positive semidefinite matrices therefore
`constitute the boundary; id est, there are no positive definite matrices on the
`boundary,
`
`(25)
`
`
`
`
`
`+ = {A ∈ Sm∂ Sm + | < yyT, A > = 0, y 6= 0}
`
`(26)
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`14
`
`2.2 Functions
`
`The icon for the convex function is bowl-shaped (Figure 33, p.214), whereas
`the concave icon is the inverted bowl. Because of this simple inverse re-
`lationship, the usage of the term convexity is often implicitly inclusive of
`concavity in the literature. We will distinguish the two terms wherever con-
`venient. Despite the iconic imagery, the reader is reminded that the set of
`all convex, concave, quasiconvex, and quasiconcave functions contains the
`monotone [9, old§2.6.1] functions; e.g., [9, old§2, exer.2.43A].
`
`2.2.1 Convex functions
`The vector-valued continuous function f (X) : Rp×k→ RM is convex in X if
`and only if dom f is a convex set and, for each and every Y, Z ∈ dom f and
`0≤ µ≤ 1,
`
`f (µ Y + (1 − µ)Z) ¹
`
`RM
`+
`
`µf (Y ) + (1 − µ)f (Z)
`
`(27)
`
`Since comparison of vectors here is with respect to RM
`+ (118), the M -dimen-
`sional nonnegative orthant, the test prescribed by (27) is simply a comparison
`on R of each entry8 of the vector function. The vector-valued function case
`is therefore a straightforward generalization of conventional convexity theory
`for a real function. (See [9, §3,§4] for all the details.)
`When, under the same previous conditions, f (X) instead satisfies
`
`f (µ Y + (1 − µ)Z) ≺
`
`RM
`+
`
`µf (Y ) + (1 − µ)f (Z)
`
`(28)
`
`we shall say f is a strictly convex function.
`We are primarily interested in matrix-valued functions g(X). We choose
`symmetric g(X)∈ SM because matrix-valued functions are most often com-
`pared (31) with respect to the positive semidefinite cone SM
`+ in the subspace
`of symmetric matrices (§2.1.3).9 Yet some of the following results depend
`8This same conclusion also follows directly from the nice theory of generalized inequality
`(§3.6.1) that states f is convex if and only if wTf is convex for each and every
`w º 0. Discretization [30, §1] allows relaxation of the w inequality to: each and every
`w ∈{ei , i = 1 . . . M}; the standard basis for RM .
`9Function symmetry is not a necessary requirement for convexity; indeed, for A∈ Rm×p
`and B∈ Rm×k, g(X) = AX + B is a convex (affine) function in X on domain Rp×k with
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`15
`
`upon a scalar definition of positive (semi)definiteness (§C.2.2).
`Scalar-Definition. Convex matrix-valued function. [9, §3]
`g(X) : Rp×k→ SM is convex in X iff wTg(X)w : Rp×k→ R is convex in X for
`each and every kwk = 1.
`⋄
`Observing for each and every real vector w of unit norm, kwk = 1,
`[24, §7.7, prob.9]
`
`wTg(X)w ≤ t ⇔ g(X) ¹
`
`SM
`+
`
`tI
`
`(29)
`
`it then follows:
`
`Definition. Convex matrix-valued function.
`1) Epigraph. We define g(X) : Rp×k→ SM to be a convex function of X iff
`its epigraph
`
`epi g ∆= ©(X, t) | X ∈ dom g , wTg(X)w ≤ t , kwk = 1ª ⊆ Rp×k× R
`= {(X, t) | X ∈ dom g , g(X) ¹
`tI }
`
`SM
`+
`
`(30)
`
`forms a convex set.
`2) Inequality form. A function g(X) : Rp×k→ SM is convex in X iff dom g
`is a convex set and, for each and every Y, Z ∈ dom g and 0≤ µ≤ 1,
`
`g(µ Y + (1 − µ)Z) ¹
`
`SM
`+
`
`µ g(Y ) + (1 − µ)g(Z)
`
`(31)
`
`Strict convexity is defined less a stroke of the pen in (31) similarly to (28). ⋄
`
`It is well established that a continuous real function f : Rp×k→ R
`2.2.1.1
`is convex if and only if its epigraph epi f ⊆ Rp×k×R forms a convex set. [10] [9]
`[11] [15] [14] [5] Given a continuous matrix-valued function g(X) : Rp×k→ SM
`respect to the nonnegative orthant Rmk
`+ . Symmetric convex functions share the same
`benefits as symmetric matrices; e.g., (569)-(571). Horn [24, §7.7] likens symmetric matrices
`to real numbers, and (symmetric) positive definite matrices to positive real numbers.
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`16
`
`consequent to the scalar-definition, we defined the epigraph of g(X) in terms
`of the corresponding real function wTg(X)w ; id est,
`
`epi g = \kwk=1
`
`epi¡wTg w¢
`
`(32)
`
`Concisely then, the following are equivalent statements: For each and every
`real vector of unit norm, kwk = 1,
`1. wTgw is a convex real function,
`
`2. epi¡wTgw¢ is a convex set,
`
`3. g is a convex matrix-valued function.
`
`g(X) : Rp×k→ SM is convex in X if and only if
`Line Theorem. [9, §3]
`⋄
`it remains convex on the intersection of any line with its domain.
`Now we assume a twice differentiable function, and we drop the subscript
`SM
`+ from the inequality when it is apparent.
`
`Definition. Differentiable convex matrix-valued function.
`g(X) : Rp×k→ SM is convex in X iff dom g is an open convex set, and its
`second derivative g′′(X + t Y ) : R→ SM is positive semidefinite on each point
`along every line X + t Y that intersects dom g ; id est, iff for each and every
`X, Y ∈ Rp×k such that X + t Y ∈ dom g over some open interval of t ∈ R ,
`d2
`dt2 g(X + t Y ) º 0
`
`(33)
`
`Similarly, if
`
`d2
`dt2 g(X + t Y ) ≻ 0
`then g is strictly convex; the converse is generally false. [9, old§2.1.4]10
`
`(34)
`
`⋄
`
`10Quadratic forms constitute a notable exception where the strict-case converse is reli-
`ably true.
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`17
`
`Example. Matrix inverse. The matrix-valued function g(X) = X−1 is
`
`+ . For each and every Y ∈ SM , (§F.2.1.1, §C.2.3)convex on int SM
`d2
`dt2 g(X + t Y ) = 2(X + t Y )−1Y (X + t Y )−1Y (X + t Y )−1 º 0
`on some open interval of t∈ R such that X + t Y ≻ 0. Hence, g(X) is con-
`vex in X. This result is extensible;11 tr X−1 is convex on that same domain.
`[24, §7.6, prob.2]
`¤
`Example. X 2...
`
`(35)
`
`¤
`
`Example.
`Matrix exponential.
`The matrix-valued function
`g(X) = eX : SM → SM is convex on the subspace of symmetric circulant ma-
`trices. Applying the line theorem, for all t∈ R and for circulant X,Y ∈ SM
`we have (§F.2.5, (566), (724), §C.2.3)
`d2
`dt2 eX+ t Y = Y eX+ t Y Y º 0 ,
`because circulant matrices are commutative (§12.3).
`Changing the function domain to the subspace of all diagonal matrices
`reduces the matrix exponential to a vector-valued function (27) in an isomet-
`rically isomorphic subspace; [31, §5.3]12 known convex from the real-valued
`function case [9, §3].
`There are, of course, multifarious methods to determine function convex-
`ity, [9] each of them efficient when appropriate.
`
`(XY )T = XY
`
`(36)
`
`¤
`
`2.2.2 Quasiconvex functions
`Quasiconvex functions [9, §3] [10] [12] [14] are useful in practical problem
`solving because they are unimodal (by definition when non-monotonic); a
`global minimum is guaranteed to exist over the function domain or over any
`convex set in the function domain. In terms of sublevel set , their definition
`is elegant and analogous to the epigraph-form definition for convex functions:
`
`11 d/dt tr g(X + t Y ) = tr d/dt g(X + t Y ).
`12The matrix exponential of a diagonal matrix exponentiates each individual diagonal
`entry.
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`18
`
`Lν
`
`Definition. Quasiconvex matrix-valued function.
`1) Sublevel set. We define g(X) : Rp×k→ SM to be a quasiconvex function
`of matrix X iff dom g is a convex set, and for each and every ν ∈ R the
`corresponding sublevel set
`∆= ©X ∈ dom g | wTg(X)w ≤ ν , kwk = 1ª ⊆ Rp×k
`= {X ∈ dom g | g(X) ¹ νI }
`is convex.
`2) Inequality form. g(X) : Rp×k→ SM is a quasiconvex function of matrix X
`iff dom g is a convex set and for each and every Y, Z ∈ dom g and 0≤ µ≤ 1,
`g(µ Y + (1 − µ)Z) ¹ max{g(Y ), g(Z)}
`(39)
`
`(37)
`(38)
`
`⋄
`The sublevel set Lν of a matrix-valued function is an intersection of sub-
`level sets of real functions (37); similarly to the epigraph as discussed on
`page 15. While convex functions must have convex sublevel sets, it is not a
`sufficient condition for their definition as it is for quasiconvex functions.
`
`Example. Rank function.
`For A,B∈ Rm×n [24, §0.4]
`rank A + rank B ≥ rank(A + B)
`that follows from the fact [19, §3.6]
`dim R(A) + dim R(B) = dim R(A + B) + dim(R(A) ∩ R(B))
`
`For A ,B∈ SM+ [9, §3]
`rank A + rank B ≥ rank(A + B) ≥ min{rank A, rank B}
`that follows from the fact [30, §6]
`A ,B∈ SM
`N (A + B) = N (A) ∩ N (B) ,
`Rank is a quasiconcave function on SM
`+ because the right-hand side of (42)
`has the concave form of (39); id est,
`
`(40)
`
`(41)
`
`(42)
`
`+
`
`(43)
`
`rank(A + B) = rank(µA + (1− µ)B)
`
`(44)
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`19
`
`on the open interval (0, 1), which follows from the dyadic linear independence
`definition in §C.7.1.
`¤
`Definition. Differentiable quasiconvex matrix-valued function.
`Assume that function g(X) : Rp×k→ SM is twice differentiable, and dom g is
`an open convex set.
`Then g(X) is quasiconvex in X if wherever in its domain the directional
`derivative 13 [32] [33] becomes zero, the second directional derivative is posi-
`tive definite there [9, §3] in the same direction Y ;
`id est, g is quasiconvex if
`for each and every point X ∈ dom g , all nonzero directions Y ∈ Rp×k, and
`for t ∈ R ,
`
`d2
`
`g(X + t Y ) ≻ 0
`
`(45)
`
`g(X + t Y ) = 0 ⇒
`
`d d
`
`dt2¯¯¯¯t=0
`dt2¯¯¯¯t=0
`
`t¯¯¯¯t=0
`t¯¯¯¯t=0
`
`Conversely, if g(X) is quasiconvex then for each and every X ∈ dom g
`and all Y ∈ Rp×k,
`
`d2
`
`g(X + t Y ) º 0
`
`(46)
`
`⋄
`
`g(X + t Y ) = 0 ⇒
`
`d d
`
`2.2.3 More salient properties of convex and quasiconvex functions
`
`1.
`
`• A convex (or concave) function is assumed continuous on the rel-
`ative interior of its domain. [11, §10]
`• A quasiconvex (or quasiconcave) function is not necessarily a con-
`tinuous function.
`
`2. g convex ⇔ −g concave.
`g quasiconvex ⇔ −g quasiconcave.
`3. Convexity ⇒ quasiconvexity.
`Concavity ⇒ quasiconcavity.
`13By using a generalization of the Taylor series in §F.1.4, we extend the traditional
`definition of directional derivative so that direction may be indicated by a vector or a
`matrix.
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`2 ESSENTIAL CONVEXITY THEOREMS, DEFINITIONS
`
`20
`
`4. The scalar-definition of matrix-valued function convexity and the line
`theorem (§2.2.1) translate identically to quasiconvexity (and quasicon-
`cavity). [9, §3]
`5. Composition g(h(X)) of a convex (concave) function g with any affine
`mapping h : Rm×n → Rp×k, such that h(Rm×n)∩ dom g 6= ∅ , becomes
`convex (concave) in X ∈ Rm×n. Likewise for the quasiconvex (quasi-
`concave) functions g . [10, §B.2.1]
`• A nonnegatively weighted sum of convex (concave) functions re-
`mains convex (concave).
`• A nonnegatively weighted maximum of quasiconvex functions re-
`mains quasiconvex. A nonnegatively weighted minimum of quasi-
`concave functions remains quasiconcave.
`
`6.
`
`Ericsson Exhibit 1123
`ERICSSON v. ETRI
`
`

`

`3 BASIC CONVEX GEOMETRY
`
`21
`
`Figure 4: Convex hull of a random list of points in R3. Some points from
`that generating list reside in the relative interior of this convex polyhedron.
`[34, Convex Polyhedron, Avis-Fukuda]
`
`3 Basic convex geometry
`
`Convexity has an immensely rich structure and numerous appli-
`cations. On the other hand, almost every “convex” idea can be ex-
`plained by a two-dimensional picture. −Alexander Bar