Completamiento de matriz

Matriz de terminación de una matriz de 5 x 5 parcialmente revelada con rango 1. Izquierda: matriz incompleta observada; derecha: resultado de terminación de la matriz.

Completar una matriz es la tarea de completar las entradas faltantes de una matriz parcialmente observada, lo que equivale a realizar una imputación de datos en estadística. Una amplia gama de conjuntos de datos se organizan naturalmente en forma de matriz. Un ejemplo es la matriz de calificaciones de películas, como aparece en el problema de Netflix : Dada una matriz de calificaciones en la que cada entrada representa la calificación de la película por parte del cliente , si el cliente ha visto la película y falta algo, nos gustaría predecir las entradas restantes para hacer buenas recomendaciones a los clientes sobre qué ver a continuación. Otro ejemplo es la matriz de documentos y términos : las frecuencias de las palabras utilizadas en una colección de documentos se pueden representar como una matriz, donde cada entrada corresponde al número de veces que aparece el término asociado en el documento indicado. ${\displaystyle (i,j)}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle j}$

Sin ninguna restricción en el número de grados de libertad en la matriz completa, este problema está subdeterminado ya que a las entradas ocultas se les pueden asignar valores arbitrarios. Por lo tanto, necesitamos alguna suposición sobre la matriz para crear un problema bien planteado , como suponer que tiene determinante máximo, es definida positiva o es de rango bajo. ^{[1] [2]}

Por ejemplo, se puede suponer que la matriz tiene una estructura de bajo rango y luego buscar la matriz de rango más bajo o, si se conoce el rango de la matriz completa, una matriz de rango que coincida con las entradas conocidas. La ilustración muestra que una matriz de rango 1 parcialmente revelada (a la izquierda) se puede completar con cero errores (a la derecha) ya que todas las filas con entradas faltantes deben ser las mismas que la tercera fila. En el caso del problema de Netflix, se espera que la matriz de calificaciones sea de bajo rango, ya que las preferencias del usuario a menudo se pueden describir mediante unos pocos factores, como el género de la película y el momento del estreno. Otras aplicaciones incluyen la visión por computadora, donde los píxeles faltantes en las imágenes deben reconstruirse, la detección del posicionamiento global de los sensores en una red a partir de información de distancia parcial y el aprendizaje multiclase . El problema de finalización de la matriz es en general NP-hard , pero bajo supuestos adicionales hay algoritmos eficientes que logran una reconstrucción exacta con alta probabilidad. ${\displaystyle r}$

Desde el punto de vista del aprendizaje estadístico, el problema de compleción de matrices es una aplicación de la regularización de matrices , que es una generalización de la regularización vectorial . Por ejemplo, en el problema de compleción de matrices de bajo rango se puede aplicar la penalización de regularización tomando la forma de una norma nuclear. ${\displaystyle R(X)=\lambda \|X\|_{*}}$

Matriz de finalización de rango bajo

Una de las variantes del problema de completar matrices consiste en encontrar la matriz de menor rango que coincida con la matriz que deseamos recuperar para todas las entradas del conjunto de entradas observadas. La formulación matemática de este problema es la siguiente: ${\displaystyle X}$ ${\displaystyle M}$ ${\displaystyle E}$

${\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}}$

Candès y Recht ^[3] demostraron que con supuestos sobre el muestreo de las entradas observadas y un número suficiente de entradas muestreadas, este problema tiene una solución única con alta probabilidad.

Una formulación equivalente, dado que se sabe que la matriz a recuperar es de rango , es resolver para donde ${\displaystyle M}$ ${\displaystyle r}$ ${\displaystyle X}$ ${\displaystyle X_{ij}=M_{ij}\;\;\forall i,j\in E}$

Supuestos

Con frecuencia se hacen una serie de suposiciones sobre el muestreo de las entradas observadas y el número de entradas muestreadas para simplificar el análisis y garantizar que el problema no quede subdeterminado .

Muestreo uniforme de las entradas observadas

