Saltar al contenido
Volver a los resultados

Completado de matrices

Propuesto por
Emmanuel Candès & Benjamin Recht
Año
2009
Tipo
Convex low-rank recovery
Familia
Missing data

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

El completado de matrices es una técnica para recuperar una matriz de bajo rango a partir de un subconjunto pequeño, posiblemente aleatorio, de sus entradas.

Introducida por Emmanuel Candès y Benjamin Recht en 2009, reformula el problema como minimización de la norma nuclear — un sustituto convexo de la minimización del rango — y proporciona garantías teóricas de que la recuperación exacta es factible cuando las entradas se observan de forma uniforme aleatoria y la matriz satisface una condición de incoherencia.

La intuición detrás del método

Imagine una hoja de cálculo parcialmente rellenada de valoraciones de usuarios sobre películas, donde la mayoría de las celdas están en blanco. Si los datos subyacentes tienen una estructura simple — digamos, el gusto se explica por solo unos pocos factores latentes como la preferencia por género y la época — entonces conocer incluso una pequeña fracción de las valoraciones es suficiente para rellenar el resto con confianza. El completado de matrices explota esta estructura oculta de baja dimensión, de forma similar a completar un rompecabezas cuando se sabe que la imagen tiene solo unas pocas formas distintas.

Historia

El completado de matrices surgió de la literatura de detección comprimida. Candès y Recht (2009) establecieron el primer teorema de recuperación exacta a través de la minimización de la norma nuclear, seguido de cerca por el trabajo de Candès y Tao sobre el poder de la incoherencia. El método ganó amplia atención pública a través de la competencia Netflix Prize, donde los métodos de filtrado colaborativo de bajo rango lograron una precisión de recomendación de vanguardia. Trabajos posteriores de Recht, Fazel y Parrilo conectaron la minimización de la norma nuclear con la regularización de la norma de traza en el aprendizaje automático.

Cuándo usarlo

Utilice el completado de matrices cuando los datos puedan organizarse como una matriz con entradas sistemáticamente faltantes y haya razones para creer que la señal verdadera tiene bajo rango — por ejemplo, en sistemas de recomendación, genómica, análisis de redes sociales y recuperación de imágenes. Las suposiciones clave son que las entradas faltan al azar y que la matriz satisface una condición de incoherencia. No es apropiado para matrices con datos faltantes estructurados o no aleatorios, estructura de rango muy alto, o cuando la suposición de bajo rango no está justificada. Las alternativas incluyen la imputación MICE para datos faltantes generales y NMF cuando se requiere no negatividad.

Limitaciones y consideraciones

  • El costo computacional de la programación semidefinida escala mal con las dimensiones de la matriz
  • La suposición de incoherencia puede fallar en conjuntos de datos reales con datos faltantes estructurados o valores atípicos
  • El rendimiento se degrada cuando el rango verdadero no es mucho menor que las dimensiones de la matriz
  • La minimización de la norma nuclear puede ser sensible al ruido; las variantes robustas añaden complejidad adicional

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Recuperación exacta demostrable bajo condiciones leves con un programa convexo de tiempo polinomial
  • Maneja tasas muy altas de datos faltantes cuando la matriz es verdaderamente de bajo rango
  • No se requiere conocimiento previo del rango; la minimización de la norma nuclear lo encuentra implícitamente
  • Fuertes garantías teóricas basadas en la teoría de matrices aleatorias y el análisis convexo

Aplicaciones

  • Filtrado colaborativo y sistemas de recomendación (predicción de valoraciones de usuarios-ítems)
  • Genómica y bioinformática (recuperación de matrices de expresión génica con mediciones faltantes)
  • Visión por computadora (relleno de imágenes y sustracción de fondo de video)
  • Localización de redes de sensores (recuperación de matrices de posición a partir de mediciones de distancia parciales)
  • Neurociencia (completado de matrices de conectividad funcional a partir de observaciones parciales de fMRI)

