Finalización de la matriz

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 esté subdeterminado .

El problema de minimización de rango es NP-difícil . Un enfoque, propuesto por Candès y Recht, consiste en formar una relajación convexa del problema y minimizar la norma nuclear.${\displaystyle \|M\|_{*}}$(que da la suma de los valores singulares de${\displaystyle M}$) en lugar de${\displaystyle {\text{rank}}(M)}$(que cuenta el número de valores singulares distintos de cero de${\displaystyle M}$). ^{[ 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) al observar que el problema de optimización es equivalente a

${\displaystyle {\begin{aligned}&\min \limits _{W_{1},W_{2}}&&\operatorname {trace} (W_{1})+\operatorname {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 usar SDP para resolver la relajación convexa es${\displaystyle O({\text{max}}(m,n)^{4})}$Los solucionadores de última generación como SDPT3 solo pueden manejar matrices de tamaño hasta 100 x 100. ^{[ 15 ]} Un método alternativo de primer orden que resuelve aproximadamente la relajación convexa es el algoritmo de umbralización de valores singulares introducido por Cai, Candès y Shen. ^{[ 15 ]}

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${\displaystyle \max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n}$(supongamos sin pérdida de generalidad)${\displaystyle m<n}$), 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${\displaystyle 1-{\frac {c}{n^{3}}}}$por alguna constante${\displaystyle c}$Si el rango de${\displaystyle M}$es pequeño (${\displaystyle r\leq {\frac {n^{0.2}}{\mu _{0}}}}$), el tamaño del conjunto de observaciones se reduce al orden de${\displaystyle \mu _{0}n^{1.2}r\log n}$Estos resultados son casi óptimos, ya que el número mínimo de entradas que deben observarse para que el problema de completación de matrices no esté subdeterminado es del orden de${\displaystyle nr\log n}$.

Este resultado ha sido mejorado por Candès y Tao. ^{[ 6 ]} Logran cotas que difieren de las cotas óptimas solo por factores polilogarítmicos al fortalecer los supuestos. En lugar de la propiedad de incoherencia, asumen la propiedad de incoherencia fuerte con parámetro${\displaystyle \mu _{3}}$Esta propiedad establece que:

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

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

Candès y Tao descubren que cuando${\displaystyle r}$es${\displaystyle O(1)}$y el número de entradas observadas es del orden de${\displaystyle \mu _{3}^{4}n(\log n)^{2}}$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${\displaystyle 1-{\frac {c}{n^{3}}}}$por alguna constante${\displaystyle c}$. Por arbitrario${\displaystyle r}$, el número de entradas observadas suficientes para que esta afirmación sea cierta es del orden de${\displaystyle \mu _{3}^{2}nr(\log n)^{6}}$

Otro enfoque de relajación convexa ^{[ 16 ]} consiste en minimizar la norma cuadrada de Frobenius bajo una restricción de rango. Esto es equivalente a resolver

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

Al introducir una matriz de proyección ortogonal${\displaystyle Y}$(significado${\displaystyle Y^{2}=Y,Y=Y'}$) para modelar el rango de${\displaystyle X}$a través de${\displaystyle X=YX,{\text{trace}}(Y)\leq k}$y tomando la relajación convexa de este problema, obtenemos el siguiente programa semidefinido.

${\displaystyle {\begin{aligned}&\min \limits _{X,Y,\theta }&&{\text{trace}}(\theta )\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {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 ajustada. De lo contrario, proporciona una cota inferior válida 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 de forma voraz. ^{[ 16 ]} Cabe destacar que esta relajación convexa se puede resolver mediante la minimización alternada de 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 puede aplicarse para obtener una cota inferior válida en cualquier problema de bajo rango con una función objetivo convexa de traza. ^{[ 17 ]}

Keshavan, Montanari y Oh ^{[ 11 ]} consideran una variante de completación de matrices donde el rango de la${\displaystyle m}$por${\displaystyle n}$matriz${\displaystyle M}$, que debe ser recuperado, se sabe que es${\displaystyle r}$Asumen un muestreo de Bernoulli de las entradas y una relación de aspecto constante .${\displaystyle {\frac {m}{n}}}$, magnitud limitada de entradas de${\displaystyle M}$(sea el límite superior${\displaystyle M_{\text{max}}}$), y número de condición constante${\displaystyle {\frac {\sigma _{1}}{\sigma _{r}}}}$(dónde${\displaystyle \sigma _{1}}$y${\displaystyle \sigma _{r}}$son los valores singulares más grandes y más pequeños de${\displaystyle M}$respectivamente). Además, suponen que se cumplen las dos condiciones de incoherencia con${\displaystyle \mu _{0}}$y${\displaystyle \mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}}$dónde${\displaystyle \mu _{0}}$y${\displaystyle \mu _{1}}$son constantes. Sea${\displaystyle M^{E}}$ser una matriz que coincida${\displaystyle M}$en el set${\displaystyle E}$de entradas observadas y es 0 en los demás casos. A continuación, proponen el siguiente algoritmo:

1. Recortar${\displaystyle M^{E}}$eliminando todas las observaciones de columnas con grado mayor que${\displaystyle {\frac {2|E|}{n}}}$estableciendo las entradas en las columnas a 0. De manera similar, elimine todas las observaciones de las filas con un grado mayor que${\displaystyle {\frac {2|E|}{n}}}$.
2. Proyecto${\displaystyle M^{E}}$en su primera${\displaystyle r}$componentes principales . Llamar a la matriz resultante${\displaystyle {\text{Tr}}(M^{E})}$.
3. Resolver${\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)}$dónde${\displaystyle G(X,Y)}$es alguna función de regularización por descenso de gradiente con búsqueda lineal . Inicializar${\displaystyle X,\;Y}$en${\displaystyle X_{0},\;Y_{0}}$dónde${\displaystyle {\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }}$. Colocar${\displaystyle G(X,Y)}$como alguna función forzando${\displaystyle X,\;Y}$permanecer incoherente durante todo el descenso de gradiente si${\displaystyle X_{0}}$y${\displaystyle Y_{0}}$son incoherentes.
4. Devuelve la matriz${\displaystyle XSY^{\dagger }}$.

Los pasos 1 y 2 del algoritmo producen una matriz${\displaystyle {\text{Tr}}(M^{E})}$muy cerca de la matriz verdadera${\displaystyle M}$(medido por el error cuadrático medio (RMSE) ) con alta probabilidad. En particular, con probabilidad${\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}}}}$por alguna constante${\displaystyle C}$. ${\displaystyle \|\cdot \|_{F}}$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 contraintuitivo, ya que implica descartar información, garantiza la proyección.${\displaystyle M^{E}}$en su primera${\displaystyle r}$Los componentes principales brindan más información sobre la matriz subyacente.${\displaystyle M}$que sobre las entradas observadas.

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

La minimización alternada representa un enfoque ampliamente aplicable y empíricamente exitoso para encontrar matrices de bajo rango que mejor se ajusten 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 constituyó un componente principal de la entrada 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 luego alterna entre encontrar el mejor${\displaystyle U}$y el mejor${\displaystyle V}$Si bien el problema general no es convexo, cada subproblema suele ser convexo y puede resolverse de manera eficiente. Jain, Netrapalli y Sanghavi ^{[ 12 ]} brindaron una de las primeras garantías de rendimiento para la minimización alternada tanto para la completación de matrices como para la detección de matrices.

El algoritmo de minimización alternada puede considerarse 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${\displaystyle \Omega }$, valores${\displaystyle P_{\Omega }(M)}$
2. Dividir${\displaystyle \Omega }$en${\displaystyle 2T+1}$subconjuntos${\displaystyle \Omega _{0},\cdots ,\Omega _{2T}}$con cada elemento de${\displaystyle \Omega }$perteneciente a uno de los${\displaystyle \Omega _{t}}$con igual probabilidad (muestreo con reemplazo)
3. ${\displaystyle {\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)}$es decir, superior-${\displaystyle k}$vectores singulares izquierdos de${\displaystyle {\frac {1}{p}}P_{\Omega _{0}}(M)}$
4. Recorte : Establecer todos los elementos de${\displaystyle {\hat {U}}^{0}}$que tienen una magnitud mayor que${\displaystyle {\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}}$a cero y ortonormalizar las columnas de${\displaystyle {\hat {U}}^{0}}$
5. para${\displaystyle t=0,\cdots ,T-1}$hacer
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}}$

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

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

Cabe destacar que, si bien los métodos basados ​​en la relajación convexa cuentan con un análisis riguroso, los algoritmos basados ​​en la minimización alternada tienen más éxito en la práctica.

Una adición sencilla a los algoritmos basados ​​en factorización es la recuperación de matrices de Gauss-Newton (GNMR). ^{[ 13 ]} De forma similar a la minimización alternada, GNMR aborda el objetivo de completar matrices de bajo rango factorizadas:

${\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}}}$

