Aproximación de la matriz CUR

Una aproximación matricial CUR es un conjunto de tres matrices que, al multiplicarse entre sí, se aproximan estrechamente a una matriz dada. ^{[1] [2] [3]} Una aproximación CUR se puede utilizar de la misma manera que la aproximación de bajo rango de la descomposición en valores singulares (SVD). Las aproximaciones CUR son menos precisas que la SVD, pero ofrecen dos ventajas clave, ambas derivadas del hecho de que las filas y columnas provienen de la matriz original (en lugar de vectores singulares izquierdo y derecho):

• Existen métodos para calcularlo con una complejidad temporal asintótica menor que la SVD.
• Las matrices son más interpretables; los significados de las filas y columnas en la matriz descompuesta son esencialmente los mismos que sus significados en la matriz original.

Formalmente, una aproximación matricial CUR de una matriz A son tres matrices C , U y R tales que C está formada por columnas de A , R está formada por filas de A y que el producto CUR se aproxima estrechamente a A . Por lo general, se selecciona que la CUR sea una aproximación de rango - k , lo que significa que C contiene k columnas de A , R contiene k filas de A y U es una matriz k por k . Hay muchas aproximaciones matriciales CUR posibles y muchas aproximaciones matriciales CUR para un rango dado.

La aproximación matricial CUR se utiliza a menudo ^{[ cita requerida ]} en lugar de la aproximación de bajo rango de la SVD en el análisis de componentes principales . La CUR es menos precisa, pero las columnas de la matriz C se toman de A y las filas de R se toman de A. En PCA, cada columna de A contiene una muestra de datos; por lo tanto, la matriz C está formada por un subconjunto de muestras de datos. Esto es mucho más fácil de interpretar que los vectores singulares izquierdos de la SVD, que representan los datos en un espacio rotado. De manera similar, la matriz R está formada por un subconjunto de variables medidas para cada muestra de datos. Esto es más fácil de comprender que los vectores singulares derechos de la SVD, que son otras rotaciones de los datos en el espacio.

Matriz CUR

Hamm ^[4] y Aldroubi et al. ^[5] describen el siguiente teorema, que describe una descomposición CUR de una matriz con rango : ${\displaystyle L}$ ${\displaystyle r}$

Teorema: Consideremos los índices de fila y columna con . Denotemos submatrices y . Si rank( ) = rank( ), entonces , donde denota la pseudoinversa de Moore–Penrose . ${\displaystyle I,J\subseteq [n]}$ ${\displaystyle |I|,|J|\geq r}$ ${\displaystyle C=L_{:,J},}$ ${\displaystyle U=L_{I,J}}$ ${\displaystyle R=L_{I,:}}$ ${\displaystyle U}$ ${\displaystyle L}$ ${\displaystyle L=CU^{+}R}$ ${\displaystyle (\cdot )^{+}}$

En otras palabras, si tiene rango bajo, podemos tomar una submatriz del mismo rango, junto con algunas filas y columnas de y usarlas para reconstruir . ${\displaystyle L}$ ${\displaystyle U=L_{I,J}}$ ${\displaystyle R}$ ${\displaystyle C}$ ${\displaystyle L}$ ${\displaystyle L}$

Tensor CUR

La descomposición CURT de tensor ^[6] es una generalización de la descomposición CUR de matriz. Formalmente, una aproximación de tensor CURT de un tensor A son tres matrices y un tensor (central) C , R , T y U tales que C está formado por columnas de A , R está formado por filas de A , T está formado por tubos de A y que el producto U(C,R,T) (donde la -ésima entrada de este es ) se aproxima estrechamente a A . Por lo general, se selecciona que la CURT sea una aproximación de rango - k , lo que significa que C contiene k columnas de A , R contiene k filas de A , T contiene tubos de A y U es un tensor (central) k -por- k -por- k . ${\displaystyle i,j,l}$ ${\displaystyle \sum _{i',j',l'}U_{i',j',l'}C_{i,i'}R_{j,j'}T_{l,l'}}$

Algoritmos

La aproximación de la matriz CUR no es única y existen múltiples algoritmos para calcularla. Uno de ellos es ALGORITHMCUR. ^[1]

El algoritmo "Linear Time CUR" ^[7] simplemente selecciona J mediante un muestreo aleatorio de columnas (con reemplazo) con probabilidad proporcional a las normas de columna al cuadrado, ; y de manera similar, un muestreo de I proporcional a las normas de fila al cuadrado, . Los autores muestran que tomando y donde , el algoritmo alcanza el límite de error de Frobenius , donde es la aproximación óptima de rango k . ${\displaystyle \|L_{:,j}\|_{2}^{2}}$ ${\displaystyle \|L_{i}\|_{2}^{2}}$ ${\displaystyle |J|\approx k/\varepsilon ^{4}}$ ${\displaystyle |I|\approx k/\varepsilon ^{2}}$ ${\displaystyle 0\leq \varepsilon }$ ${\displaystyle \|A-CUR\|_{F}\leq \|A-A_{k}\|_{F}+\varepsilon \|A\|_{F}}$ ${\displaystyle A_{k}}$

Véase también

• Reducción de dimensionalidad

Referencias

1. Michael W. Mahoney; Petros Drineas. "Descomposiciones de matrices CUR para un mejor análisis de datos" . Consultado el 26 de junio de 2012 .
2. Boutsidis, Christos; Woodruff, David P. (2014). Descomposiciones óptimas de matrices CUR . STOC '14 Actas del cuadragésimo sexto simposio anual de la ACM sobre teoría de la computación.
3. Song, Zhao; Woodruff, David P.; Zhong, Peilin (2017). Aproximación de rango bajo con error de norma L1 por entrada . STOC '17 Actas del cuadragésimo noveno simposio anual de la ACM sobre teoría de la computación. arXiv : 1611.00898 .
4. Keaton Hamm y Longxiu Huang. Perspectivas sobre las descomposiciones CUR. Análisis armónico computacional y aplicado, 48(3):1088–1099, 2020.
5. Aldroubi, Akram y Hamm, Keaton y Koku, Ahmet Bugra y Sekmen, Ali. Descomposiciones CUR, matrices de similitud y agrupamiento de subespacios. Frontiers in Applied Mathematics and Statistics, 2019, Frontiers Media SA
6. Song, Zhao; Woodruff, David P.; Zhong, Peilin (2017). "Aproximación de rango bajo del tensor de error relativo". arXiv : 1704.08246 [cs.DS].
7. Drineas, Petros; Kannan, Ravi; Mahoney, Michael W. (1 de enero de 2006). "Algoritmos rápidos de Monte Carlo para matrices I: Aproximación de la multiplicación de matrices". Revista SIAM de Computación . 36 (1): 132–157. doi :10.1137/S0097539704442684. ISSN  0097-5397.