Para que el análisis sea manejable, a menudo se supone que el conjunto de entradas observadas y cardinalidad fija se muestrea de manera uniforme al azar de la colección de todos los subconjuntos de entradas de cardinalidad . Para simplificar aún más el análisis, en cambio se supone que se construye mediante muestreo de Bernoulli , es decir, que cada entrada se observa con probabilidad . Si se establece en donde es la cardinalidad esperada deseada de , y son las dimensiones de la matriz (sea sin pérdida de generalidad), está dentro de con alta probabilidad, por lo que el muestreo de Bernoulli es una buena aproximación para el muestreo uniforme. ^[3] Otra simplificación es suponer que las entradas se muestrean de forma independiente y con reemplazo. ^[4] ${\displaystyle E}$ ${\displaystyle |E|}$ ${\displaystyle E}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle {\frac {N}{mn}}}$ ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle m,\;n}$ ${\displaystyle m<n}$ ${\displaystyle |E|}$ ${\displaystyle O(n\log n)}$ ${\displaystyle N}$

Límite inferior del número de entradas observadas

Supongamos que la matriz por (con ) que estamos tratando de recuperar tiene rango . Existe un límite inferior teórico de la información sobre cuántas entradas deben observarse antes de que se pueda reconstruir de forma única. El conjunto de matrices por con rango menor o igual a es una variedad algebraica en con dimensión . Usando este resultado, uno puede demostrar que al menos se deben observar entradas para completar la matriz en para tener una solución única cuando . ^[5] ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle m<n}$ ${\displaystyle r}$ ${\displaystyle M}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle {\mathbb {C} }^{m\times n}}$ ${\displaystyle (n+m)r-r^{2}}$ ${\displaystyle 4nr-4r^{2}}$ ${\displaystyle {\mathbb {C} }^{n\times n}}$ ${\displaystyle r\leq n/2}$

En segundo lugar, debe haber al menos una entrada observada por fila y columna de . La descomposición en valores singulares de está dada por . Si la fila no es observada, es fácil ver que el vector singular derecho de , , se puede cambiar a algún valor arbitrario y aún así producir una matriz coincidente sobre el conjunto de entradas observadas. De manera similar, si la columna no es observada, el vector singular izquierdo de , puede ser arbitrario. Si asumimos un muestreo de Bernoulli del conjunto de entradas observadas, el efecto del recolector de cupones implica que se deben observar entradas del orden de para garantizar que haya una observación de cada fila y columna con alta probabilidad. ^[6] ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle U\Sigma V^{\dagger }}$ ${\displaystyle i}$ ${\displaystyle i^{\text{th}}}$ ${\displaystyle M}$ ${\displaystyle v_{i}}$ ${\displaystyle M}$ ${\displaystyle j}$ ${\displaystyle j^{\text{th}}}$ ${\displaystyle M}$ ${\displaystyle u_{i}}$ ${\displaystyle O(n\log n)}$

Combinando las condiciones necesarias y suponiendo que (una suposición válida para muchas aplicaciones prácticas), el límite inferior del número de entradas observadas necesarias para evitar que el problema de completar la matriz quede subdeterminado es del orden de . ${\displaystyle r\ll m,n}$ ${\displaystyle nr\log n}$

Incoherencia

El concepto de incoherencia surgió en la detección comprimida . Se introduce en el contexto de la terminación de matrices para garantizar que los vectores singulares de no sean demasiado "dispersos" en el sentido de que todas las coordenadas de cada vector singular sean de magnitud comparable en lugar de solo unas pocas coordenadas que tengan magnitudes significativamente mayores. ^{[7] [8]} Los vectores de base estándar son entonces indeseables como vectores singulares, y el vector en es deseable. Como ejemplo de lo que podría salir mal si los vectores singulares son suficientemente "dispersos", considere la matriz por con descomposición en valores singulares . Casi todas las entradas de deben muestrearse antes de que pueda reconstruirse. ${\displaystyle M}$ ${\displaystyle {\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle {\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}}$ ${\displaystyle I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}}$ ${\displaystyle M}$

Candès y Recht ^[3] definen la coherencia de una matriz con espacio columna un subespacio dimensional de como , donde es la proyección ortogonal sobre . La incoherencia afirma entonces que dada la descomposición en valores singulares de la matriz por , ${\displaystyle U}$ ${\displaystyle r-}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i}\|^{2}}$ ${\displaystyle P_{U}}$ ${\displaystyle U}$ ${\displaystyle U\Sigma V^{\dagger }}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle M}$

1. ${\displaystyle \mu (U),\;\mu (V)\leq \mu _{0}}$
2. Las entradas de tienen magnitudes limitadas superiormente por ${\displaystyle \sum _{k}u_{k}v_{k}^{\dagger }}$ ${\displaystyle \mu _{1}{\sqrt {\frac {r}{mn}}}}$