Inspirado en el enfoque clásico de Gauss-Newton , GNMR linealiza la función objetivo. Esto da como resultado el siguiente subproblema de mínimos cuadrados lineales:

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

Partiendo de una inicialización${\displaystyle (U_{0},V_{0})}$GNMR resuelve iterativamente el subproblema de mínimos cuadrados lineales y actualiza${\displaystyle U_{t+1}\leftarrow U_{t}+\Delta U,}$${\displaystyle V_{t+1}\leftarrow V_{t}+\Delta V}$hasta la convergencia. Dado que el subproblema de mínimos cuadrados tiene un rango deficiente, GNMR selecciona la solución de norma mínima, preservando así el equilibrio entre${\displaystyle U}$y${\displaystyle V}$Sin regularización explícita. Se ha demostrado que este algoritmo cuenta con sólidas garantías teóricas. Además, a pesar de su simplicidad, los resultados empíricos indican que GNMR supera a varios algoritmos populares, especialmente cuando las observaciones son escasas o la matriz está mal condicionada.

En aplicaciones como los sistemas de recomendación, donde las entradas de la matriz son discretas (por ejemplo, calificaciones enteras del 1 al 5), incorporar esta discreción al problema de completación de la matriz puede mejorar el rendimiento. Los enfoques de completación de matrices que tienen en cuenta la discreción introducen un regularizador que fomenta que las entradas de la matriz completada se alineen con un alfabeto discreto finito.

