고차단수값분해

Higher-order singular value decomposition

다중선형 대수학에서 텐서고차 특이치 분해(HOSVD)는 특정 직교 터커 분해입니다.이것은 행렬 특이치 분해의 일반화의 한 가지 유형으로 간주될 수 있습니다.그것컴퓨터 비전, 컴퓨터 그래픽, 기계 학습, 과학 컴퓨팅, 그리고 신호 처리에 응용 프로그램을 가지고 있습니다.1928년 [1]F. L. 히치콕까지 거슬러 올라갈 수 있는 측면도 있지만 L. R. 1960년대[2][3][4]3차 텐서용으로 일반적인 Tucker 분해를 개발한 Tucker는 L. De Lathauwer et al.[5]의해 파워 방법을 사용하는 Multilinear SVD 작업에서 추가로 지지되거나, 행렬 SVD를 사용하는 병렬 알고리즘인 M-mode SVD를 개발한 Vasilescu와 Terzopoulos에 의해 지지되었습니다.

더 높은 차수의 특이값 분해(HOSVD)라는 용어가 DeLathauwer라는 이름으로 만들어졌지만, 문헌에서 HOSVD로 흔히 언급되고 Tucker 또는 DeLathauwer 중 하나에 귀속되는 알고리즘은 Vasilescu와 [6][7][8]Terzopoulos에 의해 개발되었습니다.HOSVD의 강건하고 L1-norm 기반 변형도 [9][10][11][12]제안되었습니다.


정의.

