Journal of Convex Analysis Volume 3 (1996), No.1, 153–166

On Extreme Singular Values of Matrix Valued Functions

Liqun Qi, Rob S. Womersley

School of Mathematics, The University of New South Wales, Sydney, N.S.W. 2052, Australia. e-mail: nsmooth@solution.maths.unsw.edu.au

Received June 9, 1994 Revised manuscript received November 14, 1995

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

This paper considers the extreme (typically the largest or smallest) singular values of a matrix valued function. A max characterization, using the Frobenius inner product, of the sum of the largest singular values is given. This is obtained by giving a lower bound on the sum of the singular values of a matrix, and necessary and sufficient conditions for attaining this lower bound. The sum f of the largest singular values of a matrix is a convex function of the elements of the matrix, while the smallest singular value is a difference of convex functions. For smooth matrix valued functions these results imply that f is a regular locally Lipschitz function, and a formula for the Clarke subdifferential is given. For a Gâteauxdifferentiable matrix-valued function f is a semiregular functions, while the smallest singular value is the negative of a semiregular functions. This enables us to derive concise characterizations of the generalized gradient of functions related to the extreme singular values and the condition number of a matrix.

Keywords : singular value, subdifferential, regularity.

1. Introduction

This paper is concerned with the extreme singular values of matrices and matrix valued functions. Typical functions of interest are the largest and smallest singular values of a matrix valued function A(x) ∈ IR^{m×n}, where x ∈ IR^{s} is a vector of design parameters. In control systems many important structural properties, such as robustness and noise sensitivity, can be expressed as inequalities involving the singular values of transfer matrices (e.g. [4], [5], [6], [23] and [27]). There is also interest in the structured singular value (see [5], [6] and [31] for example) in better representing system properties.

One well recognized difficulty is that a singular value may not be differentiable when it is multiple. This has led to a number of algorithms for optimization problems involving singular values based on nonsmooth (nondifferentiable) optimization principles, such as the Clarke generalized gradient [2]. Typically these are bundle methods and are only linearly convergent [24]. If better algorithms are to be developed then a better understanding of the differential properties of the singular values, and better representations of their generalized gradients are required.

A motivation for this work is the results of Overton and Womersley [22] on the sum of the

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

154 L. Qi, R. S. Womersley / On extreme singular values of matrix valued functions

κ largest eigenvalues of a symmetric matrix valued function. The singular values can be characterized in terms of the eigenvalues of a symmetric matrix. For example when m ≥ n the singular values of A are the square roots of the eigenvalues of A^{T} A. Alternatively the eigenvalues of

[ \begin{matrix}0 & A \\ A^{T} & 0 \end{matrix} ]

are the singular values of A and their negatives. However both these representations have disadvantages. Working with A^{T} A can destroy nice structure in the matrix valued function A(x) (for example if A(x) is affine). The second characterization increases the dimension, hence it is preferable to work directly with the singular values of A in those applications involving singular values, such as [3, 4, 5, 19, 23, 27].

In Section 2 we establish bounds on the singular values of a matrix. In Section 3 these bounds are used to derive a max characterization of the sum of the κ largest singular values of a matrix, in terms of the Frobenius inner product. The max characterization is established by showing that that the sum of the absolute values of the diagonal elements of a rectangular matrix is a lower bound of the singular values of the matrix, and giving a necessary and sufficient condition for attaining this lower bound. This max characterization readily shows that the largest singular value of a matrix is a convex function of the elements of the matrix. Identifying the elements which achieve the maximum gives a concise formula for the subdifferential (generalized gradient) of the sum of the κ largest singular values. Bounds on singular values of matrices are widely known (see [14], [16] for example). Subramani [30] provides a review of the inequalities relevant to characterizing sums of the largest singular values of a rectangular matrix.

Another convexity property of the largest singular value is given by Sezinger and Overton [29]. They establish that the largest singular value of e^{X}A_{0}e^{−X} is convex on any convex set of commuting matrices in IR^{n×n}, where A_{0} ∈ IR^{n×n} is fixed. The sensitivity of sums of singular values has also been studied by Seeger [28]. This paper concentrates on bounds on singular values and their use in characterizing the subdifferential of functions of the singular values of matrix valued functions.

The largest singular value of a matrix-valued function is discussed in Section 4, regarding it as a composite function (see [8] and [32] for typical uses of composite functions). When the matrix-valued function is smooth (at least once continuously differentiable), the sum of the κ largest singular values is regular and a formula for its Clarke subdifferential follows. When the matrix-valued function is only Gâteaux-differentiable, we use the Michel-Penot subdifferential, a modification of the Clarke subdifferential, to give similar results.

