Aproximación de la matriz CUR

Una aproximación matricial CUR es un conjunto de tres matrices que, al multiplicarse entre sí, aproximan con precisión una matriz dada. ^{[ 1 ] [ 2 ] [ 3 ]} Una aproximación CUR puede utilizarse 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 los vectores singulares izquierdo y derecho):

• Existen métodos para calcularlo con una complejidad temporal asintótica menor que la de la descomposición en valores singulares (SVD).
• Las matrices son más fáciles de interpretar; el significado de las filas y columnas en la matriz descompuesta es esencialmente el mismo que su significado en la matriz original.

Formalmente, una aproximación matricial CUR de una matriz A consiste en tres matrices C , U y R, donde C está formada por las columnas de A , R por las filas de A , y el producto CUR se aproxima fielmente a A. Generalmente, la aproximación CUR se elige con rango k , lo que significa que C contiene k columnas de A , R contiene k filas de A , y U es una matriz de k × k . Existen muchas aproximaciones matriciales CUR posibles, y muchas aproximaciones CUR para un rango dado.

La aproximación de matriz CUR se usa frecuentemente 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 también 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 otra rotación de los datos en el espacio.

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

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

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

La descomposición tensorial-CURT ^{[ 6 ]} es una generalización de la descomposición matricial-CUR. Formalmente, una aproximación tensorial CURT de un tensor A son tres matrices y un (núcleo)tensor C , R , T y U tales que C está hecho de columnas de A , R está hecho de filas de A , T está hecho de tubos de A y que el producto U(C,R,T) (donde el${\displaystyle i,j,l}$-la entrada es${\displaystyle \sum _{i',j',l'}U_{i',j',l'}C_{i,i'}R_{j,j'}T_{l,l'}}$) se aproxima mucho a A. Por lo general, se selecciona CURT para que 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 (núcleo) de k por k por k .

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 elige J muestreando columnas al azar (con reemplazo) con una probabilidad proporcional a las normas de columna al cuadrado,${\displaystyle \|L_{:,j}\|_{2}^{2}}$; y de manera similar, muestreando I proporcional a las normas de fila al cuadrado,${\displaystyle \|L_{i}\|_{2}^{2}}$Los autores demuestran que tomar${\displaystyle |J|\approx k/\varepsilon ^{4}}$y${\displaystyle |I|\approx k/\varepsilon ^{2}}$dónde${\displaystyle 0\leq \varepsilon }$El algoritmo alcanza la cota de error de Frobenius.${\displaystyle \|A-CUR\|_{F}\leq \|A-A_{k}\|_{F}+\varepsilon \|A\|_{F}}$, dónde${\displaystyle A_{k}}$es la aproximación óptima de rango k .

• Reducción de dimensionalidad