이 글의 목적을 위해, 추상 A{\{\M-웨이 배열로서 일부 기저에 대해 좌표로 가정하며, 또한 A 1× ⋯ × ⋯ I ⋯ × ^{ I_{여기서 M은 모드의 수와 텐서의 차수입니다. 복소수이며 R (와) 순수 허수를 모두 포함합니다.

m × R {\}} R_표준 모드-m A [ m {\의 {\{\_{j}의 j번째 {\은 A {\의 j번째 큰 단수 값에 해당합니다. 모드/인자 {\{\(는) 모드 평탄화의 특정 정의에 따라 달라지지 않습니다.다중선형 곱셈의 성질에 의해, 우리는

여기서 ⋅ 켤레 전치를 나타냅니다.두 번째 동일성은 {\{\가 유니터리 행렬이기 때문입니다.지금 코어 텐서 정의
그러면, A {\ HOSVD는[5] 분해입니다.
위의 구성은 모든 텐서가 HOSVD를 가지고 있음을 보여줍니다.

컴팩트 HOSVD

행렬의 콤팩트한 특이치 분해의 경우와 마찬가지로 응용에 매우 유용한 콤팩트한 HOSVD를 고려하는 것도 가능합니다.

× m{\{\m}\m}}}가 표준 인자 m [ m {\의 {\displaystyle {A}에 해당하는 좌단수 벡터의 기저를 포함하는 유니터리 열을 가진 이라고 가정합니다. C를 다음과 같이 합니다.{\ 번째 번째 열 {\{\ 값이A [ {\ 열에 해당하도록 정렬합니다 {\displaystyle} 열부터 입니다.A 이미지의 기초가 됩니다 [{\{\

첫 번째 등식은 (허미트 내부 곱에서) 직교 투영의 속성에 기인하고 마지막 등식은 다중 선형 곱셈의 속성에 기인합니다.평탄화는 사영 지도이고 위의 공식은 = 2 …,M {\ m = 2 m M에 대해 유효하므로, 우리는 이전과 같이 다음을 발견합니다.
여기서 코어 S{\{\는 이제 1× × ⋯ × M{\ R_ R_ \ R_입니다.

다선순위

A {\ 다중 선형[1] 순위는 랭크- {\로 표시됩니다.다중 선형 순위는 {\의 튜플입니다. := ( ] ){\}:=\ {\의 모든 튜플이 다중 선형 순위는 아닙니다.다중 선형 순위는 1 m 1 R_로 제한되며 R m i ≠ {\ R_ _ m} 가 있어야 .

콤팩트 HOSVD는 코어 텐서의 차원이 텐서의 다중 선형 순위의 구성 요소와 일치한다는 점에서 순위 공개 분해입니다.

해석

다음과 같은 기하학적 해석은 전체 HOSVD와 컴팩트 HOSVD 모두에 유효합니다.( 1 2 {\ A{\{\의 다중선 순위라고 하자 R × 2 × ⋯ × {\{\{\ R_ \ R_를 다차원 배열이라고 하면 다음과 같이 확장할 수 있습니다.

_ {\{\{\번째 표준 기저 벡터입니다. 다중 선형 곱셈의 정의에 의해, 다음이 성립합니다.
여기서 × {\{\ R_의 열입니다. B = { 2 ⋯ ⊗ ⊗ r M} ,r …, {\ B =u} _u _{ {u} _{r_{M}}\otimes {} _(는) 정규 텐서 집합입니다.이는 HOSVD가 다차원 S{\{\로 주어진 계수를 사용하여 특별히 선택된 정규 B{\ B 대한 A{\ 표현하는 방법으로 해석될 수 있음을 의미합니다.

계산

A ∈ × 2× ⋯ × I {\ {\ I_ I_를 랭크-1 2 R {\ 를 하위 집합으로하는 텐서라고 .

고전적 계산

Multilinear SVD와 M-mode SVD를 계산하는 전략은 1960년대 L. R.의해 소개되었습니다. Tucker, L.[3] De Lathauwer et al.,[5] 그리고 Vasilescu와 [8][6]Terzopulous에 의해 더욱 옹호되었습니다.HOSVD라는 용어는 Lieven De Lathauwer에 의해 만들어졌지만, 일반적으로 문헌에서 HOSVD로 언급된 알고리즘은 M-mode SVD라는 이름을 가진 Vasilescu와 Terzopoulos에[6][8] 의해 소개되었습니다.정규 모드 행렬을 계산하기 위해 행렬 SVD를 사용하는 병렬 계산입니다.

M-모드 SVD:[6][8]

  • 형식 = m=에서 다음을 수행합니다.
  1. mode-m A [ ]{\{\
  2. (단수) 특이값 A [ ] = m m {\ {A}_= {U_{ 그리고 왼쪽 단수 U m × {\{\ R_
  • 다중선형 S를 통해 코어 S{\{\를 계산합니다 = × × U H × U … × U {\{\}} = {\ _

인터레이스 연산

일부 또는 r≪ k {\ll n_이(가) 코어 텐서와 인자 행렬의 계산을 다음과 같이 인터레이스하는 것으로 구성될 때 훨씬 더 빠른 전략입니다.

  • A 0 ={\}={\
  • = {\ m=은(는) 다음을 수행합니다.
    1. 표준 모드-m A[ ] - {\
    2. (단수) 특이값 A [ ] - = T}= _ 그리고 × m {\ F R_
    3. = H × - {\{\}= _ 또는 이와 동등하게 [] {\{\}\ _

인플레이스 계산

HOSVD는 HOSVD 코어 텐서에 의해 원래 텐서를 덮어써 Fused In-place Sequently Truncated Higher Order Singular Value Decomposition(FIST-HOSVD) 알고리즘을 통해 제자리에서 계산할 수 있으며, 이는 HOSVD 계산의 메모리 소비를 크게 줄입니다.

근사

아래에 언급된 것과 같은 응용 프로그램에서 일반적인 문제는 주어진 A ∈ 1× × ⋯ × ⋯ × M {\ I_ \ I_ I_를 감소된 다중 선형 순위로 1개 근사화하는 것으로 구성됩니다.형식적으로, A {\의 다중선형 랭크를 -( …, …, {\ (로 표시하면, 주어진 에 대해 A { 의 A¯ {\displaystyle {\mathcal {A를 계산합니다.k -( …, …, ){\ {\ {\ {\ 비선형 비볼록 ≥ {\ _ -최적화 문제입니다.

여기서( R ≥ ) ∈ M {\ {\} m {{ I_이며, ‖ {\\ F}}는 프로베니우스 표준입니다.

이 최적화 문제를 해결하기 위한 간단한 아이디어는 고전적인 계산이나 인터레이스 계산의 2단계에서 (콤팩트한) SVD를 잘라내는 것입니다.고전적 계산에서 2단계를 대체함으로써 고전적으로 절단된 HOSVD가 얻어집니다.

  • 순위 계산 - ¯ {\{\ 절단 A [ ] ≈ σ m T{\{\ _ R {\m좌단수 U F F F F F F F F F F F F F F F F F F F F F F F F F F F{\

순차적으로 절단된 HOSVD(또는 연속적으로 절단된 HOSVD)는 인터레이스 계산에서 단계 2를 대체함으로써 얻어집니다.

  • 순위 - R ¯ {\{\ 절단 [ m] - σ v Vm]}^{U_{m}\m R {\m좌단수 U F F F F F F F F F F F F F F F F F F F F F F F F F F F{\ 유감스럽게도 잘림으로 인해 최적의 낮은 다중 선형 순위 최적화 문제가 해결되지 않습니다.[5][6][14][16]그러나 고전적 및 인터리빙된 절단된 HOSVD 모두 준최적 솔루션이 됩니다. ¯ {\가 고전적 또는 순차적으로 절단된 HOSVD를 A ¯ {\{\가 최적의 낮은 다중 선형 랭크 근사 문제 해결책을 나타냅니다.
    실제로 이는 오차가 작은 최적의 솔루션이 존재하는 경우 여러 목적을 위해 절단된 HOSVD도 충분히 우수한 솔루션을 산출할 수 있음을 의미합니다.

적용들

HOSVD는 멀티웨이 어레이에서 관련 정보를 추출하는 데 가장 일반적으로 적용됩니다.

2000년대 초반부터 바실레스쿠는 데이터 분석, 인식 및 합성 문제를 다중 선형 텐서 문제로 재구성하여 인과적 질문을 해결했습니다.텐서 프레임워크의 힘은 보행 인식,[18] 얼굴 인식을 위한 인간 모션 시그니처의 맥락에서 데이터 형성의 인과 요소 측면에서 이미지를 분해하고 표현함으로써 보여졌습니다.TensorFaces[19][20] 및 컴퓨터 그래픽스—텐서 텍스쳐.[21]

HOSVD는 게놈 신호 [22][23][24]처리와 같은 신호 처리 및 빅데이터에 성공적으로 적용되었습니다.또한 이러한 애플리케이션은 고차 GSVD(HO GSVD)[25]와 텐서 GSVD에 [26]영감을 주었습니다.

HOSVD와 SVD의 조합은 또한 [27]질병 감시에서 복잡한 데이터 스트림(공간 및 시간 차원이 있는 다변량 데이터)으로부터 실시간 이벤트 감지를 위해 적용되었습니다.

텐서 제품 모델 변환 기반 컨트롤러 [28][29]설계에도 사용됩니다.

HOSVD의 개념은 TP 모델 변환을 통해 Baranyi와 [28][29]Yam에 의해 기능으로 옮겨졌습니다.이 확장은 텐서 곱 함수의 HOSVD 기반 표준 형태와 선형 매개변수 가변 시스템[30] 모델의 정의 및 볼록 선체 조작 기반 제어 최적화 이론으로 이어졌습니다(제어 이론의 TP 모델 변환 참조).

HOSVD는 다시점 데이터[31] 분석에 적용하기 위해 제안되었으며 유전자 [32]발현으로부터 in silico 약물 발견에 성공적으로 적용되었습니다.

강건한 L1-norm 변이체

L1-터커는 L1 노름 기반의 강력한 터커 [10][11]분해 변형입니다.L1-HOSVD는 L1-터커의 [10][12]용액에 대한 HOSVD와 유사합니다.

참고문헌

  1. ^ a b Hitchcock, Frank L (1928-04-01). "Multiple Invariants and Generalized Rank of a M-Way Array or Tensor". Journal of Mathematics and Physics. 7 (1–4): 39–79. doi:10.1002/sapm19287139. ISSN 1467-9590.
  2. ^ Tucker, Ledyard R. (1966-09-01). "Some mathematical notes on three-mode factor analysis". Psychometrika. 31 (3): 279–311. doi:10.1007/bf02289464. ISSN 0033-3123. PMID 5221127. S2CID 44301099.
  3. ^ a b Tucker, L. R. (1963). "Implications of factor analysis of three-way matrices for measurement of change". In C. W. Harris (Ed.), Problems in Measuring Change. Madison, Wis.: Univ. Wis. Press.: 122–137.
  4. ^ Tucker, L. R. (1964). "The extension of factor analysis to three-dimensional matrices". In N. Frederiksen and H. Gulliksen (Eds.), Contributions to Mathematical Psychology. New York: Holt, Rinehart and Winston: 109–127.
  5. ^ a b c d De Lathauwer, L.; De Moor, B.; Vandewalle, J. (2000-01-01). "A Multilinear Singular Value Decomposition". SIAM Journal on Matrix Analysis and Applications. 21 (4): 1253–1278. CiteSeerX 10.1.1.102.9135. doi:10.1137/s0895479896305696. ISSN 0895-4798.
  6. ^ a b c d e M. A. O. 바실레스쿠, D.Terzopoulos (2002), M-mode SVD라는 이름을 가지고 있습니다.M-mode SVD는 병렬 계산에 적합하며 행렬 SVD "Multilinear Analysis of Image embles: TensorFaces", Pro. 7차 유럽 컴퓨터 비전 컨퍼런스 (ECCV'02), 코펜하겐, 덴마크, 2002년 5월
  7. ^ a b M. A. O. 바실레스쿠, D.Terzopoulos (2003), "이미지 앙상블의 다중선형 부분공간 분석", "컴퓨터 비전 및 패턴 인식에 관한 IEEE 컨퍼런스(CVPR'03), Madison, WI, June, 2003"
  8. ^ a b c d M. A. O. 바실레스쿠, D.Terzopoulos (2005) "다선 독립 성분 분석", "컴퓨터 비전 및 패턴 인식에 관한 IEEE 컨퍼런스(CVPR'05), 샌디에고, 캘리포니아, 2005년 6월, vol.1, 547-553"
  9. ^ Godfarb, Donald; Zhiwei, Qin (2014). "Robust low-rank tensor recovery: Models and algorithms". SIAM Journal on Matrix Analysis and Applications. 35 (1): 225–253. arXiv:1311.6182. doi:10.1137/130905010. S2CID 1051205.
  10. ^ a b c Chachlakis, Dimitris G.; Prater-Bennette, Ashley; Markopoulos, Panos P. (22 November 2019). "L1-norm Tucker Tensor Decomposition". IEEE Access. 7: 178454–178465. arXiv:1904.06455. doi:10.1109/ACCESS.2019.2955134.
  11. ^ a b Markopoulos, Panos P.; Chachlakis, Dimitris G.; Papalexakis, Evangelos (April 2018). "The Exact Solution to Rank-1 L1-Norm TUCKER2 Decomposition". IEEE Signal Processing Letters. 25 (4): 511–515. arXiv:1710.11306. Bibcode:2018ISPL...25..511M. doi:10.1109/LSP.2018.2790901. S2CID 3693326.
  12. ^ a b Markopoulos, Panos P.; Chachlakis, Dimitris G.; Prater-Bennette, Ashley (21 February 2019). "L1-Norm Higher-Order Singular-Value Decomposition". 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP). pp. 1353–1357. doi:10.1109/GlobalSIP.2018.8646385. ISBN 978-1-7281-1295-4. S2CID 67874182.
  13. ^ a b Carlini, Enrico; Kleppe, Johannes (2011). "Ranks derived from multilinear maps". Journal of Pure and Applied Algebra. 215 (8): 1999–2004. doi:10.1016/j.jpaa.2010.11.010.
  14. ^ a b c Vannieuwenhoven, N.; Vandebril, R.; Meerbergen, K. (2012-01-01). "A New Truncation Strategy for the Higher-Order Singular Value Decomposition". SIAM Journal on Scientific Computing. 34 (2): A1027–A1052. Bibcode:2012SJSC...34A1027V. doi:10.1137/110836067. ISSN 1064-8275. S2CID 15318433.
  15. ^ a b Hackbusch, Wolfgang (2012). Tensor Spaces and Numerical Tensor Calculus SpringerLink. Springer Series in Computational Mathematics. Vol. 42. doi:10.1007/978-3-642-28027-6. ISBN 978-3-642-28026-9. S2CID 117253621.
  16. ^ a b c d Cobb, Benjamin; Kolla, Hemanth; Phipps, Eric; Çatalyürek, Ümit V. (2022). FIST-HOSVD: Fused in-Place Sequentially Truncated Higher Order Singular Value Decomposition. Platform for Advanced Scientific Computing(PASC). doi:10.1145/3539781.3539798. ISBN 9781450394109.
  17. ^ Grasedyck, L. (2010-01-01). "Hierarchical Singular Value Decomposition of Tensors". SIAM Journal on Matrix Analysis and Applications. 31 (4): 2029–2054. CiteSeerX 10.1.1.660.8333. doi:10.1137/090764189. ISSN 0895-4798.
  18. ^ M. A. O. 바실레스쿠(2002) "인간 동작 서명: 분석, 합성, 인식", "패턴인식에 관한 국제회의 의사록(ICPR 2002), 제3권, 캐나다 퀘벡시, 2002년 8월, 456-460호
  19. ^ M.A.O. 바실레스쿠, D.Terzopoulos (2003) "이미지 앙상블을 위한 다중선형 부분공간 분석, M. A. O. Vasilescu, D. 테르조풀로스, 프록 컴퓨터 비전 및 패턴 인식 콘프. (CVPR '03), Vol. 2, Madison, WI, June, 2003, 93–99.
  20. ^ M.A.O. 바실레스쿠, D.Terzopoulos (2002) "이미지 앙상블의 다중선형 분석: TensorFaces", Pro. 제7회 컴퓨터 비전 유럽 회의(ECCV'02), 덴마크 코펜하겐, 2002년 5월, 컴퓨터 비전 -- ECCV 2002, 컴퓨터 과학 강의 노트, Vol. 2350, A. Heyden et al. (Eds.), Springer-Verlag, Berlin, 2002, 447-460
  21. ^ M.A.O. 바실레스쿠, D.Terzopoulos (2004) "텐서 텍스쳐: 다중선형 이미지 기반 렌더링", M. A. O. 바실레스쿠와 D. 테르조풀로스, 프록 ACM SIGGRAPH 2004 컨퍼런스 로스앤젤레스, 캘리포니아, 2004년 8월, 컴퓨터 그래픽 프로시딩, 연례 컨퍼런스 시리즈, 2004, 336-342.
  22. ^ L. Omberg; G. H. Golub; O. Alter (November 2007). "A Tensor Higher-Order Singular Value Decomposition for Integrative Analysis of DNA Microarray Data From Different Studies". PNAS. 104 (47): 18371–18376. Bibcode:2007PNAS..10418371O. doi:10.1073/pnas.0709146104. PMC 2147680. PMID 18003902.
  23. ^ L. Omberg; J. R. Meyerson; K. Kobayashi; L. S. Drury; J. F. X. Diffley; O. Alter (October 2009). "Global Effects of DNA Replication and DNA Replication Origin Activity on Eukaryotic Gene Expression". Molecular Systems Biology. 5: 312. doi:10.1038/msb.2009.70. PMC 2779084. PMID 19888207. Highlight.
  24. ^ C. Muralidhara; A. M. Gross; R. R. Gutell; O. Alter (April 2011). "Tensor Decomposition Reveals Concurrent Evolutionary Convergences and Divergences and Correlations with Structural Motifs in Ribosomal RNA". PLOS ONE. 6 (4): e18768. Bibcode:2011PLoSO...618768M. doi:10.1371/journal.pone.0018768. PMC 3094155. PMID 21625625. Highlight.
  25. ^ S. P. Ponnapalli; M. A. Saunders; C. F. Van Loan; O. Alter (December 2011). "A Higher-Order Generalized Singular Value Decomposition for Comparison of Global mRNA Expression from Multiple Organisms". PLOS ONE. 6 (12): e28072. Bibcode:2011PLoSO...628072P. doi:10.1371/journal.pone.0028072. PMC 3245232. PMID 22216090. Highlight.
  26. ^ P. Sankaranarayanan; T. E. Schomay; K. A. Aiello; O. Alter (April 2015). "Tensor GSVD of Patient- and Platform-Matched Tumor and Normal DNA Copy-Number Profiles Uncovers Chromosome Arm-Wide Patterns of Tumor-Exclusive Platform-Consistent Alterations Encoding for Cell Transformation and Predicting Ovarian Cancer Survival". PLOS ONE. 10 (4): e0121396. Bibcode:2015PLoSO..1021396S. doi:10.1371/journal.pone.0121396. PMC 4398562. PMID 25875127. AAAS EurekAlert! Press Release and NAE Podcast Feature.
  27. ^ Hadi Fanaee-T; João Gama (May 2015). "EigenEvent: An algorithm for event detection from complex data streams in Syndromic surveillance". Intelligent Data Analysis. 19 (3): 597–616. arXiv:1406.3496. Bibcode:2014arXiv1406.3496F. doi:10.3233/IDA-150734. S2CID 17966555.
  28. ^ a b P. Baranyi (April 2004). "TP model transformation as a way to LMI based controller design". IEEE Transactions on Industrial Electronics. 51 (2): 387–400. doi:10.1109/tie.2003.822037. S2CID 7957799.
  29. ^ a b P. Baranyi; D. Tikk; Y. Yam; R. J. Patton (2003). "From Differential Equations to PDC Controller Design via Numerical Transformation". Computers in Industry. 51 (3): 281–297. doi:10.1016/s0166-3615(03)00058-7.
  30. ^ P. Baranyi; L. Szeidl; P. Várlaki; Y. Yam (July 3–5, 2006). Definition of the HOSVD-based canonical form of polytopic dynamic models. 3rd International Conference on Mechatronics (ICM 2006). Budapest, Hungary. pp. 660–665.
  31. ^ Y-h. Taguchi (August 2017). "Tensor decomposition-based unsupervised feature extraction applied to matrix products for multi-view data processing". PLOS ONE. 12 (8): e0183933. Bibcode:2017PLoSO..1283933T. doi:10.1371/journal.pone.0183933. PMC 5571984. PMID 28841719.
  32. ^ Y-h. Taguchi (October 2017). "Identification of candidate drugs using tensor-decomposition-based unsupervised feature extraction in integrated analysis of gene expression between diseases and DrugMatrix datasets". Scientific Reports. 7 (1): 13733. Bibcode:2017NatSR...713733T. doi:10.1038/s41598-017-13003-0. PMC 5653784. PMID 29062063.