We then discuss the smallest singular value of a matrix in Section 5. The smallest singular value is the difference of the sum of the singular values of a matrix and the sum of all but the smallest singular values of a matrix. Hence the smallest singular value is the difference of convex functions. The properties of d.-c. (difference of convex) functions are studied in [11]. This framework also provides formulae for the Clarke subdifferential of the spectral radius of the inverse of a symmetric matrix, and the condition number of square matrix. These two functions are regular at points at which they exist.

This is slightly different to the situation for eigenvalues of symmetric matrices, where the sum of all the eigenvalues of a matrix is equal to the trace of the matrix, and hence is a linear function of the elements of the matrix. As the sum of the κ largest eigenvalues of a symmetric matrix is a convex function of the matrix elements [7], [13], [22] it immediately follows that the smallest eigenvalue is a concave function of the matrix elements.

Throughout this paper, we use IR^{m×n} and S_{n} to denote the spaces of all m by n real matrices and all n by n real symmetric matrices respectively, and use O_{n} and O_{m,n} to denote the spaces of all n by n and all m by n real orthogonal matrices respectively. We use I_{n} to denote the n by n identity matrix, and ||.|| to denote the Euclidean norm for vectors. We use capital letters to denote matrices and the corresponding small letters to denote their rows, columns and elements. For example, we use a_{i.}, a_{.j} and a_{ij} to denote the ith row, the jth column and the (i, j)-th elements of A respectively. Let p = min {m, n}. We also use A[i_{1}, i_{2}, …, i_{r}] to denote the corresponding principal submatrix of A ∈ IR^{m×n}, where 1 ≤ i_{1} < i_{2} < … < i_{r} ≤ p. For a matrix D = diag(d_{11}, …, d_{pp}) ∈ IR^{m×n}, all the off-diagonal elements of D are zero. For a symmetric matrix A, we use ρ(A) to denote its spectral radius. The positive semi-definite partial ordering on S_{n} is used to express matrix inequalities [14]. Thus for A, B ∈ S_{n} the inequality A ≥ B means that A − B is positive semi-definite. The Frobenius inner product ⟨A, B⟩ of two matrices A, B ∈ IR^{m×n} is

⟨A, B⟩ = tr(AB^{T}) = ∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}b_{ij}.

For any nonsingular matrices E ∈ IR^{m×m} and F ∈ IR^{n×n},

⟨A, B⟩ = ⟨E^{−1}A, E^{T} B⟩ = ⟨AF^{−1}, BF^{T} ⟩.

For more properties of Frobenius inner products of matrices see [6], [19], [21] and [22]. Let δ_{ii} = 1 and δ_{ij} = 0 if i ≠ j. Let A = (a_{ij}) ∈ IR^{m×n} and let p = min{m, n}. The trace of A is

tr(A) = ∑_{i=1}^{p} a_{ii}.

Define the absolute trace of A by

atr(A) = ∑_{i=1}^{p} |a_{ii}|,

the absolute sum of A by

asum(A) = ∑_{i=1}^{m} ∑_{j=1}^{n} |a_{ij}|,

and the maximum row-column norm of A by

maxn(A) = max{ max_{1≤i≤m} ||a_{i.}||, max_{1≤j≤n} ||a_{.j}||}.

Let the singular values of A ∈ IR^{m×n} be σ_{i} ≡ σ_{i}(A) for i = 1, …, p, where σ_{1} ≥ σ_{2} ≥ … ≥ σ_{p} ≥ 0. By the singular value decomposition [10] or [14] there exist U ∈ O_{m} and V ∈ O_{n} such that

U^{T} AV = Σ = diag(σ_{1}, …, σ_{p}),  (1.1)

where Σ ∈ IR^{m×n}. Note that for any X ∈ O_{m} and Y ∈ O_{n} the matrices A, XA, AY and XAY all have the same singular values. Let κ ∈ {1, …, p}. The sum of the κ largest singular values is a function mapping IR^{m×n} to IR defined by

f_{κ}(A) = ∑_{i=1}^{κ} σ_{i}(A).

Particular functions of interest are the largest singular value

f_{1}(A) = σ_{1}(A),

the sum of all the singular values

f_{p}(A) = ∑_{i=1}^{p} σ_{i}(A),

and the smallest singular value

σ_{p}(A) = ∑_{i=1}^{p} σ_{i}(A) − ∑_{i=1}^{p−1} σ_{i}(A).

2. Bounds on the singular values

In [25] Qi gave a lower bound for f_{1}(A) as follows:

Proposition 2.1. f_{1}(A) ≥ maxn(A).

Corollary 2.2. For any i and j, |a_{ij}| ≤ f_{1}(A). If for some i and j, |a_{ij}| = f_{1}(A), then all the other elements of A in the ith row and the jth column are zero.