Cómo funciona

Cómo funciona

1

El algoritmo comienza con una matriz M cuyas entradas solo se observan en un conjunto de índices Omega. Estos valores observados forman las restricciones para el problema de recuperación. Se asume que el patrón de escasez se muestrea de forma uniforme aleatoria, que es el entorno teórico en el que se establecen las garantías de recuperación exacta.

Fórmula
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}
2

Dado que minimizar directamente el rango de una matriz es NP-difícil, Candès y Recht proponen minimizar la norma nuclear — la suma de los valores singulares — como una relajación convexa. La norma nuclear desempeña el mismo papel para las matrices que la norma L1 para los vectores en la detección comprimida: promueve soluciones de bajo rango manteniendo el problema tratable mediante programación semidefinida.

Fórmula
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega
3

Para que la recuperación sea posible, los vectores singulares de la matriz verdadera no deben estar demasiado alineados con la base estándar, cuantificado por el parámetro de incoherencia mu. Las matrices que concentran su energía en solo unas pocas filas o columnas son incoherentes; las matrices altamente localizadas violan esta condición y no pueden recuperarse de una muestra aleatoria, porque demasiada información está codificada en las entradas no observadas.

Fórmula
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}
4

Cuando el número de entradas observadas excede un umbral proporcional a mu veces el rango r veces n log n, el minimizador del problema de la norma nuclear recupera la matriz verdadera exactamente con alta probabilidad. Este resultado muestra que el tamaño de muestra requerido es solo logarítmicamente mayor que los grados de libertad intrínsecos de una matriz de rango-r, lo que hace que el enfoque sea teóricamente casi óptimo en cuanto a la información.

Fórmula
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}

Errores comunes

  • Asumir datos faltantes aleatorios uniformes cuando las observaciones reales son seleccionadas por el usuario o sesgadas (por ejemplo, solo se califican los elementos muy valorados), lo que viola el modelo de muestreo teórico
  • Omitir la verificación de la condición de incoherencia, lo que lleva a una recuperación deficiente incluso con observaciones suficientes
  • Usar minimización de la norma nuclear sin escalado o regularización en el entorno ruidoso, donde la formulación de recuperación exacta es inapropiada
  • Confundir el completado de matrices con heurísticas de factorización de matrices: el método de mínimos cuadrados alternos puede converger a mínimos locales y carece de las garantías de recuperación de la minimización de la norma nuclear

Preguntas frecuentes

¿Es la minimización de la norma nuclear la única forma de resolver el completado de matrices?

No. Los mínimos cuadrados alternos (ALS) y el descenso de gradiente sobre formas factorizadas (por ejemplo, SGD sobre U y V tal que M ≈ UV^T) se utilizan ampliamente en la práctica por su escalabilidad. Sin embargo, estos enfoques no convexos carecen de las garantías de recuperación exacta de la minimización de la norma nuclear y pueden converger a mínimos locales sin una inicialización cuidadosa.

¿Cuántos datos se necesitan para la recuperación exacta?

Candès y Recht demostraron que aproximadamente C·mu·r·n·log(n) entradas observadas son suficientes para una matriz n×n de rango-r con parámetro de incoherencia mu. En la práctica, esto significa que una matriz de bajo rango a menudo puede recuperarse de una muestra que es solo un múltiplo pequeño de sus grados de libertad intrínsecos, que es r(2n−r) para una matriz n×n.

¿Qué es la condición de incoherencia y por qué es importante?

La incoherencia mide cuán dispersos están los vectores singulares en la base de coordenadas. Una matriz con vectores singulares concentrados — como una matriz de rango 1 que solo es distinta de cero en una fila — almacena la mayor parte de su información en un pequeño conjunto de entradas. Si esas entradas resultan no ser observadas, la recuperación es imposible independientemente de cuántas otras entradas se conozcan.

Métodos relacionados

Fuentes

  1. Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.

    Abrir referencia DOI
    Copiado.