Journal of Convex Analysis Volume 2 (1995), No.1/2, 173–183

The Convex Analysis of Unitarily Invariant Matrix Functions

A.S. Lewis^{1}

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1. email: aslewis@orion.uwaterloo.ca

Received 12 July 1994 Revised manuscript received December 1995

Dedicated to R. T. Rockafellar on his 60th Birthday

A fundamental result of von Neumann’s identifies unitarily invariant matrix norms as symmetric gauge functions of the singular values. Identifying the subdifferential of such a norm is important in matrix approximation algorithms, and in studying the geometry of the corresponding unit ball. We show how to reduce many convex-analytic questions of this kind to questions about the underlying gauge function, via an elegant Fenchel conjugacy formula. This approach also allows such results to be extended to more general unitarily invariant matrix functions.

Keywords : unitarily invariant norm, matrix function, Fenchel conjugacy, subdifferential, matrix optimization, extreme point, exposed point.

1991 Mathematics Subject Classification: Primary: 15A60 49J52, Secondary: 90C25 65F35

1. Introduction

Consider the vector space of m × n matrices, either real or complex. To be concrete we shall restrict attention to the complex case IC^{m×n} throughout: the parallel development for the real case will be immediately apparent. Many of the most important examples of norms ∥ · ∥ on IC^{m×n} are unitarily invariant:

∥V XU∥ = ∥X∥ for any X ∈ IC^{m×n}, U ∈ U_{n}, V ∈ U_{m}

(where U_{n} denotes the set of n × n unitary matrices). A famous fundamental result of von Neumann’s [9] (see for example [5]) states that such matrix norms can be characterized as composite functions of the form f(σ(·)) = f ∘ σ, where the function σ : IC^{m×n} → IR^{q} (with q = min{m, n}) has components σ_{1}(X) ≥ σ_{2}(X) ≥ … ≥ σ_{q}(X) ≥ 0, the singular values of the matrix X, and the function f : IR^{q} → IR is a symmetric gauge function (a norm on IR^{q} which is invariant under signchanges and permutations of the components). Von Neumann’s proof revolves around the

1 Research partially supported by the Natural Sciences and Engineering Research Council of Canada

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

174 A.S. Lewis / The convex analysis of unitarily invariant matrix functions

elegant idea that

(f ∘ σ)^{D} = f^{D} ∘ σ  (1.1)

(where ∥ · ∥^{D} denotes the polar, or dual norm). The most common examples fall into two families. The Schatten p norms correspond to f = ∥ · ∥_{p} (for 1 ≤ p ≤ ∞), special cases being the trace norm (p = 1), the Frobenius norm (p = 2), and the spectral norm (p = ∞). The other family are the Ky Fan k norms (for 1 ≤ k ≤ q), which correspond to the symmetric gauge function

f(γ) = sum of k largest of {|γ_{1}|, |γ_{2}|, …, |γ_{q}|},

the special case k = 1 giving the spectral norm once again, and k = q giving the trace norm. Such norms have been the focus of recent interest in matrix approximation algorithms (see for example [11]), and in a variety of investigations aiming to analyze the geometry of the unit ball in the matrix space, B_{f∘σ}, in terms of the geometry of the underlying ball B_{f} in IR^{q} (see [1], [12], [13], [3], [4]). In each case a central problem is the investigation of the subdifferential of f ∘ σ at a matrix X,

∂(f ∘ σ)(X) = {Y ∈ IC^{m×n} |
Re(traceZY^{∗}) ≤ f(σ(X + Z)) − f(σ(X)) ∀ Z ∈ IC^{m×n}}.

(1.2)

The aim of this paper is to give a simple, self-contained approach to this problem, giving back the subdifferential formula for (1.2) in [13] for example. Our idea will be to generalize von Neumann’s result somewhat by asking which convex functions (rather than simply norms) are unitarily invariant: appropriately, the key idea will be a Fenchel conjugacy formula analogous to von Neumann’s polarity formula (1.1):

(f ∘ σ)^{∗} = f^{∗} ∘ σ.