We now establish a lower bound and an upper bound for the sum of all the singular values of A. Consideration of a square diagonal matrix shows that these bounds can be achieved.

Theorem 2.3. atr(A) ≤ f_{p}(A) ≤ asum(A). Moreover if atr(A) = f_{p}(A) then

(a) a_{rs} = 0 if r > p or s > p;

(b) |a_{rs}| = |a_{sr}|, |a_{rr}a_{ss}| ≥ a_{rs}^{2} and a_{rr}a_{ss}a_{rs}a_{sr} ≥ 0 if r, s ≤ p.

Proof. By the singular value decomposition A = UΣV^{T},

a_{ii} = ∑_{j=1}^{p} u_{ij}σ_{j}(A)v_{ij},

L. Qi, R. S. Womersley / On extreme singular values of matrix valued functions 157

where U = (u_{ij}) and V = (v_{ij}). Hence,

atr(A) = ∑_{i=1}^{p} |∑_{j=1}^{p} u_{ij}σ_{j}(A)v_{ij}|

≤ ∑_{j=1}^{p} σ_{j}(A) ∑_{i=1}^{p} |u_{ij}v_{ij}|

≤ ∑_{j=1}^{p} σ_{j}(A)||u_{.j}|| ||v_{.j}||

= ∑_{j=1}^{p} σ_{j}(A) ≡ σ(A).

On the other hand, Σ = U^{T} AV, so

σ_{i}(A) = ∑_{j=1}^{m} ∑_{k=1}^{n} u_{ji}a_{jk}v_{ki}.

Hence,

σ_{(}A) = ∑_{i=1}^{p} ∑_{j=1}^{m} ∑_{k=1}^{n} u_{ji}a_{jk}v_{ki}

≤ ∑_{j=1}^{m} ∑_{k=1}^{n} |a_{jk}| ∑_{i=1}^{p} |u_{ji}v_{ki}|

≤ ∑_{j=1}^{m} ∑_{k=1}^{n} |a_{jk}| ||u_{j.}|| ||v_{k.}||

= ∑_{j=1}^{m} ∑_{k=1}^{n} |a_{jk}| ≡ asum(A).

Suppose now that f_{p}(A) = atr(A). To establish (a) assume that m ≥ r > n ≥ s and that a_{rs} ≠ 0. Let

B = P A,

where P = (p_{ij}) ∈ O_{m}, p_{ij} = δ_{ij} except

p_{rr} = p_{ss} = \frac{a_{ss}}{\sqrt{a_{rs}^{2} + a_{ss}^{2}}} , p_{sr} = −p_{rs} = \frac{a_{rs}}{\sqrt{a_{rs}^{2} + a_{ss}^{2}}} .

Then B = P A has the same singular values as A,

b_{ii} = a_{ii} for i ≠ s,  (2.2)

and

b_{ss}^{2} = a_{ss}^{2} + a_{rs}^{2}.  (2.3)

However,

atr(A) = f_{p}(A) = f_{p}(B) ≥ atr(B).  (2.4)

Comparing (2.2), (2.3) and (2.4) we have a contradiction, so a_{rs} = 0. A similar argument holds for s > p. To establish (b) assume that r, s ≤ p. Let

B = P AQ,

where P = (p_{ij}) ∈ O_{m}, p_{ij} = δ_{ij} except

p_{rr} = p_{ss} = cos θ_{1}, p_{sr} = −p_{rs} = sin θ_{1},

tan 2θ_{1} = \frac{2(a_{rr}a_{sr} + a_{rs}a_{ss})}{a_{sr}^{2} + a_{ss}^{2} − a_{rr}^{2} − a_{rs}^{2}} , −\frac{π}{4} ≤ θ_{1} ≤ \frac{π}{4} ,

and Q = (q_{ij}) ∈ O_{n}, q_{ij} = δ_{ij} except

q_{rr} = q_{ss} = cos θ_{2}, q_{sr} = −q_{rs} = sin θ_{2},

tan 2θ_{2} = \frac{2(a_{rr}a_{rs} + a_{sr}a_{ss})}{a_{sr}^{2} + a_{rr}^{2} − a_{ss}^{2} − a_{rs}^{2}} , −\frac{π}{4} ≤ θ_{2} ≤ \frac{π}{4} .

It can be verified that A and B have the same singular values, and

b_{ii} = a_{ii}  (2.5)

for i ≠ r, s,

b_{rr}b_{ss} = a_{rr}a_{ss} − a_{rs}a_{sr},  (2.6)

and

b_{rr}^{2} + b_{ss}^{2} = a_{rr}^{2} + a_{sr}^{2} + a_{ss}^{2} + a_{rs}^{2}.  (2.7)

