Análisis robusto de componentes principales

El análisis robusto de componentes principales (RPCA, por sus siglas en inglés) es una modificación del procedimiento estadístico ampliamente utilizado de análisis de componentes principales (PCA, por sus siglas en inglés) que funciona bien con respecto a observaciones extremadamente corruptas. Existen varios enfoques diferentes para el PCA robusto, incluida una versión idealizada del PCA robusto, que tiene como objetivo recuperar una matriz de bajo rango L ₀ a partir de mediciones altamente corruptas M = L ₀ +S ₀ . ^[1] Esta descomposición en matrices dispersas y de bajo rango se puede lograr mediante técnicas como el método de búsqueda de componentes principales (PCP, por sus siglas en inglés), ^[1] PCP estable, ^[2] PCP cuantificado, ^[3] PCP basado en bloques, ^[4] y PCP local. ^[5] Luego, se utilizan métodos de optimización como el Método del Multiplicador de Lagrange Aumentado (ALM ^[6] ), el Método de Dirección Alternada (ADM ^[7] ), la Minimización Alternada Rápida (FAM ^[8] ), los Mínimos Cuadrados Reponderados Iterativamente (IRLS ^{[9] [10] [11]} ) o las Proyecciones Alternadas (AP ^{[12] [13] [14]} ).

Algoritmos

Método no convexo

El algoritmo garantizado de 2014 para el problema PCA robusto (con la matriz de entrada siendo ) es un algoritmo de tipo de minimización alternada. ^[12] La complejidad computacional es donde la entrada es la superposición de una matriz de rango bajo (de rango ) y una matriz dispersa de dimensión y es la precisión deseada de la solución recuperada, es decir, donde es el componente de rango bajo verdadero y es el componente de rango bajo estimado o recuperado. Intuitivamente, este algoritmo realiza proyecciones del residuo sobre el conjunto de matrices de rango bajo (a través de la operación SVD ) y matrices dispersas (a través de umbralización dura por entrada) de manera alternada, es decir, proyección de rango bajo de la diferencia de la matriz de entrada y la matriz dispersa obtenida en una iteración dada seguida de proyección dispersa de la diferencia de la matriz de entrada y la matriz de rango bajo obtenida en el paso anterior, e iterando los dos pasos hasta la convergencia . ${\displaystyle M=L+S}$ ${\displaystyle O\left(mnr^{2}\log {\frac {1}{\epsilon }}\right)}$ ${\displaystyle r}$ ${\displaystyle m\times n}$ ${\displaystyle \epsilon }$ ${\displaystyle \|{\widehat {L}}-L\|_{F}\leq \epsilon }$ ${\displaystyle L}$ ${\displaystyle {\widehat {L}}}$

Este algoritmo de proyecciones alternas se mejora posteriormente con una versión acelerada, denominada AccAltProj. ^[13] La aceleración se logra aplicando una proyección espacial tangente antes de proyectar el residuo sobre el conjunto de matrices de bajo rango. Este truco mejora la complejidad computacional con una constante mucho más pequeña al frente mientras mantiene la convergencia lineal garantizada teóricamente. ${\displaystyle O\left(mnr\log {\frac {1}{\epsilon }}\right)}$

Otra versión rápida del algoritmo de proyecciones alternas aceleradas es IRCUR. ^[14] Utiliza la estructura de descomposición CUR en el marco de proyecciones alternas para reducir drásticamente la complejidad computacional de RPCA. ${\displaystyle O\left(\max\{m,n\}r^{2}\log(m)\log(n)\log {\frac {1}{\epsilon }}\right)}$

Relajación convexa

Este método consiste en relajar la restricción de rango en el problema de optimización a la norma nuclear y la restricción de escasez a la norma - . El programa resultante puede resolverse utilizando métodos como el método de los Multiplicadores de Lagrange Aumentados. ${\displaystyle rank(L)}$ ${\displaystyle \|L\|_{*}}$ ${\displaystyle \|S\|_{0}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \|S\|_{1}}$

Método aumentado de aprendizaje profundo

Algunos trabajos recientes proponen algoritmos RPCA con parámetros de aprendizaje y entrenamiento. ^[15] Un algoritmo de este tipo que se puede aprender y entrenar se puede desarrollar como una red neuronal profunda cuyos parámetros se pueden aprender mediante técnicas de aprendizaje automático a partir de un conjunto de datos o una distribución de problemas determinados. El algoritmo aprendido tendrá un rendimiento superior en la distribución de problemas correspondiente.

Aplicaciones

RPCA tiene muchas aplicaciones importantes en la vida real, en particular cuando los datos en estudio se pueden modelar naturalmente como una contribución de rango bajo más una contribución dispersa. Los siguientes ejemplos están inspirados en los desafíos contemporáneos de la informática y, según las aplicaciones, el componente de rango bajo o el componente disperso podrían ser el objeto de interés:

Videovigilancia