Para algunos . ${\displaystyle \mu _{0},\;\mu _{1}}$

Completamiento de matriz de bajo rango con ruido

En aplicaciones del mundo real, a menudo se observan solo unas pocas entradas corrompidas al menos por una pequeña cantidad de ruido. Por ejemplo, en el problema de Netflix, las calificaciones son inciertas. Candès y Plan ^[9] demostraron que es posible completar las muchas entradas faltantes de matrices grandes de bajo rango a partir de solo unas pocas muestras ruidosas mediante la minimización de la norma nuclear. El modelo ruidoso supone que observamos

${\displaystyle Y_{ij}=M_{ij}+Z_{ij},(i,j)\in \Omega ,}$

donde es un término de ruido. Nótese que el ruido puede ser estocástico o determinista. Alternativamente, el modelo puede expresarse como ${\displaystyle {Z_{ij}:(i,j)\in \Omega }}$

${\displaystyle P_{\Omega }(Y)=P_{\Omega }(M)+P_{\Omega }(Z),}$

donde es una matriz con entradas para suponer que para algún .Para recuperar la matriz incompleta, intentamos resolver el siguiente problema de optimización: ${\displaystyle Z}$ ${\displaystyle n\times n}$ ${\displaystyle Z_{ij}}$ ${\displaystyle (i,j)\in \Omega }$ ${\displaystyle \|P_{\Omega }(Z)\|_{F}\leq \delta }$ ${\displaystyle \delta >0}$

${\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&\|X\|_{*}\\&{\text{subject to}}&\|P_{\Omega }(X-Y)\|_{F}\leq \delta \\\end{aligned}}}$

Entre todas las matrices consistentes con los datos, encuentre la que tenga la norma nuclear mínima. Candès y Plan ^[9] han demostrado que esta reconstrucción es precisa. Han demostrado que cuando se produce una recuperación perfecta sin ruido, la compleción de la matriz es estable frente a las perturbaciones. El error es proporcional al nivel de ruido . Por lo tanto, cuando el nivel de ruido es pequeño, el error es pequeño. Aquí el problema de compleción de la matriz no obedece a la propiedad de isometría restringida (RIP). Para las matrices, la RIP supondría que el operador de muestreo obedece ${\displaystyle \delta }$

${\displaystyle (1-\delta )\|X\|_{F}^{2}\leq {\frac {1}{p}}\|P_{\Omega }(X)\|_{F}^{2}\leq (1+\delta )\|X\|_{F}^{2}}$

para todas las matrices con rango suficientemente pequeño y suficientemente pequeñas. Los métodos también son aplicables a problemas de recuperación de señales dispersas en los que el RIP no se cumple. ${\displaystyle X}$ ${\displaystyle \delta <1}$

Matriz de finalización de alto rango

La terminación de matrices de alto rango en general es NP-Hard . Sin embargo, con ciertas suposiciones, se pueden completar algunas matrices de alto rango incompletas o incluso matrices de rango completo.

Eriksson, Balzano y Nowak ^[10] han considerado el problema de completar una matriz con el supuesto de que las columnas de la matriz pertenecen a una unión de múltiples subespacios de bajo rango. Dado que las columnas pertenecen a una unión de subespacios, el problema puede verse como una versión de datos faltantes del problema de agrupamiento de subespacios . Sea una matriz cuyas columnas (completas) se encuentran en una unión de como máximo subespacios, cada uno de , y supongamos que . Eriksson, Balzano y Nowak ^[10] demostraron que, bajo supuestos moderados, cada columna de puede recuperarse perfectamente con alta probabilidad a partir de una versión incompleta siempre que al menos las entradas de se observen uniformemente al azar, con una constante que dependa de las condiciones de incoherencia habituales, la disposición geométrica de los subespacios y la distribución de las columnas sobre los subespacios. ${\displaystyle X}$ ${\displaystyle n\times N}$ ${\displaystyle k}$ ${\displaystyle rank\leq r<n}$ ${\displaystyle N\gg kn}$ ${\displaystyle X}$ ${\displaystyle CrN\log ^{2}(n)}$ ${\displaystyle X}$ ${\displaystyle C>1}$

