radial02_red_1.gif 7.1 Introduction

m×n 행렬 A 에 대해 이  m>n 이면 overdetermined system 으로 보통 해가 존재하지 않고,

m<n 인 underdetermined sytem 은보통 무수히 많은 해갖는다.  그러면 일반적인 해법은?

 Statement of the Linear Least-Squares Problem(LSP)

주어진 m×n 행렬 A와 real 벡터 b에 대하여, 의 값을 최소화 하도록 하는 real  n - 벡터 x를 구하는 것

 만약 LSP가 하나 이상의 해를 가질 경우,  minimum Euclidean norm을 the minimum length solution또는 the minimum norm solution이라고 한다.

bar_green.gif

radial02_red_1.gif 7.2 A Simple Application Leading to an Overdetermined System

 다음 Table은 다섯 마을의 인구 및 상품의 판매수량과 그에 따른 수입을 나타낸 것이다.

 District (i)

Sales (c)

Population (a)

Per Capita income (b)

 1

 162

 274

 2450

 2

 120

 180

 3254

 3

 223

 375

 3802

 4

 131

 205

 2838

 5

 67

 86

 2347

 만일 회사가 이 Table을 바탕으로 앞으로의 판매량을 예상 하고자 할때 c, a, b의 관계는 다음과 같다.

   

 여기에 위의 data를 넣으면,

                

                

                

                

                 

 가 되고 이것은 형태로 바꿀 수 있다.

bar_green.gif

radial02_red_1.gif 7.3 Existence and Uniqueness

 선형 방정식을 풀 경우, 다음과 같은 사항을 생각해 보자.

   1. 의 least square solution은 항상 존재하는가?

   2. 존재한다면 유일한가?

   3. 그런 해을 어떻게 얻을 수 있는가?

 

radial_purple.gif Theorem 7.3.1 Least-Squares Existence and Uniqueness Theorem (증명 P. 318)

 Linear least-squares problem의 해는 항상 존재한다. 이 해가 유일하기 위한 필요충분 조건은 행렬 A가 full rank을 가져야 한다. 즉 rank(A) = n. 만약 A의 rank가 deficient면  Linear-squares problem는 무한히 많은 해를 가진다.

Full rank 경우는 여기서 증명하고(유일성은 full rank에서 바로 나온다, 더 나아가  가 positive definite 이다 Exs.), rank deficient 경우는 10장(SVD)에서 다룬다.

radial_purple.gif Lemma 7.3.1  

 x가 Ax=b의 least-squares solution이기 위한 필요충분 조건은 x가 을 만족해야 한다.

   을 normal equation of   이라 한다.

 

bar_green.gif 

radial02_red_1.gif 7.4 Geometric Interpretation of the Least-Squares Problem

 

 A를 m×n크기의 행렬이라 하자 (m>n). 그러면 A는 인 선형 변환이다. 치역 의 부분공간 이고 는 b와 Ax사이의 거리이다. 따라서 이것이 최소거리가 되려면 orthogonal(직교) 이어야 한다. (그림 참조, 증명 BWOC)

 이러한 원리에 의하여, linear system Ax = b의 least squares solution은 항상 존재한다. b - Ax는 R(A)와 수직을 이루고 R(A)는 A의 column 벡터의 일차결합들의 집합이므로 b - Ax는 A의 모든 column과 orthogonal하다. 즉 이라 할 수 있고 이항하면  이 된다.

 

bar_green.gif

radial02_red_1.gif 7.5 Normal Equations and Polynomial Fitting

 

radial_purple.gif Definition 7.5.1

 선형 방정식 의  Normal equations라 한다.

 

radial_purple.gif Example 7.5.1

 일 경우, normal equations는

 

 

  이고 이것을 풀면

   이다.

 

bar_green.gif

radial02_red_1.gif 7.6 Pseudoinverse and the Least-Squares Problem

 