(For all ideas and notation from convex analysis we refer the reader to [8].) Since the subdifferential (1.2) can be identified (directly from the definition of the conjugate) as

∂(f ∘ σ)(X) = {Y | (f ∘ σ)(X) + (f ∘ σ)^{∗}(Y) = Re(traceXY^{∗})},

it becomes easy to calculate ∂(f ∘σ) in terms of ∂f. In this fashion we can link smoothness (and, dually, strict convexity) properties of the matrix function f ∘ σ with those of the underlying function f: in the norm case, such results appear in [1] and independently in [12]. Furthermore, the identification of smooth, extreme and exposed points of the matrix unit ball B_{f∘σ} in terms of those of the underlying unit ball B_{f} is also straightforward with these tools (c.f. [1], [12]). As we note, the results we derive in the norm case are not new. On the other hand, this new approach has twofold appeal. First, the assumptions on the underlying function f are weakened (essentially by dropping the requirement of positive homogeneity). Secondly, and perhaps more significantly, all the matrix analysis required is hidden in one key variational result of von Neumann’s (Theorem 2.1): we avoid having to use analytic parametrizations of the singular values (as in [10], for example), or any partitioning (as in [13], [3]).

We remark finally that an analogous development for weakly unitarily invariant convex functions of Hermitian matrices (functions satisfying F (X) = F (U^{∗}XU) for unitary U) may be found in [6]. Such functions have become rather important in optimization: an example is the logarithmic barrier, − log det X (for positive definite X).

2. Conjugates and subdifferentials of unitarily invariant functions

By IC^{m×n} we shall mean the real inner product space of m × n complex matrices, with the inner product ⟨X, Y ⟩ = Re(traceXY^{∗}). (The results we present can be immediately translated to the real case simply by replacing ‘unitary’ with ‘orthogonal’ throughout.) We shall also use ⟨·, ·⟩ to denote the standard inner product on IR^{q}. For a vector γ in IR^{q}, the entries of the m × n diagonal matrix Diag γ are given by (Diag γ)_{ij} = γ_{i} if i = j and 0 otherwise. The following result is essentially due to von Neumann (see the discussion in [3]).

Theorem 2.1. (von Neumann) For any m × n matrices X, Y and Z,

max{⟨V ZU, Y ⟩ | U ∈ U_{n}, V ∈ U_{m}} = ⟨σ(Z), σ(Y)⟩,  (2.2)

and hence

⟨X, Y ⟩ ≤ ⟨σ(X), σ(Y)⟩.  (2.3)

Equality holds in (2.3) if and only if there exists a simultaneous singular value decomposition of X and Y of the form

X = V (Diag σ(X))U, and
Y = V (Diag σ(Y))U,

with U in U_{n} and V in U_{m}.

Given any vector γ in IR^{q}, we write γ̂ for the vector with components |γ_{i}| arranged in nonincreasing order. Notice that σ(Diag γ) = γ̂. The special case of inequality (2.3) for diagonal matrices shows that for any vectors γ and μ in IR^{q},

⟨γ, μ⟩ ≤ ⟨γ̂, μ̂⟩.  (2.4)

This is also easy to see directly. A function f : IR^{q} → [−∞, +∞] is absolutely symmetric if f(γ) = f(γ̂) for any vector γ in IR^{q}. Let us call a q × q matrix a generalized permutation matrix if it has exactly one nonzero entry in each row and each column, that entry being ±1: we will denote the set of such matrices by Λ_{q}. Clearly f is absolutely symmetric if and only if

f(Qγ) = f(γ), for all γ ∈ IR^{q} and Q ∈ Λ_{q}.  (2.5)

A function F : IC^{m×n} → [−∞, +∞] is (strongly) unitarily invariant if

F (V XU) = F (X) for all X in IC^{m×n}, U in U_{n} and V in U_{m}.

The following simple result characterizes unitarily invariant functions on IC^{m×n} as functions of the form f ∘ σ, with f absolutely symmetric on IR^{q}.

Proposition 2.2. Unitarily invariant functions on IC^{m×n} are in one-to-one correspondence with absolutely symmetric functions on IR^{q}. Specifically, if the function F : IC^{m×n} → [−∞, +∞] is unitarily invariant then the function f : IR^{q} → [−∞, +∞] defined by

f(γ) = F (Diag γ)  (2.7)

is absolutely symmetric, with F = f ∘ σ. Conversely, for any given function f : IR^{q} → [−∞, +∞], the function f ∘ σ is unitarily invariant on IC^{m×n}.

Proof. Suppose that F is unitarily invariant, and define f by (2.7). Given any vector γ in IR^{q} we can choose m × m and n × n generalized permutation matrices Q_{m} and Q_{n} so that Q_{m}(Diag γ)Q_{n} = Diag γ̂. Then

f(γ̂) = F (Diag γ̂) = F (Q_{m}(Diag γ)Q_{n}) = F (Diag γ) = f(γ),

whence f is absolutely symmetric. Now fix any m × n matrix X, and choose a singular value decomposition X = V (Diag σ(X))U, with U in U_{n} and V in U_{m}. Then

F (X) = F (V (Diag σ(X))U) = F (Diag σ(X)) = f(σ(X)),

whence F = f ∘ σ. The converse is immediate since the set of singular values is unitarily invariant.

If (X , ⟨·, ·⟩) is a finite-dimensional, real inner product space, then given a function g : X → [−∞, +∞], the (Fenchel) conjugate of g is the function g^{∗} : X → [−∞, +∞] defined by

g^{∗}(y) = sup{⟨x, y⟩ − g(x) | x ∈ X }.

It is always convex and lower semicontinuous. The function g is proper if it never takes the value −∞ and the set domg = {x | g(x) < +∞} is nonempty. In this case, for points x in domg we can define the subdifferential

∂g(x) = {y ∈ X | g(x) + g^{∗}(y) = ⟨x, y⟩},

whose elements are called subgradients. When g is proper and convex, g^{∗} is also proper, with g^{∗∗} = g providing that g is also lower semicontinuous. The standard reference for all these ideas is [8]. The following collection of results is an easy exercise, using inequality (2.4), (2.5) and the Chain Rule.

Lemma 2.3. Suppose that the function f : IR^{q} → [−∞, +∞] is absolutely symmetric. Then:

(a) The function f is differentiable at a vector γ if and only if it is differentiable at γ̂.

(b) The conjugate function f^{∗} is absolutely symmetric.

(c) For any vector μ,

f^{∗}(μ) = sup{⟨γ, μ̂⟩ − f(γ) | γ_{1} ≥ γ_{2} ≥ … ≥ γ_{q} ≥ 0}.

(d) If μ lies in ∂f(γ) then μ̂ lies in ∂f(γ̂).

The next result is our key tool: a simple formula for the conjugate of any unitarily invariant function.

Theorem 2.4. (Conjugacy Formula) If the function f : IR^{q} → [−∞, +∞] is absolutely symmetric then (f ∘ σ)^{∗} = f^{∗} ∘ σ.

Proof. For any m × n matrix Y we have (using von Neumann’s Theorem (2.1)):

(f ∘ σ)^{∗}(Y)
= sup{⟨X, Y ⟩ − f(σ(X)) | X ∈ IC^{m×n}}
= sup{⟨V ZU, Y ⟩ − f(σ(Z)) | Z ∈ IC^{m×n}, U ∈ U_{n}, V ∈ U_{m}}
= sup{sup{⟨V ZU, Y ⟩ | U ∈ U_{n}, V ∈ U_{m}} − f(σ(Z)) | Z ∈ IC^{m×n}}
= sup{⟨σ(Z), σ(Y)⟩ − f(σ(Z)) | Z ∈ IC^{m×n}}
= sup{⟨γ, σ(Y)⟩ − f(γ) | γ_{1} ≥ γ_{2} ≥ … ≥ γ_{q} ≥ 0}
= f^{∗}(σ(Y)),