El algoritmo implica varios pasos: (1) vecindarios locales; (2) subespacios locales; (3) refinamiento del subespacio; (4) compleción total de la matriz. Este método se puede aplicar a la compleción de la matriz de distancia de Internet y a la identificación de la topología.

Algoritmos para completar matrices de bajo rango

Se han propuesto varios algoritmos de finalización de matrices. ^[8] Estos incluyen el algoritmo basado en relajación convexa, ^[3] el algoritmo basado en gradiente, ^[11] y el algoritmo basado en minimización alternada. ^[12]

Relajación convexa

El problema de minimización de rangos es NP-hard . Un enfoque, propuesto por Candès y Recht, es formar una relajación convexa del problema y minimizar la norma nuclear (que da la suma de los valores singulares de ) en lugar de (que cuenta el número de valores singulares distintos de cero de ). ^{[3] Esto es análogo a minimizar la} norma L1 en lugar de la norma L0 para vectores. La relajación convexa se puede resolver utilizando programación semidefinida (SDP) notando que el problema de optimización es equivalente a ${\displaystyle \|M\|_{*}}$ ${\displaystyle M}$ ${\displaystyle {\text{rank}}(M)}$ ${\displaystyle M}$

${\displaystyle {\begin{aligned}&{\underset {W_{1},W_{2}}{\text{min}}}&&{\text{trace}}(W_{1})+{\text{trace}}(W_{2})\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix}W_{1}&X\\X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{aligned}}}$

La complejidad de utilizar SDP para resolver la relajación convexa es . Los solucionadores de última generación como SDPT3 solo pueden manejar matrices de tamaño de hasta 100 por 100 ^[13]. Un método alternativo de primer orden que resuelve aproximadamente la relajación convexa es el algoritmo de umbral de valor singular introducido por Cai, Candès y Shen. ^[13] ${\displaystyle O({\text{max}}(m,n)^{4})}$

Candès y Recht muestran, utilizando el estudio de variables aleatorias en espacios de Banach , que si el número de entradas observadas es del orden de (supongamos sin pérdida de generalidad ), el problema de minimización de rango tiene una solución única que también resulta ser la solución de su relajación convexa con probabilidad para alguna constante . Si el rango de es pequeño ( ), el tamaño del conjunto de observaciones se reduce al orden de . Estos resultados son casi óptimos, ya que el número mínimo de entradas que deben observarse para que el problema de compleción de matrices no esté subdeterminado es del orden de . ${\displaystyle \max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n}$ ${\displaystyle m<n}$ ${\displaystyle 1-{\frac {c}{n^{3}}}}$ ${\displaystyle c}$ ${\displaystyle M}$ ${\displaystyle r\leq {\frac {n^{0.2}}{\mu _{0}}}}$ ${\displaystyle \mu _{0}n^{1.2}r\log n}$ ${\displaystyle nr\log n}$

Este resultado ha sido mejorado por Candès y Tao. ^[6] Consiguen límites que difieren de los límites óptimos solo por factores polilogarítmicos reforzando los supuestos. En lugar de la propiedad de incoherencia, suponen la propiedad de incoherencia fuerte con parámetro . Esta propiedad establece que: ${\displaystyle \mu _{3}}$

1. ${\displaystyle |\langle e_{a},P_{U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'}|\leq \mu _{3}{\frac {\sqrt {r}}{m}}}$por y para ${\displaystyle a,a'\leq m}$ ${\displaystyle |\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}}$ ${\displaystyle b,b'\leq n}$
2. Las entradas de están limitadas en magnitud por ${\displaystyle \sum _{i}u_{i}v_{i}^{\dagger }}$ ${\displaystyle \mu _{3}{\sqrt {\frac {r}{mn}}}}$

Intuitivamente, la fuerte incoherencia de una matriz afirma que las proyecciones ortogonales de los vectores base estándar tienen magnitudes que tienen alta probabilidad si los vectores singulares se distribuyeran aleatoriamente. ^[7] ${\displaystyle U}$ ${\displaystyle U}$

Candès y Tao encuentran que cuando es y el número de entradas observadas es del orden de , el problema de minimización de rango tiene una solución única que también resulta ser la solución de su relajación convexa con probabilidad para alguna constante . Para arbitrario , el número de entradas observadas suficiente para que esta afirmación sea verdadera es del orden de ${\displaystyle r}$ ${\displaystyle O(1)}$ ${\displaystyle \mu _{3}^{4}n(\log n)^{2}}$ ${\displaystyle 1-{\frac {c}{n^{3}}}}$ ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle \mu _{3}^{2}nr(\log n)^{6}}$