By (2.6) and (2.7), we have

(|b_{rr}| + |b_{ss}|)^{2} − (|a_{rr}| + |a_{ss}|)^{2}
= (|a_{rs}| − |a_{sr}|)^{2} + 2(|a_{rr}a_{ss} − a_{rs}a_{sr}| + |a_{rs}a_{sr}| − |a_{rr}a_{ss}|) ≥ 0.  (2.8)

However, (2.4) still holds in this case. By (2.4) and (2.5), the left hand side of (2.8) is also 0. The conclusions of (b) follow easily.

Corollary 2.4. f_{p}(A) = |tr(A)| if and only if

(a) a_{rs} = 0 for all r > p and s > p, and

(b) A[1, …, p] ∈ S_{p} and either A[1, …, p] ≥ 0 or A[1, …, p] ≤ 0.

Proof. Suppose that |tr(A)| = f_{p}(A). As |tr(A)| ≤ atr(A) ≤ f_{p}(A) we have |tr(A)| = atr(A) = f_{p}(A), so part (a) follows directly from Theorem 2.3. Also |tr(A)| = atr(A) if and only if either a_{ii} ≥ 0 for i = 1, …, p or a_{ii} ≤ 0 for i = 1, …, p. Hence by (b) of Theorem 2.3 we see that A[1, …, p] is symmetric. Now for a symmetric matrix tr(B) is the sum of the eigenvalues of B, while f_{p}(B) is the sum of the absolute values of the eigenvalues of B. Thus, all the eigenvalues of A[1, …, p] are either nonnegative, so A[1, …, p] is positive semi-definite, or nonpositive, so A[1, …, p] is negative semi-definite. The reverse argument follows by noting that if a symmetric matrix B is positive semidefinite then its diagonal elements are non-negative and tr(B) = atr(B) = f_{p}(B). Similarly if B is negative semi-definite then its diagonal elements are non-positive and −tr(B) = atr(B) = f_{p}(B).

3. A max characterization

An key step is a max characterization of the sum of the largest singular values of a matrix. Let

Φ_{κ} = {B ∈ IR^{m×n} : f_{1}(B) ≤ 1, f_{p}(B) = κ}.

Then Φ_{κ} is compact. By Corollary 2.2, we have:

Proposition 3.1. For any A = (a_{ij}) ∈ Φ_{κ} and any i and j, |a_{ij}| ≤ 1. If for some i and j, |a_{ij}| = 1, then all the other elements of A in the ith row and the jth column are zero.

Theorem 3.2. For any κ ∈ {1, …, p}

f_{κ}(A) = max{⟨A, B⟩ : B ∈ Φ_{κ}}.

Proof. We have A = UΣV^{T}. Therefore,

max{⟨A, B⟩ : B ∈ Φ_{κ}} = max{⟨UΣV^{T} , B⟩ : B ∈ Φ_{κ}}
= max{⟨Σ, U^{T} BV ⟩ : B ∈ Φ_{κ}} = max{⟨Σ, G⟩ : G ∈ Φ_{κ}},

where the last equality holds because Φ_{κ} is invariant under orthogonal transformations (i.e. B ∈ Φ_{κ} ⟺ G = U^{T} BV ∈ Φ_{κ} where U ∈ O_{m} and V ∈ O_{n}). However,

⟨Σ, G⟩ = ∑_{i=1}^{p} σ_{i}(A)g_{ii}

where G = (g_{ij}). By Theorem 2.3 and Proposition 3.1, |g_{ii}| ≤ 1 and ∑_{i=1}^{p} |g_{ii}| = atr(G) ≤ f_{p}(G) = κ. Therefore, for any G ∈ Φ_{κ},

⟨Σ, G⟩ ≤ f_{κ}(A).

However, letting G = diag(g_{ii}), where g_{ii} = 1 for i = 1, …, κ, and g_{ii} = 0 otherwise, we have G ∈ Φ_{κ} and

⟨Σ, G⟩ = f_{κ}(A).

This proves the theorem.

Corollary 3.3. For any κ ∈ {1, …, p} the function f_{κ}(A) is convex.

Proof. The function f_{κ}(A) is the maximum of linear functions of A, so is convex [26].

We now characterize the matrices B ∈ Φ_{κ}, which achieve the maximum.

Theorem 3.4. Suppose that the singular values of A are

σ_{1} ≥ … ≥ σ_{r} > σ_{r+1} = … = σ_{κ} = … = σ_{r+t} > σ_{r+t+1} ≥ … ≥ σ_{p}.

Then matrices B ∈ Φ_{κ} achieve the maximum in Theorem 3.2 if and only if B = UGV^{T}, where G ∈ IR^{m×n} satisfies G_{ij} = 0 except