the last step being a consequence of Lemma 2.3. As a consequence we obtain a simple formula for the subdifferential of a unitarily invariant function. Corollary 2.5. (Characterization of Subgradients) Let us suppose that the function f : IR^{q} → (−∞, +∞] is absolutely symmetric, and that the m × n matrix X has σ(X) in domf. Then the m × n matrix Y lies in ∂(f ∘ σ)(X) if and only if σ(Y) lies in ∂f(σ(X)) and there exists a simultaneous singular value decomposition of the form

X = V (Diag σ(X))U, and
Y = V (Diag σ(Y))U,

with U in U_{n} and V in U_{m}. In fact

∂(f ∘ σ)(X) =
{V (Diag μ)U | μ ∈ ∂f(σ(X)), U ∈ U_{n}, V ∈ U_{m}, X = V (Diag σ(X))U}.

Proof. The matrix Y lies in ∂(f ∘ σ)(X) if and only if

f(σ(X)) + f^{∗}(σ(Y)) = (f ∘ σ)(X) + (f ∘ σ)^{∗}(Y) = ⟨X, Y ⟩,

by the Conjugacy Formula (Theorem 2.4). Since von Neumann’s Theorem (2.1) implies that for any X and Y,

f(σ(X)) + f^{∗}(σ(Y)) ≥ ⟨σ(X), σ(Y)⟩ ≥ ⟨X, Y ⟩,

we deduce that Y lies in ∂(f ∘ σ)(X) if and only if equality holds throughout. The first part now follows from the equality condition in von Neumann’s Theorem. One inclusion in the last formula is also now clear. To see the opposite inclusion, note that if μ lies in ∂f(σ(X)) and X = V (Diag σ(X))U for some unitary U and V then

⟨X, V (Diag μ)U⟩ ≤ (f ∘ σ)(X) + (f ∘ σ)^{∗}(V (Diag μ)U)
= f(σ(X)) + f^{∗}(μ̂)
= f(σ(X)) + f^{∗}(μ)
= ⟨σ(X), μ⟩
= ⟨V (Diag σ(X))U, V (Diag μ)U⟩,

using the Conjugacy Formula and Lemma 2.3. Hence V (Diag μ)U lies in ∂(f ∘ σ)(X) as required.

We can also now easily characterize those unitarily invariant functions which are convex and lower semicontinuous.

Corollary 2.6. (Characterization of Convexity) Suppose that the function f : IR^{q} → (−∞, +∞] is absolutely symmetric. Then the corresponding unitarily invariant function f ∘ σ is convex and lower semicontinuous on IC^{m×n} if and only if f is convex and lower semicontinuous.

Proof. Suppose that f is convex and lower semicontinuous. Then since f = f^{∗∗} we have by the Conjugacy Formula (Theorem 2.4),

f ∘ σ = f^{∗∗} ∘ σ = (f^{∗} ∘ σ)^{∗},

and so f ∘σ, being a conjugate function, is convex and lower semicontinuous. The converse is immediate, by restricting attention to diagonal matrices.

A symmetric gauge function on IR^{q} is a norm which is absolutely symmetric. Thus an absolutely symmetric convex function f : IR^{q} → (−∞, +∞] is a symmetric gauge function exactly when it is positively homogeneous (f(kγ) = kf(γ) for all γ in IR^{q} and scalar k ≥ 0), and finite and strictly positive except at 0. A famous result of von Neumann’s [9] states that unitarily invariant norms on IC^{m×n} can be characterized as functions of the form f ∘ σ where f is a symmetric gauge function. Evidently this result is a special case of the above corollary. The Characterization of Subgradients (Corollary 2.5), in the special case where f is a symmetric gauge function, subsumes the characterizations of subdifferentials of unitarily invariant norms in the recent papers [10], [13]. We illustrate with some wellknown examples.

Example 2.7. The c-spectral norms [7]. For any vector μ in IR^{q} with μ_{1} ≥ μ_{2} ≥ … ≥ μ_{q} ≥ 0, we can define a symmetric gauge function by f(γ) = ⟨μ, γ̂⟩: only convexity needs checking, and this follows by writing f as a maximum of linear functionals:

f(γ) = max{⟨μ, Qγ⟩ | Q a generalized permutation matrix}