Otro enfoque de relajación convexa ^[14] es minimizar la norma de Frobenius al cuadrado bajo una restricción de rango. Esto es equivalente a resolver

${\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&&\Vert X\Vert _{F}^{2}\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{Rank}}(X)\leq k.\end{aligned}}}$

Introduciendo una matriz de proyección ortogonal (que significa ) para modelar el rango de vía y tomando la relajación convexa de este problema, obtenemos el siguiente programa semidefinido ${\displaystyle Y}$ ${\displaystyle Y^{2}=Y,Y=Y'}$ ${\displaystyle X}$ ${\displaystyle X=YX,{\text{trace}}(Y)\leq k}$

${\displaystyle {\begin{aligned}&{\underset {X,Y,\theta }{\text{min}}}&&{\text{trace}}(\theta )\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{trace}}(Y)\leq k,0\preceq Y\preceq I\\&&&{\begin{pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}}$

Si Y es una matriz de proyección (es decir, tiene valores propios binarios) en esta relajación, entonces la relajación es estricta. De lo contrario, proporciona un límite inferior válido para el objetivo general. Además, se puede convertir en una solución factible con un objetivo (ligeramente) mayor redondeando los valores propios de Y con avidez. ^[14] Sorprendentemente, esta relajación convexa se puede resolver mediante la minimización alternada en X e Y sin resolver ningún SDP, y por lo tanto escala más allá de los límites numéricos típicos de los solucionadores SDP de última generación como SDPT3 o Mosek.

Este enfoque es un caso especial de una técnica de reformulación más general, que se puede aplicar para obtener un límite inferior válido en cualquier problema de rango bajo con un objetivo de matriz de trazas convexas. ^[15]

Descenso de gradiente

Keshavan, Montanari y Oh ^[11] consideran una variante de compleción de matriz donde se sabe que el rango de la matriz por , que se va a recuperar, es . Suponen un muestreo de Bernoulli de entradas, una relación de aspecto constante , una magnitud acotada de las entradas de (sea el límite superior ) y un número de condición constante (donde y son los valores singulares más grande y más pequeño de respectivamente). Además, suponen que se satisfacen las dos condiciones de incoherencia con y donde y son constantes. Sea una matriz que coincide en el conjunto de entradas observadas y es 0 en el resto. Luego proponen el siguiente algoritmo: ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle r}$ ${\displaystyle {\frac {m}{n}}}$ ${\displaystyle M}$ ${\displaystyle M_{\text{max}}}$ ${\displaystyle {\frac {\sigma _{1}}{\sigma _{r}}}}$ ${\displaystyle \sigma _{1}}$ ${\displaystyle \sigma _{r}}$ ${\displaystyle M}$ ${\displaystyle \mu _{0}}$ ${\displaystyle \mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}}$ ${\displaystyle \mu _{0}}$ ${\displaystyle \mu _{1}}$ ${\displaystyle M^{E}}$ ${\displaystyle M}$ ${\displaystyle E}$