Dada una secuencia de fotogramas de video de vigilancia , a menudo es necesario identificar las actividades que se destacan del fondo. Si apilamos los fotogramas de video como columnas de una matriz M, entonces el componente de bajo rango L ₀ corresponde naturalmente al fondo estacionario y el componente disperso S ₀ captura los objetos en movimiento en primer plano. ^{[1] [16]}

Reconocimiento facial

Las imágenes de una superficie lambertiana convexa bajo diferentes niveles de iluminación abarcan un subespacio de baja dimensión. ^[17] Esta es una de las razones de la eficacia de los modelos de baja dimensión para los datos de imágenes. En particular, es fácil aproximar imágenes de la cara de un humano mediante un subespacio de baja dimensión. Poder recuperar correctamente este subespacio es crucial en muchas aplicaciones, como el reconocimiento y la alineación de rostros . Resulta que RPCA se puede aplicar con éxito a este problema para recuperar exactamente el rostro. ^[1]

Véase también

• Análisis de componentes principales según la norma L1

Encuestas

• PCA robusto ^[16]
• RPCA dinámico ^[18]
• Descomposición en matrices de bajo rango más aditivas ^[19]
• Modelos de bajo rango ^[20]

Libros, revistas y talleres

Libros

• T. Bouwmans, N. Aybat y E. Zahzah. Manual sobre descomposición robusta de matrices dispersas y de bajo rango: aplicaciones en el procesamiento de imágenes y videos , CRC Press, Taylor and Francis Group, mayo de 2016. (Más información: http://www.crcpress.com/product/isbn/9781498724623)
• Z. Lin, H. Zhang, "Modelos de bajo rango en el análisis visual: teorías, algoritmos y aplicaciones", Academic Press, Elsevier, junio de 2017. (más información: https://www.elsevier.com/books/low-rank-models-in-visual-analysis/lin/978-0-12-812731-5)

Revistas

• N. Vaswani , Y. Chi, T. Bouwmans, Número especial sobre “Replanteamiento del PCA para conjuntos de datos modernos: teoría, algoritmos y aplicaciones”, Actas del IEEE, 2018.
• T. Bouwmans, N. Vaswani , P. Rodriguez, R. Vidal, Z. Lin, Número especial sobre “Aprendizaje y seguimiento de subespacios robustos: teoría, algoritmos y aplicaciones”, IEEE Journal of Selected Topics in Signal Processing, diciembre de 2018.

Talleres

• RSL-CV 2015: Taller sobre aprendizaje robusto del subespacio y visión artificial en colaboración con ICCV 2015 (Para más información: http://rsl-cv2015.univ-lr.fr/workshop/)
• RSL-CV 2017: Taller sobre aprendizaje robusto del subespacio y visión artificial en colaboración con ICCV 2017 (Para más información: http://rsl-cv.univ-lr.fr/2017/)
• RSL-CV 2021: Taller sobre aprendizaje subespacial robusto y visión artificial en colaboración con ICCV 2021 (Para más información: https://rsl-cv.univ-lr.fr/2021/)

Sesiones

• Sesión especial sobre "Algoritmos en línea para PCA robusto estático y dinámico y detección de compresión" en conjunto con SSP 2018. (Más información: https://ssp2018.org/)

Recursos y bibliotecas

Sitios web

• Sitio web de sustracción de antecedentes
• Sitio web de DLAM
• Documentación de la Universidad de Illinois - Enlace de archivo

Bibliotecas

La biblioteca LRS (desarrollada por Andrews Sobral) ofrece una colección de algoritmos de descomposición dispersa y de bajo rango en MATLAB. La biblioteca fue diseñada para la detección de objetos en movimiento en videos, pero también se puede utilizar para otras tareas de visión artificial y aprendizaje automático. Actualmente, la biblioteca LRS ofrece más de 100 algoritmos basados ​​en métodos matriciales y tensoriales .

Referencias

1. Emmanuel J. Candes; Xiaodong Li; Yi Ma; John Wright (2009). "¿Análisis robusto de componentes principales?". Revista de la ACM . 58 (3): 1–37. doi :10.1145/1970392.1970395. S2CID  7128002.
2. J. Wright; Y. Peng; Y. Ma; A. Ganesh; S. Rao (2009). "Análisis robusto de componentes principales: recuperación exacta de matrices de bajo rango corruptas mediante optimización convexa". Sistemas de procesamiento de información neuronal, NIPS 2009 .
3. S. Becker; E. Candes, M. Grant (2011). "TFOCS: métodos flexibles de primer orden para la minimización de rangos". Simposio de optimización de matrices de bajo rango, Conferencia SIAM sobre optimización .
4. G. Tang; A. Nehorai (2011). "Análisis robusto de componentes principales basado en descomposición matricial de bajo rango y con bloques dispersos". 2011 45th Annual Conference on Information Sciences and Systems . págs. 1–5. doi :10.1109/CISS.2011.5766144. ISBN 978-1-4244-9846-8. Número de identificación del sujeto  17079459.
5. B. Wohlberg; R. Chartrand; J. Theiler (2012). "Búsqueda de componentes principales locales para conjuntos de datos no lineales". Conferencia internacional IEEE de 2012 sobre acústica, habla y procesamiento de señales (ICASSP) . págs. 3925–3928. doi :10.1109/ICASSP.2012.6288776. ISBN . 978-1-4673-0046-9. Número de identificación del sujeto  2747520.
6. Z. Lin; M. Chen; L. Wu; Y. Ma (2013). "El método del multiplicador de Lagrange aumentado para la recuperación exacta de matrices de bajo rango corruptas". Revista de biología estructural . 181 (2): 116–27. arXiv : 1009.5055 . doi :10.1016/j.jsb.2012.10.010. PMC 3565063 . PMID  23110852. 
7. X. Yuan; J. Yang (2009). "Descomposición de matrices dispersas y de bajo rango mediante métodos de dirección alternada". Optimización en línea .
8. P. Rodríguez; B. Wohlberg (2013). "Búsqueda rápida de componentes principales mediante minimización alternada". 2013 IEEE International Conference on Image Processing . págs. 69–73. doi :10.1109/ICIP.2013.6738015. ISBN 978-1-4799-2341-0. Número de identificación del sujeto  5726914.
9. C. Guyon; T. Bouwmans; E. Zahzah (2012). "Detección de primer plano mediante descomposición robusta de matriz de bajo rango que incluye restricción espacio-temporal". Taller internacional sobre desafíos de modelos de fondo, ACCV 2012 .
10. C. Guyon; T. Bouwmans; E. Zahzah (2012). "Detección de primer plano mediante factorización de matriz robusta de bajo rango que incluye restricción espacial con regresión iterativa reponderada". Conferencia internacional sobre reconocimiento de patrones, ICPR 2012 .
11. C. Guyon; T. Bouwmans; E. Zahzah (2012). "Detección de objetos en movimiento mediante descomposición robusta de matrices de bajo rango con el esquema IRLS". Simposio internacional sobre computación visual, ISVC 2012 .
12. P., Netrapalli; U., Niranjan; S., Sanghavi; A., Anandkumar; P., Jain (2014). "PCA robusto no convexo". Avances en sistemas de procesamiento de información neuronal . 27 : 1107–1115. arXiv : 1410.7660 . Código Bibliográfico :2014arXiv1410.7660N.
13. Cai, H.; Cai, J.-F.; Wei, K. (2019). "Proyecciones alternas aceleradas para análisis robusto de componentes principales". The Journal of Machine Learning Research . 20 (1): 685–717. arXiv : 1711.05519 . Código Bibliográfico :2017arXiv171105519C.
14. Cai, H.; Hamm, K.; Huang, L.; Li, J.; Wang, T. (2021). "Análisis rápido y robusto de componentes principales: estimación inexacta de rango bajo acelerada por CUR". IEEE Signal Processing Letters . 28 : 116–120. arXiv : 2010.07422 . Código Bibliográfico :2021ISPL...28..116C. doi :10.1109/LSP.2020.3044130. S2CID  222378834.
15. Cai, H.; Liu, J.; Yin, W. (2021). "PCA robusto aprendido: un enfoque de despliegue profundo escalable para la detección de valores atípicos de alta dimensión". Avances en sistemas de procesamiento de información neuronal . 34 : 16977–16989. arXiv : 2110.05649 . Código Bibliográfico :2021arXiv211005649C.
16. T. Bouwmans; E. Zahzah (2014). "PCA robusto mediante seguimiento de componentes principales: una revisión para una evaluación comparativa en videovigilancia". Visión artificial y comprensión de imágenes . 122 : 22–34. doi :10.1016/j.cviu.2013.11.009.
17. Basri, Ronen; Jacobs, David W. (2003). "Reflectancia lambertiana y subespacios lineales". IEEE Transactions on Pattern Analysis and Machine Intelligence . 25 (2): 218–233. doi :10.1109/TPAMI.2003.1177153.
18. N. Vaswani ; T. Bouwmans; S. Javed; P. Narayanamurthy (2017). "PCA robusto y seguimiento robusto del subespacio". Preimpresión . 35 (4): 32–55. arXiv : 1711.09492 . Código Bibliográfico :2018ISPM...35d..32V. doi :10.1109/MSP.2018.2826566. S2CID  3691367.
19. T. Bouwmans; A. Sobral; S. Javed; S. Jung; E. Zahzahg (2015). "Descomposición en matrices aditivas de bajo rango para la separación de fondo/primer plano: una revisión para una evaluación comparativa con un conjunto de datos a gran escala". Computer Science Review . 23 : 1–71. arXiv : 1511.01245 . Código Bibliográfico :2015arXiv151101245B. doi :10.1016/j.cosrev.2016.11.001. S2CID  10420698.
20. Z. Lin (2016). "Una revisión sobre modelos de bajo rango en análisis de datos". Big Data y análisis de información . 1 (2): 139–161. doi : 10.3934/bdia.2016001 .

Enlaces externos

• Biblioteca LRS