(i) g_{ii} = 1 for i = 1, …, r, (ii) 0 ≤ g_{ii} ≤ 1 for i = r + 1, …, r + t and ∑_{i=r+1}^{r+t} g_{ii} = κ − r, (iii) g_{ii} = 0 for i = r + t + 1, …, p, (iv) G[r + 1, …, r + t] is symmetric, positive semi-definite and ρ(G[r + 1, …, r + t]) ≤ 1.

Proof. Let G = U^{T} BV. Then,

max{⟨A, B⟩ : B ∈ Φ_{κ}} = max{⟨Σ, G⟩ : G ∈ Φ_{κ}}.

It is easy to verify that matrices G, described in the theorem, achieve the maximum and are in Φ_{κ}. The if part of the theorem is thus proved. Furthermore, according to the proof of Theorem 3.2, if G achieves the maximum, its diagonal elements must satisfy the claims of the theorem. Then f_{p}(G) = atr(G). By Corollary 2.2 and Theorem 2.3 (a)(b), all the off-diagonal elements of G not in G(r + 1, …, r + t) are zeroes. By Theorem 2.3 (c), we get the conclusions on G[r + 1, …, r + t]. This proves the only if part of the theorem.

Denote the set of B in Theorem 3.4 as F_{κ}(A). It is convex and closed. Let U_{1} ∈ O_{m,r} and V_{1} ∈ O_{n,r} consist of the first r columns of U and V respectively. Let U_{2} ∈ O_{m,t} and V_{2} ∈ O_{n,t} consist of the next t columns of U and V respectively. Let G_{2} = G(r + 1, …, r + t). Then

F_{κ}(A) = {B = U_{1}V_{1}^{T} + U_{2}G_{2}V_{2}^{T} ∈ IR^{m×n} : G_{2} ∈ S_{t}, 0 ≤ G_{2} ≤ I_{t}, tr(G_{2}) = κ − r}.

As a referee commented, Theorem 3.2 and 3.4 are along the same lines as Ky Fan’s variational formulation. According to Theorems 3.2 and 3.4, and convex analysis [26],

Corollary 3.5. The subdifferential of f_{κ} at A is

∂f_{κ}(A) = F_{κ}(A).

Whenever σ_{κ}(A) > σ_{κ+1}(A), i.e., κ = r + t, the function f_{κ} is differentiable at A and

f′_{κ}(A) = U_{1}V_{1}^{T} + U_{2}V_{2}^{T} .

4. Matrix-Valued Functions

Suppose now that A is a matrix-valued function mapping IR^{s} to IR^{m×n}. Let g_{κ} be defined by

g_{κ}(x) = f_{κ}(A(x)).

Then g_{κ} is a composite function. If A is a smooth function, then the max characterization of f_{κ} in Theorem 3.2 shows that g_{κ}(x) is a convex composition of smooth functions, so it is a regular locally Lipschitz function. Thus the Clarke subdifferential [2] is appropriate to describe the subdifferential properties of g_{κ}. When we are dealing with matrix-valued functions which are not smooth or composite functions which cannot be expressed as a convex composition the Clarke subdifferential can be too large. Also the matrix valued function may be defined on an infinite dimensional space. A general framework can be developed when A is a (Gâteaux) Gdifferentiable function. Then we use the Michel-Penot subdifferential [17], [18] to describe the subdifferential properties of g_{κ}. The Michel-Penot subdifferential coincides with the G-derivative whenever the later exists, and is contained in the Clarke subdifferential. Suppose that X is a Banach space, Y is an open subset of X, and ϕ is a locally Lipschitzian function defined on Y. Let x be a point in Y and y be a vector in X. The Michel-Penot directional derivative of ϕ at x in the direction y is

ϕ^{•}(x; y) := sup_{z∈X}{lim sup_{t↓0}[ϕ(x + ty + tz) − ϕ(x + tz)]/t}.

The Michel-Penot subdifferential of ϕ at x is the set

∂^{•}ϕ(x) := {u ∈ X^{∗} : ⟨u, y⟩ ≤ ϕ^{•}(x; y), ∀y ∈ X},

which is a nonempty, convex and weak*-compact set for each x. We have

ϕ^{•}(x; y) ≤ ϕ^{∘}(x; y),  (4.1)

where ϕ^{∘}(x; y) is the Clarke directional derivative of ϕ at x in the direction y, and

∂^{•}ϕ(x) ⊆ ∂^{∘}ϕ(x),  (4.2)

where ∂^{∘}ϕ(x) is the Clarke subdifferential of ϕ at x. We also have

ϕ′(x; y) ≤ ϕ^{•}(x; y)  (4.3)

if the usual directional derivative ϕ′(x; y) exists, and ∂^{•}ϕ(x) is a singleton,

∂^{•}ϕ(x) = {ϕ′(x)},  (4.4)

if and only if the G-derivative of ϕ at x exists. Equation (4.4) is not true in general for the Clarke subdifferential. When (4.1) is satisfied as an equality for all y at x, we say that ϕ is normal at x. When the usual directional derivatives exists and (4.3) is satisfied as an equality for all y at x, we say that ϕ is semiregular at x. Function ϕ is regular at x if and only if it is both normal and semiregular at x. Especially, ϕ is semiregular at x if it is G-differentiable at x. If ϕ is semiregular at x and ∂^{•}ϕ(x) is known, we may calculate its directional derivatives at x by

ϕ(x; y) = ϕ^{•}(x; y) = max{⟨u, y⟩ : u ∈ ∂^{•}ϕ(x)},

which are useful in minimizing or maximizing ϕ. The following theorem is proved in [1].

Proposition 4.1. Let X, Y and x be as above. Suppose that ϕ = ψ ∘ η is a composite function, where η : Y ⟶ IR^{n} is locally Lipschitzian and G-differentiable at x, and ψ is locally Lipschitzian and regular at η(x). Then ϕ is locally Lipschitzian and semiregular at x, and

∂^{•}ϕ(x) = {∑_{i=1}^{n} v_{i}η_{i}(x) : v_{i} ∈ ∂^{∘}ψ(η(x))}.

For more general form of Theorem 4.1, see [1]. Returning to our singular value functions, by Corollaries 3.3, 3.5, and Theorem 4.1, we have

Theorem 4.2. Let A be a matrix-valued function mapping IR^{s} to IR^{m×n}, and let

g_{κ}(x) = f_{κ}(A(x)) ≡ ∑_{1}^{p} σ_{i}(A(x)).

If A is locally Lipschitzian and G-differentiable at x ∈ IR^{s}, then g_{κ} is locally Lipschitzian and semiregular at x,

∂^{•}g_{κ}(x) = {u ∈ IR^{s} : u_{k} = tr(U_{1}^{T} A_{k}(x)V_{1}) + ⟨U_{2}^{T} A_{k}(x)V_{2}, G_{2}⟩, G_{2} ∈ Ψ_{t}},
Ψ_{t} = {G_{2} ∈ S_{t} : 0 ≤ G_{2} ≤ I_{t}, tr(G_{2}) = κ − r},

where U_{1}, U_{2}, V_{1}, V_{2}, r and t have the same meanings as in Section 2 with A = A(x), and

A_{k}(x) = \frac{∂}{∂x_{k}} A(x).

If furthermore κ = r + t, then g_{κ} is G-differentiable at x, and

\frac{∂}{∂x_{k}} g_{κ}(x) = ⟨U_{1}^{T} A_{k}(x)V_{1}, I_{r}⟩ + ⟨U_{2}^{T} A_{k}(x)V_{2}, I_{t}⟩.

If A is smooth at x, then g_{κ} is regular at x.

Again, the necessary condition for x to be a minimizer of g_{κ} is

0 ∈ ∂^{•}g(x).  (4.5)

If A is affine, then g_{κ} is convex, and thus (3.5) is also sufficient. Proposition 2.8.8 of Clarke [2], Hiriart-Urruty and Ye [13] and Overton and Womersley [21] discuss extremal eigenvalue functions of smooth symmetric matrix-valued functions. Their results can also be generalized to G-differentiable matrix-valued functions. Notice the spectral radius of a symmetric matrix is its largest singular value. So our results also cover the spectral radius of symmetric matrix-valued functions.

5. The Smallest Singular Value

Another interesting function is the smallest singular value function μ. Let our notation be the same as in Section 2. Then μ is a function mapping IR^{m×n} to R, defined by

μ(A) = σ_{p}(A).

Theorem 5.1. The smallest singular value μ is the difference of a smooth convex function and a convex function. Thus, −μ is a regular function. Suppose that the singular values of A are σ_{1} ≥ … ≥ σ_{r} > σ_{r+1} = … = σ_{p}. Let t = p − r. Let U_{3} ∈ O_{m,t} and V_{3} ∈ O_{n,t} consist of the last t columns of U and V respectively. Then

∂^{∘}μ(A) = {U_{3}G_{3}V_{3}^{T} : G_{3} ∈ S_{t}, 0 ≤ G_{3} ≤ I_{t}, tr(G_{3}) = 1}.  (5.1)

When the smallest singular value of A has multiplicity 1, μ is differentiable at A, and

μ(A) = uv^{T} ,  (5.2)