(using inequality (2.4)). Hence the function ⟨μ, σ(·)⟩ is a unitarily invariant norm. The case where μ_{i} = 1 for i = 1, 2, …, k and 0 otherwise gives the Ky Fan k norm.

Example 2.8. The spectral norm. As we have seen, in the case where the function f is ∥ · ∥_{∞} we obtain the spectral norm. A straightforward calculation with the Characterization of Subgradients (Corollary 2.5) shows that the subdifferential of this norm at the matrix X is just the convex hull of matrices of the form (v^{1})(u^{1})^{∗} for column vectors u^{1} in IC^{n} and v^{1} in IC^{m} appearing in some singular value decomposition of X of the form X = ∑_{i=1}^{q} σ_{i}(X)(v^{i})(u^{i})^{∗} (c.f. Example 1 in [10], and also [2], [13]).

3. Differentiability and strict convexity

Given a finite-dimensional inner product space X, then a convex function g : X → (−∞, +∞] is differentiable at a point x in domg if and only if the subdifferential ∂g(x) is a singleton (in which case ∂g(x) = {∇g(x)}) [8, Thm 25.1]. Our Characterization of Subgradients (Corollary 2.5) now makes it easy to identify when convex, unitarily invariant functions are differentiable (c.f. [4, Cor 5.2]).

Theorem 3.1. (Gradient Formula) If a function f : IR^{q} → (−∞, +∞] is convex and absolutely symmetric then the corresponding convex, unitarily invariant function f ∘ σ is differentiable at the m×n matrix X if and only if f is differentiable at σ(X). In this case

∇(f ∘ σ)(X) = V (Diag ∇f(σ(X)))U,  (3.2)

for any matrices U in U_{n} and V in U_{m} with X = V (Diag σ(X))U, and furthermore

σ(∇(f ∘ σ)(X)) = ∇f(σ(X)).  (3.3)

Proof. In one direction the first part is clear (without convexity) simply by restricting attention to matrices of the form V (Diag γ)U for vectors γ in IR^{q}. Conversely then, suppose that f is differentiable at σ(X) (which therefore lies in the interior of domf). Since f must agree with f^{∗∗} on a neighbourhood of σ(X) [8, Thms 7.4 and 12.2], and consequently f ∘ σ agrees with f^{∗∗} ∘ σ on a neighbourhood of X (since σ is continuous), we may as well assume that f is lower semicontinuous (by replacing f with the lower semicontinuous function f^{∗∗} if necessary). Hence f ∘ σ is convex by the Characterization of Convexity (Corollary 2.6), and, by the Characterization of Subgradients (Corollary 2.5), any subgradient Y has σ(Y) = ∇f(σ(X)). The subdifferential is convex, and the Frobenius norm of each element is constant (∥∇f(σ(X))∥_{2}). Thus the set is a singleton (because the Frobenius norm is strict), and the result follows.

Given a function g : X → (−∞, +∞] which is lower semicontinuous. proper and convex, we say that g is essentially smooth if its subdifferential is a singleton whenever it is nonempty: in particular, a finite convex function on X is essentially smooth exactly when it is everywhere differentiable. We say that the function g is essentially strictly convex if it is strictly convex on any convex set on which the subdifferential is everywhere nonempty: in particular, a finite convex function on X is essentially strictly convex exactly when it is strictly convex. Essential smoothness and essential strict convexity are dual notions: the function g is essentially smooth if and only if the conjugate g^{∗} is essentially strictly convex (and vice versa). All these ideas may be found in [8, §26]. For the special case of the following result for norms, see [1].

Corollary 3.2. (Smoothness and Strict Convexity) Suppose that the function f : IR^{q} → (−∞, +∞] is proper, convex, lower semicontinuous and absolutely symmetric. Then f is essentially smooth (respectively essentially strictly convex) if and only if the corresponding unitarily invariant function f ∘ σ is essentially smooth (respectively essentially strictly convex).

