강력한 주성분 분석

강력한 주성분 분석(RCA)은 광범위하게 사용되는 주성분 분석(PCA)의 통계적 절차를 수정하는 것으로, 완전히 손상된 관측치에 대해 잘 작동한다.Robust PCA에는 매우 손상된 측정치 M = L₀ +S로부터₀ 낮은 등급의 매트릭스 L을₀ 복구하는 것을 목표로 하는 Robust PCA의 이상화된 버전을 포함하여 다양한 접근법이 존재한다.^[1]낮은 순위 및 희소성 행렬에서의 이러한 분해는 주성분 추적법(PCP),^[1] 안정적 PCP,^[2] 정량화된 PCP,^[3] 블록 기반 PCP,^[4] 로컬 PCP 등의 기법에 의해 달성될 수 있다.^[5]그 다음, ALM(Advanced^[6] Lagrange Multiplement Method), ADM(^[7]Active Direction Method), FAM^[8](Fast Crother Minimization), 반복적으로 재가중 최소 제곱(IRLS) 또는 교대 투영(AP^[12]^[13]^[14])과 같은 최적화 방법이 사용된다.

알고리즘

비콘벡스법

강건한 PCA 문제에 대한 2014년 보장 알고리즘(입력 $M=L+S$ 가 $M=L+S$ M $M=L+S$ = L $M=L+S$ + $M=L+S$ {\ $displaystyle M=L+S}$ 인 경우 $M=L+S$ 은 교번 최소화형 알고리즘이다.^[12]The computational complexity is $O\left(mnr^{2}\log {\frac {1}{\epsilon }}\right)$ where the input is the superposition of a low-rank (of rank $r$ ) and a sparse matrix of dimension $m\times n$ and $\epsilon$ is thedesired accuracy of the recovered solution, i.e., $\ {\widehat {L}}-L\ _{F}\leq \epsilon$ where $L$ is the true low-rank component and ${\widehat {L}}$ is the estimated or recovered low-rank component.직관적으로 이 알고리즘은 (SVD 작동을 통해) 낮은 순위 행렬 집합과 희소 행렬 집합(입력-경직 임계값을 통해)에 대한 잔존의 투영을 번갈아 수행한다. 즉, 입력 행렬과 희소 행렬이 주어진 반복에서 얻은 차이와 희소 행렬에 대한 낮은 순위 투영 후 희소 프로젝트.입력 매트릭스와 이전 단계에서 얻은 낮은 순위 매트릭스의 차이에 대해, 그리고 수렴될 때까지 두 단계를 반복한다.

이 교대 투영 알고리즘은 나중에 가속 버전에 의해 개선된다. AcAcAltProj라는 신조어.^[13]가속은 낮은 순위의 행렬 집합에 잔류물을 투영하기 전에 접선 공간 투영을 적용함으로써 달성된다.이 트릭은 이론적으로 보장된 선형 수렴을 유지하면서 앞에 훨씬 작은 $상수$ 를 가진 $(mnr$ 로 연산 복잡성을 개선한다.

가속 교대 투영 알고리즘의 또 다른 빠른 버전은 IRCUR이다.^[14]It uses the structure of CUR decomposition in alternating projections framework to dramatically reduces the compuational complexity of RPCA to $O\left(\max\{m,n\}r^{2}\log(m)\log(n)\log {\frac {1}{\epsilon }}\right)$

볼록 이완

This method consists of relaxing the rank constraint $rank(L)$ in the optimization problem to the nuclear norm $\ L\ _{*}$ and the sparsity constraint $\ S\ _{0}$ to $\ell _{1}$ -norm ${\displaystyle$ $\ S\ _{1$ 결과 프로그램은 증강 라그랑주 멀티피어 등의 방법으로 해결할 수 있다.

적용들

RPCA는 특히 연구 대상 데이터가 자연적으로 낮은 순위와 희박한 기여도로 모델링될 수 있을 때 많은 실제 중요한 응용 프로그램을 가지고 있다.컴퓨터 과학의 현대적 도전에서 영감을 얻은 예는 다음과 같으며, 응용 프로그램에 따라 낮은 순위 요소나 희소성 요소 중 하나가 관심 대상이 될 수 있다.

비디오 감시

일련의 감시 비디오 프레임을 감안할 때, 종종 배경에서 눈에 띄는 활동을 식별해야 한다.비디오 프레임을 매트릭스 M의 컬럼으로 쌓으면, 낮은 순위 컴포넌트 L은₀ 자연스럽게 정지된 배경에 대응하고 희소 컴포넌트 S는₀ 전경에 움직이는 물체를 포착한다.^[1]^[15]

얼굴 인식

다양한 조명 아래 볼록한 램버트 표면의 이미지는 저차원 공간에 걸쳐 있다.^[16]이는 이미지 데이터에 대한 저차원 모델의 효과에 대한 이유 중 하나이다.특히 저차원의 아공간으로 사람의 얼굴 이미지를 대충 짐작하기 쉽다.이 하위 공간을 올바르게 검색할 수 있는 것은 얼굴 인식 및 정렬과 같은 많은 애플리케이션에서 중요하다.이 문제에 RPCA를 성공적으로 적용하면 얼굴을 정확히 회복할 수 있는 것으로 나타났다.^[1]

설문 조사

강력한 PCA
동적 RPCA
낮은 순위와 적층 행렬로 분해
하위 등급 모델^[19]

책, 저널 및 워크샵

책들

T. Bouwmans, N. Aybat, E. Zahzah.강력한 저등급 및 희소성 매트릭스 분해에 대한 지침서: 2016년 5월 이미지 및 비디오 처리, CRC 프레스, 테일러 및 프랜시스 그룹의 애플리케이션(자세한 정보: http://www.crcpress.com/product/isbn/9781498724623)
Z. Lin, H. Zhang "시각적 분석에서 낮은 등급 모델:이론, 알고리즘 및 응용 프로그램", 학술지, Escvier, 2017년 6월. (자세한 정보: https://www.elsevier.com/books/low-rank-models-in-visual-analysis/lin/978-0-12-812731-5)

저널스

N. Vaswani, Y.Chi, T. Bouwmans, "현대 데이터셋을 위한 PCA 재고하기: 이론, 알고리즘 및 응용 프로그램", IEEE의 절차, 2018.
T. Bouwmans, N. Vaswani, P. Rodriges, R. Vidal, Z.린, "Robust Subspace Learning and Tracking: 2018년 12월, 신호 처리에서 선택된 주제에 대한 IEEE 저널 " 이론, 알고리즘 및 응용 프로그램".

워크샵

RSL-CV 2015: ICCV 2015와 연계한 강력한 서브스페이스 학습 및 컴퓨터 비전 워크숍(자세한 내용은 http://rsl-cv2015.univ-lr.fr/workshop/)
RSL-CV 2017: ICCV 2017과 연계한 강력한 서브스페이스 학습 및 컴퓨터 비전에 관한 워크숍(자세한 내용은: http://rsl-cv.univ-lr.fr/2017/)
RSL-CV 2021: ICCV 2021과 연계한 강력한 서브스페이스 학습 및 컴퓨터 비전 워크숍(자세한 내용은 https://rsl-cv.univ-lr.fr/2021/)

세션

SSP 2018과 연계한 "정적·동적 강건한 PCA 및 압축 감지를 위한 온라인 알고리즘" 특별 세션(자세한 정보: https://ssp2018.org/)

리소스 및 라이브러리

웹사이트

도서관

LRS 라이브러리(Andrews Sobral에 의해 개발됨)는 MATLAB에 저위 및 희소성 분해 알고리즘의 컬렉션을 제공한다.이 도서관은 비디오에서 사물 감지를 이동하도록 설계되었지만, 다른 컴퓨터 비전/기계 학습 작업에도 사용할 수 있다.현재 LRSLibrary는 매트릭스와 텐서 방법을 기반으로 100개 이상의 알고리즘을 제공하고 있다.

참조

^ ^a ^b ^c ^d Emmanuel J. Candes; Xiaodong Li; Yi Ma; John Wright (2009). "Robust Principal Component Analysis?". Journal of the ACM. 58 (3): 1–37. doi:10.1145/1970392.1970395. S2CID 7128002.
^ J. Wright; Y. Peng; Y. Ma; A. Ganesh; S. Rao (2009). "Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices by Convex Optimization". Neural Information Processing Systems, NIPS 2009.
^ S. Becker; E. Candes, M. Grant (2011). "TFOCS: Flexible First-order Methods for Rank Minimization". Low-rank Matrix Optimization Symposium, SIAM Conference on Optimization.
^ G. Tang; A. Nehorai (2011). "Robust principal component analysis based on low-rank and block-sparse matrix decomposition". Annual Conference on Information Sciences and Systems, CISS 2011: 1–5. doi:10.1109/CISS.2011.5766144. ISBN 978-1-4244-9846-8. S2CID 17079459.
^ B. Wohlberg; R. Chartrand; J. Theiler (2012). "Local Principal Component Pursuit for Nonlinear Datasets". International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012: 3925–3928. doi:10.1109/ICASSP.2012.6288776. ISBN 978-1-4673-0046-9. S2CID 2747520.
^ Z. Lin; M. Chen; L. Wu; Y. Ma (2013). "The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices". Journal of Structural Biology. 181 (2): 116–27. arXiv:1009.5055. doi:10.1016/j.jsb.2012.10.010. PMC 3565063. PMID 23110852.
^ X. Yuan; J. Yang (2009). "Sparse and Low-Rank Matrix Decomposition via Alternating Direction Methods". Optimization Online.
^ P. Rodríguez; B. Wohlberg (2013). "Fast Principal Component Pursuit Via Alternating Minimization". IEEE International Conference on Image Processing, ICIP 2013: 69–73. doi:10.1109/ICIP.2013.6738015. ISBN 978-1-4799-2341-0. S2CID 5726914.
^ C. Guyon; T. Bouwmans; E. Zahzah (2012). "Foreground Detection via Robust Low Rank Matrix Decomposition including Spatio-Temporal Constraint". International Workshop on Background Model Challenges, ACCV 2012.
^ C. Guyon; T. Bouwmans; E. Zahzah (2012). "Foreground Detection via Robust Low Rank Matrix Factorization including Spatial Constraint with Iterative Reweighted Regression". International Conference on Pattern Recognition, ICPR 2012.
^ C. Guyon; T. Bouwmans; E. Zahzah (2012). "Moving Object Detection via Robust Low Rank Matrix Decomposition with IRLS scheme". International Symposium on Visual Computing, ISVC 2012.
^ ^a ^b P., Netrapalli; U., Niranjan; S., Sanghavi; A., Anandkumar; P., Jain (2014). "Non-convex robust PCA". Advances in Neural Information Processing Systems. 1410: 1107–1115. arXiv:1410.7660. Bibcode:2014arXiv1410.7660N.
^ ^a ^b Cai, H.; Cai, J.-F.; Wei, K. (2019). "Accelerated alternating projections for robust principal component analysis". The Journal of Machine Learning Research. 20 (1): 685–717. arXiv:1711.05519. Bibcode:2017arXiv171105519C.
^ ^a ^b Cai, H.; Hamm, K.; Huang, L.; Li, J.; Wang, T. (2021). "Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation". IEEE Signal Processing Letters. 28: 116–120. arXiv:2010.07422. Bibcode:2020arXiv201007422C. doi:10.1109/LSP.2020.3044130.
^ ^a ^b T. Bouwmans; E. Zahzah (2014). "Robust PCA via Principal Component Pursuit: A Review for a Comparative Evaluation in Video Surveillance". Computer Vision and Image Understanding. 122: 22–34. doi:10.1016/j.cviu.2013.11.009.
^ R. Basri; D. Jacobs. "Lambertian reflectance and linear subspaces". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
^ N. Vaswani; T. Bouwmans; S. Javed; P. Narayanamurthy (2017). "Robust PCA and Robust Subspace Tracking". Preprint. 35 (4): 32–55. arXiv:1711.09492. Bibcode:2017arXiv171109492V. doi:10.1109/MSP.2018.2826566. S2CID 3691367.
^ T. Bouwmans; A. Sobral; S. Javed; S. Jung; E. Zahzahg (2015). "Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset". Computer Science Review. 23: 1–71. arXiv:1511.01245. Bibcode:2015arXiv151101245B. doi:10.1016/j.cosrev.2016.11.001. S2CID 10420698.
^ Z. Lin (2016). "A Review on Low-Rank Models in Data Analysis". Big Data and Information Analytics. 1 (2): 139–161. doi:10.3934/bdia.2016001.

외부 링크

LRSLibrary

[RPCA-1] Emmanuel J. Candes; Xiaodong Li; Yi Ma; John Wright (2009). "Robust Principal Component Analysis?". Journal of the ACM. 58 (3): 1–37. doi:10.1145/1970392.1970395. S2CID 7128002.

[RPCA-WRIGHT-2] J. Wright; Y. Peng; Y. Ma; A. Ganesh; S. Rao (2009). "Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices by Convex Optimization". Neural Information Processing Systems, NIPS 2009.

[RPCA-BECKER-3] S. Becker; E. Candes, M. Grant (2011). "TFOCS: Flexible First-order Methods for Rank Minimization". Low-rank Matrix Optimization Symposium, SIAM Conference on Optimization.

[RPCA-TANG-4] G. Tang; A. Nehorai (2011). "Robust principal component analysis based on low-rank and block-sparse matrix decomposition". Annual Conference on Information Sciences and Systems, CISS 2011: 1–5. doi:10.1109/CISS.2011.5766144. ISBN 978-1-4244-9846-8. S2CID 17079459.

[RPCA-WOHLBERG-5] B. Wohlberg; R. Chartrand; J. Theiler (2012). "Local Principal Component Pursuit for Nonlinear Datasets". International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012: 3925–3928. doi:10.1109/ICASSP.2012.6288776. ISBN 978-1-4673-0046-9. S2CID 2747520.

[RPCA-LIN-6] Z. Lin; M. Chen; L. Wu; Y. Ma (2013). "The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices". Journal of Structural Biology. 181 (2): 116–27. arXiv:1009.5055. doi:10.1016/j.jsb.2012.10.010. PMC 3565063. PMID 23110852.

[RPCA-YUAN-7] X. Yuan; J. Yang (2009). "Sparse and Low-Rank Matrix Decomposition via Alternating Direction Methods". Optimization Online.

[RPCA-RODRIGUEZ-8] P. Rodríguez; B. Wohlberg (2013). "Fast Principal Component Pursuit Via Alternating Minimization". IEEE International Conference on Image Processing, ICIP 2013: 69–73. doi:10.1109/ICIP.2013.6738015. ISBN 978-1-4799-2341-0. S2CID 5726914.

[RPCA-GUYON-1-9] C. Guyon; T. Bouwmans; E. Zahzah (2012). "Foreground Detection via Robust Low Rank Matrix Decomposition including Spatio-Temporal Constraint". International Workshop on Background Model Challenges, ACCV 2012.

[RPCA-GUYON-2-10] C. Guyon; T. Bouwmans; E. Zahzah (2012). "Foreground Detection via Robust Low Rank Matrix Factorization including Spatial Constraint with Iterative Reweighted Regression". International Conference on Pattern Recognition, ICPR 2012.

[RPCA-GUYON-3-11] C. Guyon; T. Bouwmans; E. Zahzah (2012). "Moving Object Detection via Robust Low Rank Matrix Decomposition with IRLS scheme". International Symposium on Visual Computing, ISVC 2012.

[netrapalli2014non-12] P., Netrapalli; U., Niranjan; S., Sanghavi; A., Anandkumar; P., Jain (2014). "Non-convex robust PCA". Advances in Neural Information Processing Systems. 1410: 1107–1115. arXiv:1410.7660. Bibcode:2014arXiv1410.7660N.

[cai2019accelerated-13] Cai, H.; Cai, J.-F.; Wei, K. (2019). "Accelerated alternating projections for robust principal component analysis". The Journal of Machine Learning Research. 20 (1): 685–717. arXiv:1711.05519. Bibcode:2017arXiv171105519C.

[cai2021rapid-14] Cai, H.; Hamm, K.; Huang, L.; Li, J.; Wang, T. (2021). "Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation". IEEE Signal Processing Letters. 28: 116–120. arXiv:2010.07422. Bibcode:2020arXiv201007422C. doi:10.1109/LSP.2020.3044130.

[RPCA-BOUWMANS-15] T. Bouwmans; E. Zahzah (2014). "Robust PCA via Principal Component Pursuit: A Review for a Comparative Evaluation in Video Surveillance". Computer Vision and Image Understanding. 122: 22–34. doi:10.1016/j.cviu.2013.11.009.

[16] R. Basri; D. Jacobs. "Lambertian reflectance and linear subspaces". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[RPCA-VASWANI-17] N. Vaswani; T. Bouwmans; S. Javed; P. Narayanamurthy (2017). "Robust PCA and Robust Subspace Tracking". Preprint. 35 (4): 32–55. arXiv:1711.09492. Bibcode:2017arXiv171109492V. doi:10.1109/MSP.2018.2826566. S2CID 3691367.

[RPCA-BOUWMANS-COSREV-18] T. Bouwmans; A. Sobral; S. Javed; S. Jung; E. Zahzahg (2015). "Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset". Computer Science Review. 23: 1–71. arXiv:1511.01245. Bibcode:2015arXiv151101245B. doi:10.1016/j.cosrev.2016.11.001. S2CID 10420698.

[LR-LIN-19] Z. Lin (2016). "A Review on Low-Rank Models in Data Analysis". Big Data and Information Analytics. 1 (2): 139–161. doi:10.3934/bdia.2016001.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[12]

[13]

[14]

[15]

[16]

[19]

Search