Un método temprano en este ámbito utilizó el${\displaystyle \ell _{1}}$-norma como una relajación convexa de la${\displaystyle \ell _{0}}$-norma para imponer discreción, lo que permite una optimización eficiente utilizando métodos de gradiente proximal. Partiendo de esto, Führling et al. (2023) ^{[ 14 ]} reemplaza la${\displaystyle \ell _{1}}$-norma con una aproximación continua y diferenciable de la${\displaystyle \ell _{0}}$-norma, lo que hace que el problema sea más manejable y mejora el rendimiento.

El problema de completación de matrices con consideración de la discretización se puede formular como:

${\displaystyle {\underset {{\boldsymbol {X}}\in \mathbb {R} ^{m\times n}}{\arg \min }}\,f({\boldsymbol {X}})+\lambda g({\boldsymbol {X}})+\zeta r({\boldsymbol {X}}\mid 0),}$

dónde:

• ${\displaystyle ({\boldsymbol {X}})={\frac {1}{2}}\left\|P_{\Omega }({\boldsymbol {X}}-{\boldsymbol {O}})\right\|_{F}^{2}}$garantiza la fidelidad a las entradas observadas, con${\displaystyle P_{\Omega }}$como la proyección sobre el conjunto observado${\displaystyle \Omega }$y${\displaystyle {\boldsymbol {O}}}$como la matriz observada.
• ${\displaystyle g({\boldsymbol {X}})=\|{\boldsymbol {X}}\|_{*}}$es la norma nuclear para imponer una estructura de bajo rango.
• ${\displaystyle r({\boldsymbol {X}}\mid 0)=\sum _{k=1}^{|{\mathcal {A}}|}\left\|\operatorname {vec} _{\overline {\Omega }}({\boldsymbol {X}})-a_{k}\mathbf {1} \right\|_{0}}$es el regularizador de espacio discreto, con${\displaystyle {\mathcal {A}}}$siendo el alfabeto discreto (por ejemplo, {1, 2, 3, 4, 5}) y${\displaystyle {\overline {\Omega }}}$el conjunto de entradas no observadas.

Para resolver este problema no convexo,${\displaystyle \ell _{0}}$La norma se aproxima mediante una función continua . Esta aproximación se convexifica utilizando programación fraccionaria , transformando el problema en una serie de subproblemas convexos.

El algoritmo actualiza iterativamente la estimación de la matriz aplicando operaciones proximales al regularizador de espacio discreto y umbralización de valores singulares para imponer la restricción de rango bajo. Inicializando el proceso con la solución de la${\displaystyle \ell _{1}}$El método basado en la norma puede acelerar la convergencia. Los resultados de la simulación, probados en conjuntos de datos como MovieLens-100k, demuestran que este método supera a ambos.${\displaystyle \ell _{1}}$-predecesor basado en normas y otras técnicas de vanguardia, particularmente cuando la proporción de entradas observadas es baja (por ejemplo, del 20% al 60%). ^{[ 14 ]}

El filtrado colaborativo consiste en realizar predicciones automáticas sobre los intereses de un usuario mediante la recopilación de información sobre sus preferencias de múltiples usuarios. Empresas como Apple, Amazon, Barnes & Noble y Netflix intentan predecir las preferencias de sus usuarios a partir de información parcial. En este tipo de problemas de compleción de matrices, la matriz completa desconocida suele considerarse de bajo rango, ya que solo unos pocos factores contribuyen a los gustos o preferencias de un individuo.

En el control, se desearía 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${\displaystyle u(t)\in \mathbb {R} ^{m}}$y resultados${\displaystyle y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N}$. El vector${\displaystyle x(t)\in \mathbb {R} ^{n}}$es el estado del sistema en el momento${\displaystyle t}$y${\displaystyle n}$es el orden del modelo del sistema. A partir del par entrada/salida, se desearía recuperar las matrices${\displaystyle A,B,C,D}$y el estado inicial${\displaystyle x(0)}$Este problema también puede considerarse un problema de completación de matrices de bajo rango.

El problema de localización (o posicionamiento global) surge de forma 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 entre pares de sensores. Por lo tanto, se trata de un problema de completación de matrices de rango dos si los sensores se encuentran en un plano 2D y de rango tres si se encuentran en un espacio 3D. ^{[ 18 ]}

La mayoría de las redes sociales del mundo real tienen matrices de distancia de bajo rango. Cuando no podemos medir la red completa, debido a factores como nodos privados, almacenamiento limitado o recursos computacionales insuficientes, solo conocemos una fracción de las distancias. Las redes criminales son un buen ejemplo de este tipo de redes. La completación de matrices de bajo rango puede utilizarse para recuperar estas distancias no observadas. ^{[ 19 ]}