Proof. Suppose first that f ∘ σ is essentially smooth. If ∂f(μ) is nonempty then so is ∂f(μ̂) by Lemma 2.3, and hence so is ∂(f ∘ σ)(Diag μ̂) by the Characterization of Subgradients (Corollary 2.5). Since f ∘ σ is essentially smooth it must be differentiable at Diag μ̂, whence f is differentiable at μ̂ by the Gradient Formula (Theorem 3.1), and hence at μ by Lemma 2.3. Conversely, suppose that f is essentially smooth. If ∂(f ∘ σ)(X) is nonempty then so is ∂f(σ(X)) by the Characterization of Subgradients. Hence f is differentiable at σ(X), and therefore f ∘ σ is differentiable at X by the Gradient Formula. The strict case follows by taking conjugates using the Conjugacy Formula (Theorem 2.4).

The example that we choose to illustrate this development is the special case of norms. The results in this case are known. However, as we remarked in the introduction, one of our principal concerns is to show how these may be derived in this framework in a concise, unified way, without further matrix analysis. Given a norm ∥ · ∥ on X, the dual norm ∥ · ∥_{∗} on X is defined by

∥y∥_{∗} = max{⟨x, y⟩ | ∥x∥ = 1}.

It is a straightforward computation to check that

(∥ · ∥^{2}/2)^{∗} = ∥ · ∥_{∗}^{2}/2.  (3.5)

The norm ∥ · ∥ is smooth when ∥ · ∥^{2}/2 is everywhere differentiable, and is strict when ∥ · ∥^{2}/2 is strictly convex.

Example 3.3. (Smooth and strict norms) Suppose that the norm ∥ · ∥ is a symmetric gauge function on IR^{q}. Then the corresponding unitarily invariant norm ∥σ(·)∥ is smooth (respectively strict) if and only if ∥·∥ is smooth (respectively strict), and the dual norm is ∥σ(·)∥_{∗}. To see this, note first that the discussion after the Characterization of Convexity (Corollary 2.6) ensures that |∥ · ∥| = ∥σ(·)∥ is indeed a unitarily invariant norm. By (3.5), the dual norm is determined by

|∥ · ∥|_{∗}^{2}/2 = (|∥ · ∥|^{2}/2)^{∗} = (∥σ(·)∥^{2}/2)^{∗} = ∥σ(·)∥_{∗}^{2}/2,

using the Conjugacy Formula on the absolutely symmetric function ∥σ(·)∥^{2}/2. It follows that |∥ · ∥|_{∗} = ∥σ(·)∥_{∗}. Now as we observed, ∥σ(·)∥ is smooth if and only if ∥σ(·)∥^{2}/2 is essentially smooth. Applying the previous result shows that this is equivalent to the essential smoothness of ∥·∥^{2}/2, and hence to the smoothness of ∥·∥. The strict case follows by taking conjugates. These characterizations first appeared in [1] and independently in [12].

The above example shows how we can use to advantage the fact that our analysis applies to a somewhat more general class of functions than symmetric gauge functions (even when these may be of primary interest): the most significant feature is that we do not require positive homogeneity. For example, if ∥ · ∥ is a symmetric gauge function and h : IR_{+} → (−∞, +∞] is lower semicontinuous, convex, nondecreasing, and finite at zero, then the function h(∥·∥) satisfies the conditions for our various characterizations (2.4, 2.5, 2.6, 3.1, 3.2), as well as any finite sum or supremum of such functions. Of course, such examples are not completely distinct from the symmetric gauge case, being decomposable into building blocks depending on some collection of symmetric gauge functions. However, it may not be transparent how to decompose a given function into this form, and there does not appear to be any analytic advantage to working with the function expressed in terms of symmetric gauge functions. We continue by studying an example of the above form, h(∥ · ∥), to derive further known results in this framework. Given a norm ∥ · ∥ on X, we denote the (closed) unit ball by

B_{∥·∥} = {x ∈ X | ∥x∥ ≤ 1},

and the indicator function of this set is defined by