1. Recorte eliminando todas las observaciones de las columnas con grado mayor que estableciendo las entradas en las columnas a 0. De manera similar, elimine todas las observaciones de las filas con grado mayor que . ${\displaystyle M^{E}}$ ${\displaystyle {\frac {2|E|}{n}}}$ ${\displaystyle {\frac {2|E|}{n}}}$
2. Proyectar sobre sus primeros componentes principales . Llamar a la matriz resultante . ${\displaystyle M^{E}}$ ${\displaystyle r}$ ${\displaystyle {\text{Tr}}(M^{E})}$
3. Resuelva donde es alguna función de regularización por descenso de gradiente con búsqueda de línea . Inicialice en donde . Establezca como alguna función que fuerza a permanecer incoherente durante el descenso de gradiente si y son incoherentes. ${\displaystyle \min _{X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\sum _{i,j\in E}(M_{ij}-(XSY^{\dagger })_{ij})^{2}+\rho G(X,Y)}$ ${\displaystyle G(X,Y)}$ ${\displaystyle X,\;Y}$ ${\displaystyle X_{0},\;Y_{0}}$ ${\displaystyle {\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }}$ ${\displaystyle G(X,Y)}$ ${\displaystyle X,\;Y}$ ${\displaystyle X_{0}}$ ${\displaystyle Y_{0}}$
4. Devuelve la matriz . ${\displaystyle XSY^{\dagger }}$

Los pasos 1 y 2 del algoritmo producen una matriz muy cercana a la matriz verdadera (medida por el error cuadrático medio (RMSE) ) con alta probabilidad. En particular, con probabilidad , para alguna constante . denota la norma de Frobenius . Nótese que no se necesita el conjunto completo de supuestos para que este resultado sea válido. La condición de incoherencia, por ejemplo, solo entra en juego en la reconstrucción exacta. Finalmente, aunque el recorte puede parecer contra-intuitivo ya que implica descartar información, asegura que la proyección sobre sus primeros componentes principales brinde más información sobre la matriz subyacente que sobre las entradas observadas. ${\displaystyle {\text{Tr}}(M^{E})}$ ${\displaystyle M}$ ${\displaystyle 1-{\frac {1}{n^{3}}}}$ ${\displaystyle {\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F}^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}}$ ${\displaystyle C}$ ${\displaystyle \|\cdot \|_{F}}$ ${\displaystyle M^{E}}$ ${\displaystyle r}$ ${\displaystyle M}$

En el Paso 3, el espacio de matrices candidatas se puede reducir notando que el problema de minimización interna tiene la misma solución para que para donde y son ortonormales por matrices. Luego, se puede realizar el descenso de gradiente sobre el producto vectorial de dos variedades de Grassman . Si y el conjunto de entradas observado está en el orden de , la matriz devuelta por el Paso 3 es exactamente . Entonces, el algoritmo es óptimo en cuanto al orden, ya que sabemos que para que el problema de compleción de matrices no esté subdeterminado, el número de entradas debe estar en el orden de . ${\displaystyle X,\;Y}$ ${\displaystyle (X,Y)}$ ${\displaystyle (XQ,YR)}$ ${\displaystyle Q}$ ${\displaystyle R}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r\ll m,\;n}$ ${\displaystyle nr\log n}$ ${\displaystyle M}$ ${\displaystyle nr\log n}$

Minimización por mínimos cuadrados alternos

La minimización alternada representa un enfoque ampliamente aplicable y empíricamente exitoso para encontrar matrices de bajo rango que se ajusten mejor a los datos dados. Por ejemplo, para el problema de completar matrices de bajo rango, se cree que este método es uno de los más precisos y eficientes, y formó un componente principal de la propuesta ganadora en el problema de Netflix. En el enfoque de minimización alternada, la matriz objetivo de bajo rango se escribe en forma bilineal :

${\displaystyle X=UV^{T}}$;

El algoritmo alterna entonces entre encontrar el mejor y el mejor . Si bien el problema general no es convexo, cada subproblema es típicamente convexo y se puede resolver de manera eficiente. Jain, Netrapalli y Sanghavi ^[12] han brindado una de las primeras garantías para el desempeño de la minimización alternada tanto para la terminación de matrices como para la detección de matrices. ${\displaystyle U}$ ${\displaystyle V}$

El algoritmo de minimización alternada puede verse como una forma aproximada de resolver el siguiente problema no convexo:

${\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}$

El algoritmo AltMinComplete propuesto por Jain, Netrapalli y Sanghavi se enumera aquí: ^[12]

1. Entrada : conjunto observado , valores ${\displaystyle \Omega }$ ${\displaystyle P_{\Omega }(M)}$
2. Partición en subconjuntos con cada elemento perteneciente a uno de ellos con igual probabilidad (muestreo con reemplazo) ${\displaystyle \Omega }$ ${\displaystyle 2T+1}$ ${\displaystyle \Omega _{0},\cdots ,\Omega _{2T}}$ ${\displaystyle \Omega }$ ${\displaystyle \Omega _{t}}$
3. ${\displaystyle {\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)}$es decir, vectores singulares superiores izquierdos de ${\displaystyle k}$ ${\displaystyle {\frac {1}{p}}P_{\Omega _{0}}(M)}$
4. Recorte : Establezca todos los elementos que tengan magnitud mayor que cero y ortonormalice las columnas de ${\displaystyle {\hat {U}}^{0}}$ ${\displaystyle {\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}}$ ${\displaystyle {\hat {U}}^{0}}$
5. para hacer ${\displaystyle t=0,\cdots ,T-1}$
6. ${\displaystyle \quad {\hat {V}}^{t+1}\leftarrow {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T}-M)\|_{F}^{2}}$
7. ${\displaystyle \quad {\hat {U}}^{t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\times k}}\|P_{\Omega _{T+t+1}}(U({\hat {V}}^{t+1})^{T}-M)\|_{F}^{2}}$
8. fin para
9. Devolver ${\displaystyle X={\hat {U}}^{T}({\hat {V}}^{T})^{T}}$