radial_purple.gif Definition 7.6.1

  행렬 라 하자. 여기서 A는 m×n크기의 행렬이고(m>n) rank는 n이다. 이때의 를 행렬 A의  Pseudo-inverse라 부른다.

  참고:   http://matrix.skku.ac.kr/sglee/project/generalized-inverse/Generalized_Inverse.html

 

 Least-Squares Solution Using the Pseudoinverse

 full-rank의 overdetermined least-squares problem Ax = b는 다음과 같은 유일한 least-squares을 갖는다.

      

 

radial_purple.gif Definition 7.6.2

  A는 m×n크기의 full rank을 갖는 행렬이라 하자. 그러면 우리는 condition number

  Cond(A)   로 정의 한다.

 

radial_purple.gif Example 7.6.1

   rank(A) = 2

행렬 A는 full rank을 가지므로

 Cond(A)  

 

bar_green.gif 

radial02_red_1.gif 7.7 Sensitivity of the Least-Squares Problem

 

 Case 1: Perturbation in the Vector b

 여기서는 vector b을 b + δb로 perturbed 한다. 그러나 A는 변화시키지 않는다.

radial_purple.gif Theorem 7.7.1 Least-Squares Right Perturbation Theorem

 x와 y을 각각 perturbed되기 전,후의 유일한 least-squares solutions이라 하자 그러면,

         ( )

wnere : projections of vectot b onto R(A), : projections of δb onto R(A)

 

radial_purple.gif Example 7.7.1

 

  projection of A onto R(A)

      = 예제 5.6.2참조

Cond(A)=2.4495

으로 매우 작다. 여기서 A는 well condition이므로, 우리는  least-squares solution은 많이 perturbed되지 않는 것을 알 수 있다.

 

 Case 2: Perturbaion in the Matrix A

 행렬의 Perturbation을 E가 다음을 만족하며 충분히 작다고 하자.

      rank(A) = rank(A+E)

 을 projection of E onto R(A) 그리고 을 projection of E onto the orthogonal complement of R(A). 만약에 이면 다음 Theorem을 얻을 수 있다.

radial_purple.gif Theorem 7.7.2 Least-Squares left Perturbation Theorem

 x와 y을 각각 Ax = b와 (A + E)y = b 유일한 least-squares solutions이라 하자. 단, rank(A) = rank(A+E)

  ( )

 위의 Theorem에서 만약, 이 0이면 sensitivity는 Cond(A)에 의존한다. 그리고 만약 이면 residual r = b-Ax는 0이다.

radial_purple.gif Example 7.7.3 ~ 4 Two Example with Different Sensitivities

 

(1) Sensitivity Depending Upon the Square of the Condition Number

 

 , , (예제 5.6.3 참조)

 라 하자.

그러면 ,

이 작다고 해도, 으로 크다. 따라서 처음의 해와 perturbed된 해는 큰 차이가 있다. 실제로 계산 결과는

,   이다.

(매우 큼)

 

(2) Sensitivity Depending Upon the Condition Number

 A와 E는 위와 동일하고  라 하자.

 이 경우 이고

  (예제 5.6.3 참조)

 따라서 Theorem 7.7.2에 의해서 Cond(A)의 제곱은 어떤 영향도 미치지 않는다. least-squares solution은 Cond(A)에 의해서 영향을 받는다.

 

우리는 여기서 행렬 A의 perturbation을 줄 경우, least-squares solutions의 sensitivities는 right-hand side의 벡터 b의 값에 따라 변한다는 것을 알 수 있다.

 

bar_green.gif

radial02_red_1.gif 7.8 Computational Methods for Overdetermined Least-Squares Problems

 

 7.8.1 The Normal Equations Method

 

 least-squares solution을 구하기 위해 가장 폭넓게 사용하는 것이  normal equations method 이다. 이방법은 다음과 같은 normal equations의 해를 구하는 것이다.

                       

 여기서 행렬 A는 이고 full rank 갖는다고 하자. 이 경우 는 symmetric이고 positive definite이므로 Cholesky decomposition으로 변형되어 이 된다. 그러므로 least-squares problem을 풀기 위해 다음과 같은 알고리즘을 생각할 수 있다.

