Singular ValuesNorm computations through singular values6.241 Dynamic Systems and Control Lecture 4: Singular Values Readings: DDV, Chapter 4 Emilio Frazzoli Aeronautics and Astronautics Massachusetts Institute of Technology February 14, 2011 E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 1 / 9Outline 1 2 Singular Values Norm computations through singular values E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 2 / 9Unitary Matrices A square matrix U ∈ Cn×n is unitary if U�U = UU� = I . A square matrix U ∈ Rn×n is orthogonal if UT U = UUT = I . Properties: If U is a unitary matrix, then �Ux �2 = �x �2, for all x ∈ Cn . If S = S� is a Hermitian matrix, then there exists a unitary matrix U such that U�SU is a diagonal matrix. 1 For any matrix A ∈ Rm×n, both A�A ∈ Rn×n , AA� ∈ Rm×m are Hermitian ⇒can be diagonalized by unitary matrices. For any matrix A, the eigenvalues of A�A and AA� are always real 2 and non-negative 3 (in other words, A�A and AA� are positive definite). 1S = S� ⇔ �Sx, y� = �x, Sy �. Let v1 be an eigenvector of S, and let M1= R(v1)⊥. If u ∈ M1, then so is Su: �Su, v1� = �u, Sv1� = �u, λ1v1� = 0. All other eigenvectors must b e in M1. Finite induction gets the result. 2Assuming �v1, v1� = 1, λ1= �Sv1, v1� = �v1, Sv1� = �Sv1, v1�� = λ�1 30 < �Av1, Av1� = v�A�Av1= λ1v1�v1.1E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 3 / 9Singular Value Decomposition Theorem (SVD) Any matrix A ∈ Cm×n can be decomposed as A = UΣV , where U ∈ Cm×m and V ∈ Cn×n are unitary matrices. The matrix Σ ∈ Rm×n is “diagonal,” with non-negative elements on the main diagonal. The non-zero elements of Σ are called the singular values of A, and satisfy σi = √i-th eigenvalue of A�A. Proof (assuming rank(A) = m): Since AA� is Hermitian, there exist a diagonal matrix Λ = diag(λ1, λ2, . . . , λm) > 0 such that UΛU� = AA�. Write Λ = Σ2 = diag(σ2, σ2, . . . , σ2 ) 1 1 2 mDefine V1� := Σ−1U�A ∈ Rm×n . Clearly, V1�V1 = Σ−1U�AA�UΣ−1 = I m×m .1 1 1 Construct V = [V1, V2] ∈ Cn×n by choosing the columns in V2 so that V is unitary, and Σ = [Σ1, 0] ∈ Rn×n, by padding with zeroes. Hence, ΣV � = Σ1V1� + 0V2� = U�A, i.e., A = UΣV �. E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 4 / 9� � � � � � Singular Vectors If U and V are written as sequences of column vectors, i.e., U = u1, u2, . . . , um and V = v1, v2, . . . , vn , then rA = UΣV � = σi ui vi� i=1 The columns of U are called the left singular vectors, and the columns of V are called the right singular vectors. Note: Ax can be written as the weighted sum of the left singular vectors, where the weights are given by the projections of x onto the right singular vectors: rAx = σi ui (vi�x), i=1 The range of A is given by the span of the first r vectors in U The rank of A is given by r ; The nullspace of A is given the span of the last (n − r) vectors in V . E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 5 / 9Outline 1 2 Singular Values Norm computations through singular values E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 6 / 9Induced 2-norm computation Theorem (Induced 2-norm) �A�2 = sup x�=0 �Ax�2 �x�2 = σmax(A). Proof: �Ax�2 �UΣV �x�2 �ΣV �x�2 sup = sup = sup = x=0 x=0 x=0��x�2 ��x�2 ��x�2 ���1/2 sup �Σy�2 = sup �Σy�2 = sup ��in =1 σi 2|yi |�21/2 ≤ σmax(A). y=0��Vy�2 y=0��y�2 y =0�ni=1 |yi |2 Assuming σmax = σ1, the supremum is attained for y = (1, 0, . . . , 0). This corresponds to x = v1, and Av1 = σu1 E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 7 / 9Minimal amplification Theorem Given A ∈ Cm×n, with rank(A) = n, inf x�=0 �Ax�2 �x�2 = σn(A). Proof: inf x�=0 �Ax�2 �x�2 = inf x�=0 �UΣV �x�2 �x�2 = inf x�=0 �ΣV �x�2 �x�2 = �Σy�2 �Σy�2 ��in =1 σi 2 yi 2 �1/2 inf = inf = inf ��| |�1/2 ≥ σmin(A). y=0��Vy�2 y =0��y�2 y=0�ni=1 |yi |2 Assuming σmin = σn, the supremum is attained for y = (0, . . . , 0, 1). This corresponds to x = vn, and Avn = σun E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 8 / 9Frobenius norm computation Theorem �A�F = � r� i=1 σi (A)2 �1/2 Proof: �A�F = ⎛ ⎝ n� m� |aij |2 ⎞ ⎠ 1/2 = (Trace(A�A))1/2 = (Trace(V Σ�U�UΣV �))1/2 = j=1 i=1 � �1/2r� �1/2 � �1/2 � Trace(V �V Σ2) = Trace(Σ2) = σi 2 i=1 E. Frazzoli (MIT) Lecture 4: Singular Values Feb 14, 2011 9 / 9MIT OpenCourseWare http://ocw.mit.edu 6.241J / 16.338J Dynamic Systems and Control Spring 2011 For information about citing these materials or our Terms of Use, visit: