Matrix decomposition
선형 대수(linear algebra)에서, 행렬 분해(matrix decomposition) 또는 행렬 인수분해(matrix factorization)는 행렬(matrix)을 행렬의 곱으로의 인수분해(factorization)입니다. 많은 다른 행렬 분해가 있습니다; 각각은 특정 종류의 문제 중에서 용도를 찾습니다.
Example
수치 해석(numerical analysis)에서, 다양한 분해가 효율적인 행렬 알고리듬(algorithms)을 구현하기 위해 사용됩니다.
예를 들어, 선형 방정식의 시스템 을 풀 때, 행렬 A는 LU 분해를 통해 분해될 수 있습니다. LU 분해는 행렬을 아래쪽 삼각 행렬(lower triangular matrix) L과 위쪽 삼각 행렬(upper triangular matrix) U로 인수화합니다. 시스템 와 는 원래 시스템 와 비교하여 더 적은 수의 덧셈과 곱셈을 필요로 하지만, 부동 점(floating point)과 같은 부정확한 산술에서는 훨씬 더 많은 자릿수가 필요할 수 있습니다.
유사하게, QR 분해는 A를 직교 행렬(orthogonal matrix) Q와 위쪽 삼각 행렬 R을 갖는 QR로 표현합니다. 시스템 Q(Rx) = b는 Rx = QTb = c로 해결되고, 시스템 Rx = c는 '역방향 대입(back substitution)'으로 해결됩니다. 필요한 덧셈과 곱셈의 횟수는 LU 해결기(solver)를 사용할 때보다 약 2배이지만, QR 분해가 수치적으로 안정적이기 때문에 부정확한 산술에서 더 이상 자릿수가 필요하지 않습니다.
LU decomposition
- 전통적으로 적용-가능: 정사각 행렬 A이지만, 직사각 행렬도 적용할 수 있습니다.[1][nb 1]
- 분해: , 여기서 L은 아래쪽 삼각(lower triangular)이고 U는 위쪽 삼각(upper triangular)입니다.
- 관련됨: LDU 분해는 이며, 여기서 L은 대각선 위에 1을 갖는 아래쪽 삼각이고, U는 대각선 위에 1을 갖는 위쪽 삼각이고, D는 대각 행렬(diagonal matrix)입니다.
- 관련됨: LUP 분해는 이며, 여기서 L은 아래쪽 삼각, U는 위쪽 삼각이고, P는 순열 행렬(permutation matrix)입니다.
- 존재: LUP 분해는 임의의 정사각 행렬 A에 대해 존재합니다. P가 항등 행렬(identity matrix)일 때, LUP 분해는 LU 분해로 축소됩니다.
- 참조: LUP 분해와 LU 분해는 n-×-n 선형 방정식의 시스템 을 푸는 데 유용합니다. 이들 분해는 행렬 형식에서 가우스 소거법(Gaussian elimination)의 과정을 요약합니다. 행렬 P는 가우스 소거법의 과정에서 수행되는 임의의 행 교환을 나타냅니다. 만약 가우스 소거법이 임의의 행 교환을 요구 없이 행 사다리꼴 형식(row echelon form)을 생성하면, P = I이므로, LU 분해가 존재합니다.
LU reduction
Block LU decomposition
Rank factorization
- 적용-가능: 랭크 r의 m-×-n 행렬 A
- 분해: , 여기서 C는 m-×-r 전체 열 랭크 행렬이고 F는 r-×-n 전체 행 랭크 행렬입니다.
- 참조: 랭크 인수분해는 A의 무어-펜로즈 유사-역을 계산하기 위해 사용될 수 있으며, 이는 선형 시스템 의 모든 해를 얻기 위해 적용할 수 있습니다.
Cholesky decomposition
- 적용-가능: 정사각, 에르미트, 양수 한정 행렬
- 분해: , 여기서 는 실수 양수 대각 엔트리를 갖는 위쪽 삼각입니다.
- 참조: 행렬 가 에르미트이고 양수 반-한정이면, 그것은 만약 의 대각 엔트리가 영이 되도록 허용되면 형식 의 분해를 가집니다.
- 고유성: 양수 한정 행렬에 대해 숄레스키 분해(Cholesky decomposition)는 고유합니다. 어쨌든, 그것은 양수 반-한정 경우에서 고유하지 않습니다.
- 참조: 만약 가 실수이고 대칭이면, 는 모든 실수 원소를 가집니다.
- 참조: 대안은 LDL 분해이며, 이는 제곱근 추출을 피할 수 있습니다.
QR decomposition
- 적용-가능: 선형적으로 독립 열을갖는 m-×-n 행렬 A
- 분해: , 여기서 는 크기 m-×-m의 유니태리 행렬(unitary matrix)이고, 은 크기 m-×-n의 위쪽 삼각(upper triangular) 행렬입니다.
- 고유성: 일반적으로 그것은 고유하지 않지만, 가 전체 랭크(rank)이면, 양수 대각 원소를 가지는 단일 이 존재합니다. 만약 가 정사각이면, 역시 도 고유합니다.
- 참조: QR 분해는 방정식의 시스템 을 풀기 위한 효율적인 방법을 제공합니다. 가 직교(orthogonal)라는 사실은 가 와 동등하도록 임을 의미하며, 이는 이 삼각(triangular)이기 때문에 매우 풀기 쉽습니다.
RRQR factorization
Interpolative decomposition
Eigendecomposition
- 역시 스펙트럼 분해(spectral decomposition)라고 불립니다.
- 적용-가능: 선형적으로 독립 고유벡터를 갖는 정사각 행렬(square matrix) A (반드시 구별되는 고윳값일 필요는 없음).
- 분해: , 여기서 D는 A의 고윳값(eigenvalues)에서 형성된 대각 행렬(diagonal matrix)이고, V의 열은 A의 대응하는 고유벡터(eigenvectors)입니다.
- 존재: n-×-n 행렬 A는 항상 n (복소수) 고윳값을 가지며, 이는 고윳값 방정식(eigenvalue equation) 를 만족시키는 n-×-n 대각 행렬 D와 비-영 열 V의 해당하는 행렬을 형성하도록 (여러 방법으로) 순서화될 수 있습니다. 가 역-가능인 것과 n개의 고유벡터가 선형적으로 독립(linearly independent)인 것은 필요충분 조건입니다 (즉, 각 고윳값은 대수적 중복도와 같은 기하학적 중복도를 가집니다). 이것이 일어나기 위한 충분 (그러나 필요는 아닌) 조건은 모든 고윳값이 다르다는 것입니다 (이 경우에서 기하학적 중복도와 대수적 중복도는 1과 같습니다).
- 참조: 길이 1을 가지도록 고유벡터를 항상 정규화할 수 있습니다 (고윳값 방정식의 정의를 참조).
- 참조: 모든 각 정규 행렬 A (즉, 인 행렬, 여기서 는 켤레 전치)는 고유분해될 수 있습니다. 정규 행렬 A에 대해 (및 정규 행렬에 대해서만), 고유벡터는 직교정규 ()로 만들 수 있고 고유분해는 로 읽습니다. 특히 모든 유니태리, 에르미트, 또는 반-에르미트 (실수-값의 경우에서, 각각 모든 직교, 대칭, 또는 반-대칭) 행렬은 정규이고 따라서 이 속성을 보유합니다.
- 참조: 임의의 실수 대칭 행렬(symmetric matrix) A에 대해, 고유분해는 항상 존재하고 로 쓸 수 있으며, 여기서 D와 V 둘 다는 실수-값입니다.
- 참조: 고유분해는 선형 보통의 미분 방정식 또는 선형 차이 방정식의 시스템의 해를 이해하는 데 유용합니다. 예를 들어, 초기 조건 에서 시작하는 차이 방정식 는 에 의해 풀리며, 이는 와 동등하며, 여기서 V와 D는 A의 고유벡터와 고윳값에서 형성된 행렬입니다. D는 대각이기 때문에, 그것을 의 거듭제곱으로 올리면, 대각선 위의 각 원소를 t의 거듭제곱으로 올리는 것입니다. 이것은 A가 보통 대각이기 때문에 A를 t의 거듭제곱으로 올리는 것보다 수행하고 이해하기가 훨씬 쉽습니다.
Jordan decomposition
조르당 정규 형식(Jordan normal form)과 조르당-슈발레 분해(Jordan–Chevalley decomposition)
- 적용-가능: 정사각 행렬(square matrix) A
- 참조: 조르당 정규 형식은 반복되는 고윳값이 있고 대각화될 수 없는 경우에 대해 고유분해를 일반화하고, 조르당-슈발레 분해는 기저를 선택 없이 이를 수행합니다.
Schur decomposition
- 적용-가능: 정사각 행렬(square matrix) A
- 분해 (복소수 버전): , 여기서 U는 유니태리 행렬(unitary matrix), 는 U의 켤레 전치(conjugate transpose)이고, T는 대각선을 따라 A의 고윳값(eigenvalues)을 가지는 복소 슈어 형식(Schur form)이라고 하는 위쪽 삼각 행렬(upper triangular)입니다.
- 참조: 만약 A가 정규 행렬(normal matrix)이면, T는 대각이고 슈어 분해는 스펙트럼 분해와 일치합니다.
Real Schur decomposition
- 적용-가능: 정사각 행렬(square matrix) A
- 분해: 이것은 와 가 실수만 포함하는 슈어 분해의 버전입니다. 우리는 항상 라고 쓸 수 있으며, 여기서 V는 실수 직교 행렬(orthogonal matrix)이고, 는 V의 전치(transpose)이고, S는 실수 슈어 형식(Schur form)이라고 하는 블록 위쪽 삼각 행렬(block upper triangular)입니다. S의 대각선에 있는 블록은 크기 1×1 (이 경우에서 그것들은 실수 고윳값을 나타냄) 또는 2×2 (이 경우에서 그것들은 복소 켤레 고윳값 쌍에서 유도됨)입니다.
QZ decomposition
- 역시 다음과 같이 불림: 일반화된 슈어 분해(generalized Schur decomposition)
- 적용-가능: 정사각 행렬(square matrices) A와 B
- 참조: 이 분해에는 복소수와 실수의 두 가지 버전이 있습니다.
- 분해 (복소수 버전): 및 , 여기서 Q와 Z는 유니태리 행렬(unitary matrices), * 위첨자는 켤레 전치(conjugate transpose)를 나타내고, S와 T는 위쪽 삼각(upper triangular) 행렬입니다.
- 참조: 복소수 QZ 분해에서, T의 해당 대각선 원소에 대한 S의 대각선 원소의 비율, 은 일반화된 고윳값 문제(generalized eigenvalue problem) (여기서 는 미지수 스칼라이고 v는 미지수 비-영 벡터임)를 푸는 일반화된 고윳값(eigenvalues)입니다.
- 분해 (실수 버전): 및 , 여기서 A, B, Q, Z, S, 및 T는 실수만 포함하는 행렬입니다. 이 경우에서 Q와 Z는 직교 행렬(orthogonal matrices), T 위첨자는 전치(transposition)를 나타내고, S와 T는 블록 위쪽 삼각(block upper triangular) 행렬입니다. S와 T의 대각선에 있는 블록은 크기 1×1 또는 2×2입니다.
Takagi's factorization
- 적용가능: 정사각, 복소수, 대칭 행렬 A.
- 분해: , 여기서 D는 실수 비-음의 대각 행렬(diagonal matrix)이고, V는 유니태리(unitary)입니다. 는 V의 행렬 전치(matrix transpose)를 나타냅니다.
- 참조: D의 대각 원소는 의 고윳값의 비-음의 제곱근입니다.
- 참조: V는 심지어 A가 실수이더라도 복소수가 될 수 있습니다.
- 참조: 이것은 대신 을 사용하는 고유분해 (위 참조)의 특별한 경우가 아닙니다. 게다가, A가 실수가 아니면, 그것은 에르미트가 아니고 를 사용하는 형식도 적용되지 않습니다.
Singular value decomposition
- 적용-가능: m-×-n 행렬 A.
- 분해: , 여기서 D는 비-음의 대각 행렬(diagonal matrix)이고, U와 V는 를 만족시킵니다. 여기서 는 V의 켤레 전치(conjugate transpose) (또는 V가 실수만 포함하면 단순히 전치)이고, I는 (일부 차원의) 항등 행렬을 나타냅니다.
- 참조: D의 대각 원소는 A의 특이값(singular values)이라고 불립니다.
- 참조: 위의 고윳값 분해와 마찬가지로, 특이값 분해는 행렬 곱셈이 스칼라 곱셈과 동등한 기본 방향을 찾는 것을 포함하지만, 고려 중인 행렬이 정사각일 필요가 없으므로 일반성이 더 큽니다.
- 고유성: 의 특이값은 항상 고유하게 결정됩니다. 와 는 일반적으로 고유할 필요가 없습니다.
Scale-invariant decompositions
대각선 스케일링과 관련하여 불변인 SVD와 같은 기존 행렬 분해의 변형을 참조합니다.
- 적용가능: m-×-n 행렬 A.
- 단위-스케일-불면 특이-값 분해: , 여기서 S는 스케일-불변 특이값의 고유한 비-음의 대각 행렬(diagonal matrix), U와 V는 유니태리 행렬(unitary matrices), 는 V의 켤레 전치(conjugate transpose)이고, D와 E는 양수 대각 행렬입니다.
- 참조: S의 대각선 원소가 임의적인 비-특이 대각 행렬에 의한 A의 왼쪽 및/또는 오른쪽 곱셈에 관해 불변이라는 점을 제외하고 SVD와 유사하며, 임의적인 유니태리 행렬에 의한 A의 왼쪽 및/또는 오른쪽 곱셈에 관해 특이값이 불변인 표준 SVD와 반대입니다.
- 참조: 의 유니태리 변환이 아닌 대각선에 관해 불변이 필요할 때 표준 SVD의 대안입니다.
- 고유성: 의 스케일-불변 특이값 (S의 대각선 원소에 의해 제공됨)은 항상 고유하게 결정됩니다. 대각선 행렬 D와 E, 및 유니태리 U와 V는 일반적으로 고유할 필요는 없습니다.
- 참조: U와 V 행렬은 SVD에서 그것들과 같지 않습니다.
유사한 스케일-불변 분해는 다른 행렬 분해에서 유도될 수 있습니다; 예를 들어, 스케일-불변 고윳값을 얻기 위해.[2][3]
Other decompositions
Polar decomposition
- 적용가능: 임의의 정사각 복소수 행렬 A.
- 분해: (오른쪽 극 분해) 또는 (왼쪽 극 분해), 여기서 U는 유니태리 행렬(unitary matrix)이고 P와 P'은 양수 반한정 에르미트 행렬(positive semidefinite Hermitian matrices)입니다.
- 고유성: 는 항상 고유하고 와 같습니다 (이는 항상 에르미트이고 양수 반한정입니다). 만약 가 역가능이면, 는 고유합니다.
- 참조: 임의의 에르미트 행렬은 유니태리 행렬로 스펙트럼 분해를 허용하므로, 는 로 쓸 수 있습니다. 는 양수 반한정이므로, 에서 모든 원소는 비-음수입니다. 두 유니태리 행렬의 곱은 유니태리이므로, 를 취하여 특이값 분해인 를 쓸 수 있습니다. 따라서, 극 분해의 존재는 특이값 분해의 존재와 동등합니다.
Algebraic polar decomposition
- 적용가능: 정사각, 복소수, 비-특이 행렬 A.[4]
- 분해: , 여기서 Q는 복소수 직교 행렬이고 S는 복소수 대칭 행렬입니다.
- 고유성: 만약 가 음의 실수 고윳값을 가지지 않으면, 분해는 고유합니다.[5]
- 참조: 이 분해의 존재는 가 와 닮은 것과 동등합니다.[6]
- 참조: 이 분해의 변형은 이며, 여기서 R은 실수 행렬이고 C는 순환 행렬(circular matrix)입니다.[5]
Mostow's decomposition
- 적용가능: 정사각, 복소수, 비-특이 행렬 A.[7][8]
- 분해: , 여기서 U는 유니태리, M은 실수 반-대칭이고 S는 실수 대칭입니다.
- 참조: 행렬 A는 역시 로 분해될 수 있으며, 여기서 U2는 유니태리, M2는 실수 반-대칭이고 S2는 실수 대칭입니다.[5]
Sinkhorn normal form
- 적용가능: 엄격하게 양수 원소를 갖는 정사각 실수 행렬 A.
- 분해: , 여기서 S는 이중 확률(doubly stochastic)이고 D1과 D2는 엄격하게 양수 원소를 갖는 실수 대각 행렬입니다.
Sectoral decomposition
- 적용가능: 섹터 에 포함된 수치 치역(numerical range)을 갖는 정사각, 복소수 행렬 A.
- 분해: , 여기서 C는 역가능 복소수 행렬이고 모든 와 함께 입니다.[9][10]
Williamson's normal form
- 적용가능: 차수 2n×2n을 갖는 정사각, 양수-한정(positive-definite) 실수 행렬 A.
- 분해: , 여기서 는 심플렉틱 행렬(symplectic matrix)이고 D는 비-음의 n-×-n 대각 행렬입니다.[11]
Matrix square root
- 분해: , 일반적으로 고유하지 않습니다.
- 양수 반-한정 의 경우에서, 임을 만족하는 고유한 양수 반-한정 가 있습니다.
Generalizations
준행렬(quasimatrices) 및 c행렬(cmatrices) 또는 연속 행렬(continuous matrices)에 대한 SVD, QR, LU, 및 숄레스키 인수분해의 아날로그가 존재합니다.[12] '준행렬(quasimatrix)'은, 행렬과 같이, 그 원소가 인덱싱된 직사각 스킴이지만, 하나의 이산 인덱스가 연속 인덱스로 대체됩니다. 마찬가지로, 'cmatrix'는 두 인덱스에서 연속적입니다. cmatrix의 예제로, 적분 연산자(integral operator)의 커널을 생각할 수 있습니다.
이들 인수분해는 Fredholm (1903), Hilbert (1904), 및 Schmidt (1907)의 초기 연구를 기반으로 합니다. 중요한 논문의 설명 및 영어 번역에 대해서는 Stewart (2011)를 참조하십시오.
See also
References
Notes
- ^ If a non-square matrix is used, however, then the matrix U will also have the same rectangular shape as the original matrix A. And so, calling the matrix U would be incorrect as the correct term would be that U is the 'row echelon form' of A. Other than this, there are no differences in LU factorization for square and non-square matrices.
Citations
- ^ Lay, David C. (2016). Linear algebra and its applications. Steven R. Lay, Judith McDonald (Fifth Global ed.). Harlow. p. 142. ISBN 978-1-292-09223-2. OCLC 920463015.
{{cite book}}
: CS1 maint: location missing publisher (link) - ^ Uhlmann, J.K. (2018), "A Generalized Matrix Inverse that is Consistent with Respect to Diagonal Transformations", SIAM Journal on Matrix Analysis and Applications, 239 (2): 781–800, doi:10.1137/17M113890X
- ^ Uhlmann, J.K. (2018), "A Rank-Preserving Generalized Matrix Inverse for Consistency with Respect to Similarity", IEEE Control Systems Letters, 3: 91–95, arXiv:1804.07334, doi:10.1109/LCSYS.2018.2854240, ISSN 2475-1456, S2CID 5031440
- ^ Choudhury & Horn 1987, pp. 219–225
- ^ a b c Bhatia, Rajendra (2013-11-15). "The bipolar decomposition". Linear Algebra and Its Applications. 439 (10): 3031–3037. doi:10.1016/j.laa.2013.09.006.
- ^ Horn & Merino 1995, pp. 43–92
- ^ Mostow, G. D. (1955), Some new decomposition theorems for semi-simple groups, Mem. Amer. Math. Soc., vol. 14, American Mathematical Society, pp. 31–54
- ^ Nielsen, Frank; Bhatia, Rajendra (2012). Matrix Information Geometry. Springer. p. 224. arXiv:1007.4402. doi:10.1007/978-3-642-30232-9. ISBN 9783642302329. S2CID 118466496.
- ^ Zhang, Fuzhen (30 June 2014). "A matrix decomposition and its applications". Linear and Multilinear Algebra. 63 (10): 2033–2042. doi:10.1080/03081087.2014.933219. S2CID 19437967.
- ^ Drury, S.W. (November 2013). "Fischer determinantal inequalities and Highamʼs Conjecture". Linear Algebra and Its Applications. 439 (10): 3129–3133. doi:10.1016/j.laa.2013.08.031.
- ^ Idel, Martin; Soto Gaona, Sebastián; Wolf, Michael M. (2017-07-15). "Perturbation bounds for Williamson's symplectic normal form". Linear Algebra and Its Applications. 525: 45–58. arXiv:1609.01338. doi:10.1016/j.laa.2017.03.013. S2CID 119578994.
- ^ Townsend & Trefethen 2015
Bibliography
- Choudhury, Dipa; Horn, Roger A. (April 1987). "A Complex Orthogonal-Symmetric Analog of the Polar Decomposition". SIAM Journal on Algebraic and Discrete Methods. 8 (2): 219–225. doi:10.1137/0608019.
- Fredholm, I. (1903), "Sur une classe d'´equations fonctionnelles", Acta Mathematica (in French), 27: 365–390, doi:10.1007/bf02421317
- Hilbert, D. (1904), "Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen", Nachr. Königl. Ges. Gött (in German), 1904: 49–91
- Horn, Roger A.; Merino, Dennis I. (January 1995). "Contragredient equivalence: A canonical form and some applications". Linear Algebra and Its Applications. 214: 43–92. doi:10.1016/0024-3795(93)00056-6.
- Meyer, C. D. (2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 978-0-89871-454-8
- Schmidt, E. (1907), "Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Teil. Entwicklung willkürlichen Funktionen nach System vorgeschriebener", Mathematische Annalen (in German), 63 (4): 433–476, doi:10.1007/bf01449770
- Simon, C.; Blume, L. (1994). Mathematics for Economists. Norton. ISBN 978-0-393-95733-4.
- Stewart, G. W. (2011), Fredholm, Hilbert, Schmidt: three fundamental papers on integral equations (PDF), retrieved 2015-01-06
- Townsend, A.; Trefethen, L. N. (2015), "Continuous analogues of matrix factorizations", Proc. R. Soc. A, 471 (2173): 20140585, Bibcode:2014RSPSA.47140585T, doi:10.1098/rspa.2014.0585, PMC 4277194, PMID 25568618
- Jun, Lu (2021), Numerical matrix decomposition and its modern applications: A rigorous first course, arXiv:2107.02579
External links
- Online Matrix Calculator
- Wolfram Alpha Matrix Decomposition Computation » LU and QR Decomposition
- Springer Encyclopaedia of Mathematics » Matrix factorization
- GraphLab GraphLab collaborative filtering library, large scale parallel implementation of matrix decomposition methods (in C++) for multicore.