radial_purple.gif ALGORITHM 7.8.1 Least-Squares Solution Using Normal Equations

 행렬 A는 이고 rank(A) = n 이라고 하자. Cholesky factorization을 사용하여 normal equations으로부터 least-squares solution을 계산하기 위한 알고리즘은 다음과 같다.

 Step 1:

 Step 2: 의 Cholesky factor H을 계산한다.

 Step 3: 다음의 triangular systems을 푼다.

            

          

 

 

radial_purple.gif Example 7.8.1

      

 

Step 1 :

Step 2 :

Step 3 : 다음의 normal equations을 푼다.

          

                  

 

 least-squares solution을 다시 대입하여 계산하면(첫번째 row의 경우)

(원래의 값 = 162)

 

radial_purple.gif Example 7.8.2

      

 

 rank(A) = 2, rank(A , b) = 3. 따라서 Ax = b는 해를 갖지 않는다. 다음의 least-squares solution을 계산해 보자

 1.

 2. 의 Cholesky factor는

 3. 이 triangular system의 해는

,   

 

,  그리고

 

  7.8.2  QR Factorization Methods for the Full-Rank Problem

 

을 행렬의 QR decomposition이라하자.

그러면    where

따라서 을 최소화 하기 위해서 이 되도록 한다. 이 경우 residual은 로 주어진다.

 Least-Squares Using QR

 1. 로 분해

 2. 이 된다.

 3. 의 upper triangular 식 을 푼다. where

 

radial_purple.gif Example 7.8.4

      

 1. A = QR

    ,  

 2.

 3. 을 풀면,

     으로 해는

     이 되고 residual

 

  Use of Householder Matrices

 

  Use of Givens Rotations

    Givens rotations을 사용하는 것은 Householder matrices보다 더욱 expensive하다.

 

  Use of Gram-Schmidt and Modificed Gram-Schmidt Algorithms

    Gram-Schmidt proces로 행렬 A을 QR분해 할 수 있다. 이 방법은 Householder method보다 약간 더 expensive하다.

radial_purple.gif ALGORITHM 7.8.3 Classical Gram-Schmidt(CGS) for QR Factorization

 rank(A) = n의 이 되도록 하는 orthonormal columns의 행렬 와 upper triangular 행렬 에 대하여 다음과 같은 알고리즘을 생각할 수 있다.

 k = 1, 2, ... , n

   I = 1, 2, ... , k-1

      

      

      

      

   이 알고리즘은 더욱 좋은 성질은 갖도록 modified 할 수 있다. 그러한 다음 알고리즘을 Modified Gram-Schmidt algorithm이라 한다.

 

radial_purple.gif ALGORITHM 7.8.4 Modified Gram-Schmidt(MGS) for QR Factorization

  (k = 1, 2, ... n)

   k = 1, 2, ... n에 대하여

      ,   

       k = k+1, ... , n에 대하여 ,

 이 알고리즘을  row-oriented modified Gram-Schmidt method 라 한다.

   MGS는 orthogonality는 행렬 A의 condition number에 의존한다. 이 방법에 의한 Q의 orthogonality는 A가 ill-conditioned일 경우는 효용성이 없다.

 

  7.8.3 QR Factorization Method for the Rank-Deficient Case

 

 이 절에서는 rank-deficient least-squares problem에 대해서 생각해 볼 것이다. 앞의 Theorem 7.3.1처럼, 이 경우 infinitely many solutions을 갖는다.

 A를 의()행렬이라 하자. rank(A) = r < n일 경우 QR분해의 행렬 R은 rank-deficient이다.

radial_purple.gif ALGORITHM 7.8.6 Least-Squares Solutions for the Rank-Deficient Problem Using QR

 Step 1: column pivoting을 이용한 QR분해 방법으로 행렬 A는

             

 Step 2:

 Step 3: 임의의 을 선택한다.

 Step 4: 의 nonsingualr upper trianglar system

 Step 5: 원래의 x로 되돌린다.

            x = Py,   

 

radial_purple.gif Example 7.8.8

        rank(A) = 1

 

Step 1: AP = QR,

           

 

Step 2 :

Step 3: 으로 택한다.