where u and v are the unit left and right singular vectors corresponding to σ_{p}(A).

Proof. In fact,

μ = f_{p} − f_{p−1}.

By Corollary 3.3, both f_{p} and f_{p−1} are convex functions. By Corollary 3.5, f_{p} is differentiable and

f′_{p}(A) = UV^{T} .

Since eigenvectors of AA^{T} are continuous, U and V are continuous functions of A. Therefore, f_{p} is smooth. Therefore, −μ = f_{p−1} + f_{p} is the sum of two regular functions, thus also a regular function. Furthermore, by Corollary 2.8,

∂f_{p−1}(A) = {UGV^{T} : G ∈ IR^{m×n}, as described in Theorem 2.7}.

But

∂^{∘}μ(A) = f′_{p}(A) − ∂f_{p−1}(A).

A little calculation leads to (5.1). When σ_{p}(A) is simple, the right side of (5.1) is singlevalued. The last conclusion thus follows.

Remark 5.2. Function μ is neither a convex function nor a concave function. Let A, B, C ∈ IR^{2×2}, and A = (B + C)/2. Let B = I_{2} = −C. Then A = 0. We have

μ(A) = 0 < (μ(B) + μ(C))/2 = (1 + 1)/2 = 1.

Let B = diag(2, 0) and C = diag(0, 2). Then A = I_{2}. We have

μ(A) = 1 > (μ(B) + μ(C))/2 = (0 + 0)/2 = 0.

When A is symmetric and nonsingular,

ρ(A^{−1}) = 1/μ(A).

Thus, by Proposition 2.3.14 of [2],

Corollary 5.3. Let ζ : IR^{m×n} ⟶ IR, be defined by

ζ(A) = ρ(A^{−1}).

If A is symmetric and nonsingular, then ζ is regular at A, and

∂^{∘}ζ(A) = \{\frac{−U_{3}G_{3}V_{3}^{T}}{[μ(A)]^{2}} : G_{3} ∈ S_{t}, 0 ≤ G_{3} ≤ I_{t}, tr(G_{3}) = 1\}.

If furthermore the smallest singular value of A is simple, then ζ is differentiable at A, and

ζ(A) = −\frac{uv^{T}}{[μ(A)]^{2}} ,

where u and v have the same meanings as in Theorem 5.1.

Let m = n and h(A) be the condition number of A. By Corollary 2.8, Theorem 4.1 and Proposition 2.3.14 of [2],

Corollary 5.4. If A is nonsingular, then h is regular at A, and

∂^{∘}h(A) = \{\frac{μ(A)U_{1}G_{1}V_{1}^{T} − f_{1}(A)U_{3}G_{3}V_{3}^{T}}{[μ(A)]^{2}}

: G_{1} ∈ S_{q}, G_{3} ∈ S_{t}, 0 ≤ G_{1} ≤ I_{q}, 0 ≤ G_{3} ≤ I_{t}, tr(G_{1}) = tr(G_{3}) = 1},

where q is the multiplicity of the largest singular value of A, U_{1} ∈ O_{m,q} and V_{1} ∈ O_{n,q} consist of the first q columns of U and V respectively. If furthermore q = t = 1, then h is differentiable at A, and

h(A) = \frac{μ(A)ūv̄^{T} − f_{1}(A)uv^{T}}{[μ(A)]^{2}} ,

where ū, v̄, u and v are the left and right singular vectors corresponding to the largest and the smallest singular values of A respectively.

We may derive theorems for the smallest singular value and the condition number of a matrix-valued function, similar to Theorem 3.2, by Theorems 3.1, 5.1 and Corollary 5.4. This has also been discussed in [13]. One may discuss minimizing these extremal singular value functions of a matrix-valued function as done in [3], [10], [12], [13], [19], [20], [22], [33] do for the extremal eigenvalue functions of a smooth symmetric matrix-valued function. We do not go to the detail of these.

References

[1] J. R. Birge, L. Qi: Semiregularity and generalized subdifferentials with applications to optimization, Mathematics of Operations Research 18 (1993) 982–1005.

[2] F. H. Clarke: Optimization and Nonsmooth Analysis, John Wiley, New York, 1983.

[3] J. Cullum, W.E. Donath and P. Wolfe: The minimization of certain nondifferetiable sums of eigenvalues of symmetric matrices”, Mathematical Programming Study 3 (1975) 35–55.

[4] J. C. Doyle: Robustness of multiloop linear feedback systems, Proceedings of the 17th IEEE Conference on Decision and Control (1979) 12–18.

L. Qi, R. S. Womersley / On extreme singular values of matrix valued functions 165

[5] J. C. Doyle: Analysis of feedback systems with structured uncertainties, Proceedings IEEE 129, D (1982) 242–250.