Demostraron que al observar entradas aleatorias de una matriz incoherente , el algoritmo AltMinComplete puede recuperarse en pasos. En términos de complejidad de muestra ( ), teóricamente, la minimización alternada puede requerir una relajación convexa mayor que la relajación convexa. Sin embargo, empíricamente parece que no es el caso, lo que implica que los límites de complejidad de muestra se pueden ajustar aún más. En términos de complejidad temporal, demostraron que AltMinComplete necesita tiempo ${\displaystyle |\Omega |=O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle O(\log(1/\epsilon ))}$ ${\displaystyle |\Omega |}$ ${\displaystyle \Omega }$

${\displaystyle O(|\Omega |k^{2}\log(1/\epsilon ))}$.

Vale la pena señalar que, si bien los métodos basados ​​en la relajación convexa tienen un análisis riguroso, los algoritmos basados ​​en la minimización alternada son más exitosos en la práctica. ^{[ cita requerida ]}

Aplicaciones

^{Candès y Plan [9]} resumen a continuación varias aplicaciones de la terminación de matrices:

Filtrado colaborativo

El filtrado colaborativo es la tarea de hacer predicciones automáticas sobre los intereses de un usuario mediante la recopilación de información sobre gustos de muchos usuarios. Empresas como Apple, Amazon, Barnes and Noble y Netflix intentan predecir las preferencias de sus usuarios a partir de un conocimiento parcial. En este tipo de problemas de compleción de matrices, la matriz completa desconocida suele considerarse de bajo rango porque solo unos pocos factores contribuyen normalmente a los gustos o preferencias de un individuo.

Identificación del sistema

En control, uno quisiera ajustar un modelo de espacio de estados lineal invariante en el tiempo y de tiempo discreto.

${\displaystyle {\begin{aligned}x(t+1)&=Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aligned}}}$

a una secuencia de entradas y salidas . El vector es el estado del sistema en el momento y es el orden del modelo del sistema. A partir del par entrada/salida, se desea recuperar las matrices y el estado inicial . Este problema también puede verse como un problema de compleción de matriz de bajo rango. ${\displaystyle u(t)\in \mathbb {R} ^{m}}$ ${\displaystyle y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N}$ ${\displaystyle x(t)\in \mathbb {R} ^{n}}$ ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle A,B,C,D}$ ${\displaystyle x(0)}$

Localización de Internet de las cosas (IoT)

El problema de localización (o posicionamiento global) surge de manera natural en las redes de sensores de IoT. El problema consiste en recuperar el mapa de sensores en el espacio euclidiano a partir de un conjunto local o parcial de distancias por pares. Por lo tanto, se trata de un problema de completitud de matriz con rango dos si los sensores están ubicados en un plano 2-D y tres si están en un espacio 3-D. ^[16]

Recuperación de las redes sociales

La mayoría de las redes sociales del mundo real tienen matrices de distancia de bajo rango. Cuando no podemos medir la red completa, lo que puede deberse a razones como nodos privados, almacenamiento limitado o recursos computacionales, solo conocemos una fracción de las entradas de distancia. Las redes criminales son un buen ejemplo de dichas redes. La finalización de matrices de bajo rango se puede utilizar para recuperar estas distancias no observadas. ^[17]

Véase también

• Regularización de matrices
• Premio Netflix
• Filtrado colaborativo
• Identificación del sistema
• Optimización convexa
• Imputación

Referencias