Step 4: 을 푼다.

            이 된다. 또한 이것의 minimum-norm least-square solution

           

 

7.8.4 Least-Squares Solution Using SVD

radial_purple.gif Example 7.8.10

 ,

  에 의해

 , ,

 ,  

 

bar_green.gif

radial02_red_1.gif 7.9 Underdetermined Systems

 

 A를 의()행렬이라 하자. 그러면 Ax = b는 미지수보다 조건식이 적다. 이러한 식을 underdetermined system이라 한다.

 

radial_purple.gif Theorem 7.9.1

 Ax = b를 underdetermined system이라 하자. 그러면 모든 해 x는 으로 나타낼 수 있다.

 where 을  만족하고  은 A의 null space()이다.

 Full-rank의 underdetermined system은 infinite의 solutions을 갖는다. 이 경우 complete solution은 ,

 An Expression for the Solution Set of Full-Rank Underdertermined System

,     where y is arbitrary

 

7.9.1 The Minimum-Norm Solution of the Full-Rank Underdetermined Problem Using Normal Equations

 

radial_purple.gif Theorem 7.9.2

 A을 , full rank라 하자. 그러면 underdetermined system Ax = b의 minimum-norm solution x는

      

 

 는 A의 pseudoinverse이다.

 

radial_purple.gif ALGORITHM 7.9.1 Minimum-Norm Solution for the Full-Rank Underdetermined Problem Using Normal Equation

 Step 1:

 Step 2:   , minimum norm solution x을 구한다.

 

radial_purple.gif Example 7.9.1

  ,

 

 Step 1: ,     

 Step 2:

 

7.9.2 The QR Approach for the Full-Rank Underdetermined Problem

 

 이 경우 행렬 A는 columns이 rows보다 더 많으므로, 우리는 을 QR분해 한다.

 , 이 된다. 그래서 Ax = b는

   여기서 라 하면 가 되어 다음식을 갖게 된다.

   

 The minimum-norm solution은  일 경우이다. 따라서 The minimum-norm solution은 다음과 같다.

  이를 알고리즘으로 바꾸면 다음과 같다.

radial_purple.gif ALGORITHM 7.9.2 Minimum-Norm Solution for the Full-Rank Underdetermined Problem Using QR

 Step 1: 는 을 QR분해한다

            

 Step 2:

 Step 3: 의 nonsingular lower triangular system을 구한다.

             

Step 4:

 

radial_purple.gif Example 7.9.2

  ,

 

Step 1:  

 ,

 

Step 2:

 ,   

Step 3:

 

Step 4:

 

 

bar_green.gif

radial02_red_1.gif 7.10 Iterative Refinemint

 bar_green.gif

radial02_red_1.gif 7.11 Computation the Variance-Covariance Matrix

 

 선형 방정식의 해를 구하는 과정에서 The variance-covariance 행렬 을 풀어야 할 경우가 많다.

 행렬 A의 QR분해를 생각해 보자:

  그러면

  이고

 의 마지막 column은 이므로 마지막 column 은 다음식을 풀어서 쉽게 얻을 수 있다.

                                                                    (7.11.1) 

 

                                               (7.11.2)

 

                                 (7.11.3)

 

 

radial_purple.gif ALGORITHM 7.11.1 Computing the Variance-Covariance Matrix X

 Step 1: (7.11.1)에 의해 마지막 column  을 계산한다.

 Step 2: (7.11.2)을 이용해 k = n - 1, n - 2, ... , 2, 1에 대하여 을 구한다.

 Step 3: (7.11.3)을 이용해 i = k - 1, ... ,1; k = 2, 3, ... , n에 대한 을 구한다.

 

radial_purple.gif Example 7.11.1

   

 

A = QR은

,   이 된다.

마지막 column은

         (7.11.1을 사용)

                   (7.11.2을 사용)

 (7.11.3을 사용) 그러면

  Copyrights © 2003.
Made by sglee@math.skku.ac.kr, 이상구교수 with 김덕선-백명국조교
All rights reserved by
The Matrix Lab. 031-290-7025, SKKU, Suwon, Korea