δ_{B_{∥·∥}}(x) = \{ \begin{matrix}0, & if ∥x∥ ≤ 1, \\ +∞, & otherwise. \end{matrix}

If ∥x∥ = 1, the normal cone at x is defined by

N(x|B_{∥·∥}) = {y ∈ X | ∥y∥_{∗} = ⟨x, y⟩},

and it is easily checked that

N(x|B_{∥·∥}) = ∂δ_{B_{∥·∥}}(x)  (3.6)

(c.f. [8, pp. 215, 226]). Suppose now that ∥ · ∥ is a symmetric gauge function on IR^{q}. If we apply the Characterization of Subgradients (Corollary 2.5) to the function δ_{B_{∥·∥}} at a matrix X with ∥σ(X)∥ = 1, we obtain the following normal cone formula:

N(X|B_{∥σ(·)∥}) =
{V (Diag μ)U | μ∈N(σ(X)|B_{∥·∥}), U ∈U_{n}, V ∈U_{m}, X = V (Diag σ(X))U}.

This formula is analogous to the ‘dual set’ formulae in [3], or [13, Thm 3.2]). We conclude by showing how results on the extremal structure of the unit ball of a unitarily invariant norm appearing in [1], [12], for example, can be easily derived in this framework. Given a norm ∥ · ∥ on X, and a point x with norm 1, we say that x is an extreme point (of the unit ball B_{∥·∥}) if x = αy +(1−α)z for points y and z in the unit ball and α in (0, 1) implies that x = y = z, and x is a smooth point if the norm is differentiable at x. We say that x is an exposed point if there is a vector y such that the functional ⟨·, y⟩ is maximized over the unit ball uniquely at x. Equivalently [8, Cor 25.1.3],

∇∥y∥_{∗} = x, for some point y.  (3.7)

Theorem 3.4. (Extremal Structure) Suppose that ∥ · ∥ is a symmetric gauge function. Then a matrix X is exposed (respectively smooth, extreme) in the unit ball of the corresponding unitarily invariant norm ∥σ(·)∥ if and only if σ(X) is exposed (respectively smooth, extreme) in the unit ball for ∥ · ∥.

Proof. Suppose first that the vector σ(X) is exposed, so that ∇∥μ∥_{∗} = σ(X) for some vector μ. By Lemma 2.3 we also have ∇∥μ̂∥_{∗} = σ(X). Choose a singular value decomposition, X = V (Diag σ(X))U for some unitary U and V. Then the gradient of the dual norm ∥σ(·)∥_{∗} (see the previous example) at the matrix V (Diag μ̂)U is exactly X, by the Gradient Formula (Theorem 3.1), and hence X is exposed.

Conversely, suppose that X is exposed, so that X is the gradient of ∥σ(·)∥_{∗} at some matrix Y. Then by (2.7), ∇∥σ(Y)∥_{∗} = σ(X), whence σ(X) is exposed. The smooth case is a direct consequence of the Gradient Formula (Theorem 3.1). The final case is that of extreme points. First, if the vector σ(X) is not extreme in the unit ball B_{∥·∥} then there are vectors γ and μ distinct from σ(X) in the unit ball and an α in (0, 1) with σ(X) = αγ + (1 − α)μ. Choose a singular value decomposition X = V (Diag σ(X))U, with U in U_{n} and V in U_{m}, and define matrices Y = V (Diag γ)U and Z = V (Diag μ)U. Then clearly Y and Z are distinct from X in B_{∥σ(·)∥}, with X = αY + (1 − α)Z, and hence X is not extreme. Conversely, suppose that σ(X) is extreme, and yet that

X = α_{1}Y_{1} + (1 − α_{1})Z_{1}, for some α_{1} ∈ (0, 1),

where Y_{1} and Z_{1} are distinct from X in B_{∥σ(·)∥}. Let us define