[6] J. C. Doyle, J. E. Wall and G.Stein: Performance and robustness analysis for structured uncertainty, Proceedings 21st IEEE Conference on Decision and Control Orlando, Florida (1982) 629–636.

[7] R. Fletcher: Semi-definite matrix constraints in optimization, SIAM Journal on Control and Optimization 23 (1985) 493–513.

[8] R. Fletcher: Practical Methods of Optimization, 2nd Edition, John Wiley, Chichester and New York, 1987.

[9] B. Gollan: Eigenvalue perturbation and nonlinear parametric optimization, Mathematical Programming Study 30 (1987) 67–81.

[10] G. H. Golub and C. F. Van Loan: Matrix Computations, North Oxford, Oxford, 1983.

[11] J.-B. Hiriart-Urruty: Generalized differentiability, duality and optimization for problems dealing with differences of convex functions, Convexity and Duality in Optimization, Lecture Notes in Economics and Mathematical Systems 256 (J. Ponstein ed.), Springer-Verlag, Berlin, 1986.

[12] J.-B. Hiriart-Urruty, A. Seeger and D. Ye: Sensitivity analysis for a class of convex functions defined by a space of symmetric matrices, Proceedings of the 6th French-German Conference on Optimization, 1991.

[13] J.-B. Hiriart-Urruty and D. Ye: Sensitivity analysis of all eigenvalues of a symmetric matrix, Numerische Mathematik 70 (1995) 45–72.

[14] R. A. Horn and C. R. Johnson: Matrix Analysis, Cambridge University Press, Cambridge, 1985.

[15] V. C. Klema and A. J. Laub: The singular value decomposition: Its computation and some applications, IEEE Transactions on Automatic Control AC-25 (1980) 164–176.

[16] A .W. Marshall and I. Olkin: Inequalities: Theory of Majorization and its Applications, Academic Press, London, 1979.

[17] P. Michel and J.-P. Penot: Calcul sous-differentiel pour des fonctions lipschitziennes et non lipschitziennes, C. R. Acad. Sc. Paris. 298 (1984) 269–272.

[18] P. Michel and J.-P. Penot: A generalized derivative for calm and stable functions, Differential and Integral Equations 5 (1992) 433–454.

[19] M. L. Overton: On minimizing the maximum eigenvalue of a symmetric matrix, SIAM Journal on Matrix Analysis and Application 9 (1988) 256–268.

[20] M. L. Overton: Large-scale optimization of eigenvalues, SIAM Journal on Optimization 2 (1992) 88–120.

[21] M. L. Overton and R. S. Womersley: On minimizing the spectral radius of a nonsymmetric matrix: Optimality conditions and duality theory, SIAM Journal on Matrix Analysis and Application 9 (1988) 473–498.

[22] M. L. Overton and R. S. Womersley: Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Mathematical Programming 62 (1993) 321–357.

[23] E. Polak and Y. Wardi: Nondifferentiable optimization algorithm for designing control systems having singular value inequalities, Automatica 18( 1982) 267–283.

166 L. Qi, R. S. Womersley / On extreme singular values of matrix valued functions

[24] E. Polak, D. Q. Mayne and Y. Wardi: On the extension of constrained optimization algorithms from differentiable to nondifferentiable problems, SIAM Journal on Control and Optimization 21 (1983) 179–203.

[25] L. Qi: Some simple estimates for singular values of a matrix, Linear Algebra and Its Applications 56 (1984) 105–119.

[26] R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, 1970.

[27] N. R. Sandel: Robust stability of systems with applications to singular perturbations, Automatica 15 (1979) 467–470.

[28] A. Seeger: “Sensitivity analysis of nondifferentiable sums of singular values of rectangular matrices”, Technical Report, Departmet de Matematica Aplicada i Analisi, Universitat de Barcelona, 1990.

[29] R. Sezinger and M. Overton: “The largest singular value of x^{X}A_{0}e^{−X} is convex on convex sets of commuting matrices”, IEEE Transactions on Automatics Control 35 (1990) 229–230.

[30] S. Subramani: “On sums of singular values”, MSc Thesis, School of Mathematics, University of New South Wales, Sydney, Australia 1993.

[31] G. A. Watson: Computing the structured singular value, SIAM Journal on Matrix Analysis and Applications 13 (1992) 1054–1066.

[32] R. S. Womersley: Local properties of algorithms for minimizing nonsmooth composite functions, Mathematical Programming 32 (1985) 69–89.

[33] D. Ye: “Analyse de sensibilite pour les valeur propres d^{,}une matrice symetrique et dans le probleme de conception optimale de formes”, Thesis, Univ. Paul Sabatier de Toulouse, France 1992.