1. Johnson, Charles R. (1990). "Problemas de compleción de matrices: un estudio". Teoría de matrices y aplicaciones . Actas de simposios sobre matemáticas aplicadas. Vol. 40. págs. 171–198. doi :10.1090/psapm/040/1059486. ISBN 9780821801543.
2. Laurent, Monique (2008). "Problemas de terminación de matrices". Enciclopedia de optimización . Vol. 3. págs. 221–229. doi :10.1007/978-0-387-74759-0_355. ISBN . 978-0-387-74758-3.
3. Candès, EJ; Recht, B. (2009). "Completado exacto de matrices mediante optimización convexa". Fundamentos de las matemáticas computacionales . 9 (6): 717–772. arXiv : 0805.4471 . doi : 10.1007/s10208-009-9045-5 .
4. Recht, B. (2009). "Un enfoque más simple para completar matrices" (PDF) . Journal of Machine Learning Research . 12 : 3413–3430. arXiv : 0910.0651 . Código Bibliográfico :2009arXiv0910.0651R.
5. Xu, Zhiqiang (2018). "El número de medición mínimo para la recuperación de la matriz de bajo rango". Análisis armónico computacional y aplicado . 44 (2): 497–508. arXiv : 1505.07204 . doi :10.1016/j.acha.2017.01.005. S2CID  11990443.
6. Candès, EJ; Tao, T. (2010). "El poder de la relajación convexa: compleción de matriz casi óptima". IEEE Transactions on Information Theory . 56 (5): 2053–2080. arXiv : 0903.1476 . doi :10.1109/TIT.2010.2044061. S2CID  1255437.
7. Tao, T. (10 de marzo de 2009). "El poder de la relajación convexa: compleción de matriz casi óptima". Novedades .
8. Nguyen, LT; Kim, J.; Shim, B. (10 de julio de 2019). "Completado de matrices de bajo rango: un estudio contemporáneo". IEEE Access . 7 (1): 94215–94237. arXiv : 1907.11705 . Código Bibliográfico :2019arXiv190711705N. doi :10.1109/ACCESS.2019.2928130. S2CID  198930899.
9. Candès, EJ; Plan, Y. (2010). "Completado de matrices con ruido". Actas del IEEE . 98 (6): 925–936. arXiv : 0903.3131 . doi :10.1109/JPROC.2009.2035722. S2CID  109721.
10. Eriksson, B.; Balzano, L.; Nowak, R. (2011). "Completado de matriz de alto rango y agrupamiento de subespacios con datos faltantes". arXiv : 1112.5629 [cs.IT].
11. Keshavan, RH; Montanari, A.; Oh, S. (2010). "Completar la matriz a partir de unas pocas entradas". IEEE Transactions on Information Theory . 56 (6): 2980–2998. arXiv : 0901.3150 . doi :10.1109/TIT.2010.2046205. S2CID  53504.
12. Jain, P.; Netrapalli, P.; Sanghavi, S. (2013). "Completado de matrices de bajo rango mediante minimización alternada". Actas del 45.º simposio anual de la ACM sobre teoría de la computación . ACM. págs. 665–674. arXiv : 1212.0467 . doi :10.1145/2488608.2488693. ISBN . 978-1-4503-2029-0. Número de identificación del sujeto  447011.
13. Cai, J.-F.; Candès, EJ; Shen, Z. (2010). "Un algoritmo de umbralización de valores singulares para completar matrices". Revista SIAM sobre optimización . 20 (4): 1956–1982. arXiv : 0810.3286 . doi :10.1137/080738970. S2CID  1254778.
14. Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2021). "Optimización cónica de proyección mixta: un nuevo paradigma para modelar restricciones de rango". Investigación de operaciones . 70 (6): 3321–3344. arXiv : 2009.10395 . doi :10.1287/opre.2021.2182. S2CID  221836263.
15. Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2021). "Una nueva perspectiva sobre la optimización de bajo rango". Optimización en línea . arXiv : 2105.05947 .
16. Nguyen, LT; Kim, J.; Kim, S.; Shim, B. (2019). "Localización de redes de IoT mediante la finalización de matriz de bajo rango". IEEE Transactions on Communications . 67 (8): 5833–5847. doi :10.1109/TCOMM.2019.2915226. S2CID  164605437.
17. Mahindre, G.; Jayasumana, AP; Gajamannage, K.; Paffenroth, R. (2019). "Sobre el muestreo y la recuperación de la topología de redes sociales dirigidas: un enfoque basado en la finalización de matrices de bajo rango". 2019 IEEE 44th Conference on Local Computer Networks (LCN) . IEEE. págs. 324–331. doi :10.1109/LCN44214.2019.8990707. ISBN 978-1-7281-1028-8.S2CID211206354  .​