Y = \{ \begin{matrix}\frac{1}{2}(X + Y_{1}), & if σ(X) = σ(Y_{1}), \\ Y_{1}, & otherwise. \end{matrix}

Then if σ(X) = σ(Y_{1}), since the Frobenius norm is strict we have that

∥σ(Y)∥_{2} < (∥σ(X)∥_{2} + ∥σ(Y_{1})∥_{2})/2 = ∥σ(X)∥_{2}.

Thus in either case σ(Y) ≠ σ(X). By defining Z similarly, we can write X = αY +(1−α)Z with α in (0, 1), and σ(Y) and σ(Z) distinct from σ(Z) in B_{∥·∥}. Clearly σ(X) is distinct from Qσ(Y) and Qσ(Z) for any generalized permutation matrix Q. Hence, since σ(X) is extreme it must be disjoint from the convex hull of the set

{Qσ(Y), Qσ(Z) | Q ∈ Λ_{q}}.

Via a separating hyperplane we see the existence of a vector μ in IR^{q} with

⟨μ, σ(X)⟩ > ⟨μ, Qσ(Y)⟩ and ⟨μ, Qσ(Z)⟩

for all Q in Λ_{q}. Choosing Q so that Qμ̂ = μ shows that

⟨μ̂, σ(Y)⟩ and ⟨μ̂, σ(Z)⟩ < ⟨μ, σ(X)⟩ ≤ ⟨μ̂, σ(X)⟩,

by (2.4). However this is in contradiction to the fact that, since the function ⟨μ̂, σ(·)⟩ is convex (by the example after Corollary 2.6),

⟨μ̂, σ(X)⟩ = ⟨μ̂, σ(αY + (1 − α)Z)⟩ ≤ α⟨μ̂, σ(Y)⟩ + (1 − α)⟨μ̂, σ(Z)⟩.

This completes the proof.

More generally, suppose that the set C ⊂ IR^{q} is closed, convex, and absolutely symmetric (which is to say that a point γ lies in C if and only if γ̂ lies in C). Then a matrix X is exposed (respectively extreme) in the set {Z | σ(Z) ∈ C} if and only if σ(X) is exposed (respectively extreme) in C. The proof is identical, with ∥ · ∥_{∗} replaced by δ_{C}^{∗}.

References

[1] J. Arazy: On the geometry of the unit ball of unitary matrix spaces. Integral Equations and Operator Theory, 4:151–171, 1981.

[2] H. Berens and M. Finzel: A continuous selection of the metric projection in matrix spaces. In L. Collatz, G. Meinardus, and G. Nurnberger, editors, Numerical Methods of Approximation Theory, Volume 8. Birkhäser, Basel, 1987.

[3] E.M. de Sá: Exposed faces and duality for symmetric and unitarily invariant norms. Linear Algebra and its Applications, 197,198:429–450, 1994.

[4] E.M. de Sá: Faces of the unit ball of a unitarily invariant norm. Linear Algebra and its Applications, 197,198:451–493, 1994.

[5] R.A. Horn and C. Johnson: Matrix analysis. Cambridge University Press, Cambridge, U.K., 1985.

[6] A.S. Lewis: Convex analysis on the Hermitian matrices. Technical Report CORR 93-33, University of Waterloo, 1993. Accepted by SIAM Journal on Optimization.

[7] C.K. Li and N.K. Tsing: Duality between some linear preserver problems, II. Isometries with respect to c-spectral norms and matrices with fixed singular values. Linear Algebra and its Applications, 110:181–212, 1988.

[8] R.T. Rockafellar: Convex Analysis. Princeton University Press, Princeton, N.J., 1970.

[9] J. von Neumann: Some matrix inequalities and metrization of matric-space. Tomsk University Review, 1:286–300, 1937. In: Collected Works, Pergamon, Oxford, 1962, Volume IV, 205-218.

[10] G.A. Watson: Characterization of the subdifferential of some matrix norms. Linear Algebra and its Applications, 170:33–45, 1992.

[11] G.A. Watson: On matrix approximation problems with Ky Fan k norms. Numerical Algorithms, 5:263–272, 1993.

[12] K. Ziȩtak: On the characterization of the extremal points of the unit sphere of matrices. Linear Algebra and its Applications, 106:57–75, 1988.

[13] K. Ziȩtak: Subdifferentials, faces and dual matrices. Linear Algebra and its Applications, 185:125–141, 1993.

184 A.S. Lewis / The convex analysis of unitarily invariant matrix functions HIER :

Leere Seite