En matemáticas, la aproximación de rango bajo es un problema de minimización , en el que la función de costo mide el ajuste entre una matriz dada (los datos) y una matriz de aproximación (la variable de optimización), sujeto a la restricción de que la matriz de aproximación tiene rango reducido . El problema se utiliza para modelado matemático y compresión de datos . La restricción de rango está relacionada con una restricción en la complejidad de un modelo que se ajusta a los datos. En las aplicaciones, a menudo existen otras restricciones en la matriz de aproximación además de la restricción de rango, por ejemplo, la no negatividad y la estructura de Hankel .
La aproximación de rango bajo está estrechamente relacionada con:
Definición
Dado
- especificación de estructura ,
- vector de parámetros de estructura ,
- norma , y
- rango deseado ,
Aplicaciones
- Identificación del sistema lineal , en cuyo caso la matriz de aproximación está estructurada en Hankel . [1] [2]
- Aprendizaje automático , en cuyo caso la matriz de aproximación está estructurada de forma no lineal. [3]
- Sistemas de recomendación , en cuyo caso la matriz de datos tiene valores perdidos y la aproximación es categórica .
- Completar la matriz de distancia , en cuyo caso hay una restricción de definición positiva.
- Procesamiento del lenguaje natural , en cuyo caso la aproximación no es negativa .
- Álgebra informática , en cuyo caso la aproximación está estructurada por Sylvester .
Problema básico de aproximación de rango bajo
El problema no estructurado con el ajuste medido por la norma de Frobenius , es decir,
tiene solución analítica en términos de la descomposición del valor singular de la matriz de datos. El resultado se denomina lema de aproximación de matrices o teorema de Eckart-Young-Mirsky . [4] Deja
ser la descomposición en valor singular de y partición , , y como sigue:
dónde es , es , y es . Entonces el rango- matriz, obtenida de la descomposición de valores singulares truncados
es tal que
El minimizador es único si y solo si .
Prueba del teorema de Eckart-Young-Mirsky (para norma espectral )
Dejar ser una matriz real (posiblemente rectangular) con . Suponer que
es la descomposición del valor singular de. Recordar que y son matrices ortogonales , y es un matriz diagonal con entradas tal que .
Afirmamos que el mejor rango aproximación a en la norma espectral, denotado por , es dado por
dónde y denotar el a columna de y , respectivamente.
Primero, tenga en cuenta que tenemos
Por lo tanto, debemos demostrar que si dónde y tengo columnas entonces .
Desde posee columnas, entonces debe haber una combinación lineal no trivial de la primera columnas de , es decir,
tal que . Sin pérdida de generalidad, podemos escalar así que eso o equivalente) . Por lo tanto,
El resultado sigue tomando la raíz cuadrada de ambos lados de la desigualdad anterior.
Prueba del teorema de Eckart-Young-Mirsky (para la norma de Frobenius )
Dejar ser una matriz real (posiblemente rectangular) con . Suponer que
es la descomposición del valor singular de.
Afirmamos que el mejor rango aproximación a en la norma de Frobenius, denotado por , es dado por
dónde y denotar el a columna de y , respectivamente.
Primero, tenga en cuenta que tenemos
Por lo tanto, debemos demostrar que si dónde y tengo columnas entonces
Por la desigualdad del triángulo con la norma espectral, si luego . Suponer y respectivamente denotan el rango aproximación a y por el método SVD descrito anteriormente. Entonces, para cualquier
Desde , Cuándo y llegamos a la conclusión de que para
Por lo tanto,
según sea necesario.
Problemas de aproximación ponderados de rango bajo
La norma de Frobenius pondera uniformemente todos los elementos del error de aproximación . Se puede tener en cuenta el conocimiento previo sobre la distribución de los errores considerando el problema de aproximación ponderado de rango bajo
dónde vectoriza la matriz columna sabia y es una matriz de peso positiva (semi) definida dada.
El problema de aproximación general ponderado de bajo rango no admite una solución analítica en términos de la descomposición del valor singular y se resuelve mediante métodos de optimización local, que no garantizan que se encuentre una solución globalmente óptima.
En caso de ponderaciones no correlacionadas, el problema de aproximación ponderado de rango bajo también se puede formular de esta manera: [5] [6] para una matriz no negativa y una matriz queremos minimizar sobre matrices, , de rango como máximo .
Entrada sabia problemas de aproximación de rango bajo
Dejar . Para, el algoritmo más rápido se ejecuta en hora,. [7] [8] Una de las ideas importantes que se han utilizado se llama Oblivious Subpace Embedding (OSE), fue propuesta por primera vez por Sarlos. [9]
Para , se sabe que esta norma L1 de entrada es más robusta que la norma Frobenius en presencia de valores atípicos y está indicada en modelos donde las suposiciones gaussianas sobre el ruido pueden no aplicarse. Es natural buscar minimizar. [10] Para y , hay algunos algoritmos con garantías demostrables. [11] [12]
Problema de aproximación de rango bajo a distancia
Dejar y ser dos conjuntos de puntos en un espacio métrico arbitrario. Dejar representar el matriz donde . Dichas matrices de distancias se calculan comúnmente en paquetes de software y tienen aplicaciones para aprender múltiples imágenes, reconocimiento de escritura a mano y despliegue multidimensional. En un intento por reducir el tamaño de su descripción, [13] [14] uno puede estudiar la aproximación de rango bajo de tales matrices.
Problema de aproximación de rango bajo distribuido / en streaming
Los problemas de aproximación de rango bajo en la configuración distribuida y de transmisión se han considerado en. [15]
Representaciones de imágenes y kernel de las restricciones de rango
Usando las equivalencias
y
el problema de aproximación ponderado de rango bajo se vuelve equivalente a los problemas de optimización de parámetros
y
dónde es la matriz de identidad del tamaño.
Algoritmo de proyecciones alternas
La representación de la imagen de la restricción de rango sugiere un método de optimización de parámetros en el que la función de costo se minimiza alternativamente sobre una de las variables ( o ) con el otro fijo. Aunque la minimización simultánea sobre ambos y es un problema de optimización biconvexo difícil , la minimización sobre una de las variables por sí sola es un problema de mínimos cuadrados lineales y se puede resolver de manera global y eficiente.
El algoritmo de optimización resultante (llamado proyecciones alternas) es globalmente convergente con una tasa de convergencia lineal a una solución localmente óptima del problema de aproximación ponderado de rango bajo. Valor inicial para el (o ) debe darse el parámetro. La iteración se detiene cuando se cumple una condición de convergencia definida por el usuario.
Implementación de Matlab del algoritmo de proyecciones alternas para la aproximación ponderada de rango bajo:
función [dh, f] = wlra_ap ( d, w, p, tol, maxiter ) [ m , n ] = tamaño ( d ); r = tamaño ( p , 2 ); f = inf ; para i = 2 : maxiter % de minimización sobre L bp = kron ( ojo ( n ), p ); vl = ( bp ' * w * bp ) \ bp ' * w * d (:); l = remodelar ( vl , r , n ); % de minimización sobre P bl = kron ( l ' , ojo ( m )); vp = ( bl ' * w * bl ) \ bl ' * w * d (:); p = remodelar ( vp , m , r ); % comprobar condición de salida dh = p * l ; dd = d - dh ; f ( i ) = dd (:) ' * w * dd (:); si abs ( f ( i - 1 ) - f ( i )) < tol , break , end fin de
Algoritmo de proyecciones variables
El algoritmo de proyecciones alternas aprovecha el hecho de que el problema de aproximación de rango bajo, parametrizado en la forma de imagen, es bilineal en las variables o . La naturaleza bilineal del problema se utiliza efectivamente en un enfoque alternativo, llamado proyecciones variables. [dieciséis]
Considere nuevamente el problema de aproximación de rango bajo ponderado, parametrizado en la forma de imagen. Minimización con respecto a la variable (un problema lineal de mínimos cuadrados) conduce a la expresión de forma cerrada del error de aproximación en función de
Por tanto, el problema original es equivalente al problema de mínimos cuadrados no lineales de minimizar con respecto a . Para ello, se pueden utilizar métodos de optimización estándar, por ejemplo, el algoritmo de Levenberg-Marquardt .
Implementación de Matlab del algoritmo de proyecciones variables para la aproximación ponderada de rango bajo:
función [dh, f] = wlra_varpro ( d, w, p, tol, maxiter ) prob = optimset (); prob . solucionador = 'lsqnonlin' ; prob . opciones = optimset ( 'MaxIter' , maxiter , 'TolFun' , tol ); prob . x0 = p ; prob . objetivo = @ ( p ) cost_fun ( p , d , w ); [ p , f ] = lsqnonlin ( prob ); [ f , vl ] = cost_fun ( p , d , w ); dh = p * remodelar ( vl , tamaño ( p , 2 ), tamaño ( d , 2 )); función [f, vl] = cost_fun ( p, d, w ) bp = kron ( ojo ( tamaño ( d , 2 )), p ); vl = ( bp ' * w * bp ) \ bp ' * w * d (:); f = d (:) ' * w * ( d (:) - bp * vl );
El enfoque de proyecciones variables se puede aplicar también a problemas de aproximación de rango bajo parametrizados en forma de núcleo. El método es efectivo cuando el número de variables eliminadas es mucho mayor que el número de variables de optimización que quedan en la etapa de minimización de mínimos cuadrados no lineales. Tales problemas ocurren en la identificación del sistema, parametrizado en forma de kernel, donde las variables eliminadas son la trayectoria aproximada y las variables restantes son los parámetros del modelo. En el contexto de sistemas lineales invariantes en el tiempo , el paso de eliminación es equivalente al suavizado de Kalman .
Una variante: aproximación de rango bajo restringida por convexidad
Por lo general, queremos que nuestra nueva solución no solo sea de bajo rango, sino que también satisfaga otras restricciones convexas debido a los requisitos de la aplicación. Nuestro problema interesado sería el siguiente,
Este problema tiene muchas aplicaciones del mundo real, incluida la recuperación de una buena solución de una relajación inexacta (programación semidefinida). Si una restricción adicionales lineal, como requerimos que todos los elementos no sean negativos, el problema se llama aproximación estructurada de rango bajo. [17] La forma más general se denomina aproximación de rango bajo restringida por convexidad.
Este problema es útil para resolver muchos problemas. Sin embargo, es un desafío debido a la combinación de restricciones convexas y no convexas (rango bajo). Se desarrollaron diferentes técnicas basadas en diferentes realizaciones de. Sin embargo, el Método de Multiplicadores de Dirección Alternativa (ADMM) se puede aplicar para resolver el problema no convexo con la función objetivo convexa, restricciones de rango y otras restricciones convexas, [18] y, por lo tanto, es adecuado para resolver nuestro problema anterior. Además, a diferencia de los problemas generales no convexos, ADMM garantizará la convergencia de una solución factible siempre que su variable dual converja en las iteraciones.
Ver también
- La aproximación de la matriz CUR se realiza a partir de las filas y columnas de la matriz original.
Referencias
- ^ I. Markovsky, Aproximación estructurada de bajo rango y sus aplicaciones, Automatica, Volumen 44, Número 4, abril de 2008, páginas 891–909. doi : 10.1016 / j.automatica.2007.09.011
- ^ I. Markovsky, JC Willems, S. Van Huffel , B. De Moor y R. Pintelon, Aplicación de mínimos cuadrados totales estructurados para identificación de sistemas y reducción de modelos. Transacciones IEEE sobre control automático, volumen 50, número 10, 2005, páginas 1490–1500.
- ^ I.Markovsky, Aproximación de bajo rango: algoritmos, implementación, aplicaciones, Springer, 2012, ISBN 978-1-4471-2226-5
- ^ C. Eckart, G. Young, La aproximación de una matriz por otra de rango inferior. Psychometrika, Volumen 1, 1936, páginas 211–8. doi : 10.1007 / BF02288367
- ^ Srebro, Nathan; Jaakkola, Tommi (2003). Aproximaciones ponderadas de rango bajo (PDF) . ICML'03.
- ^ Razenshteyn, Ilya; Song, Zhao; Woodruff, David P. (2016). Aproximaciones ponderadas de rango bajo con garantías demostrables . STOC '16 Actas del cuadragésimo octavo simposio anual de ACM sobre teoría de la computación.
- ^ Clarkson, Kenneth L .; Woodruff, David P. (2013). Aproximación y regresión de rango bajo en tiempo de dispersión de entrada . STOC '13 Actas del cuadragésimo quinto simposio anual ACM sobre Teoría de la Computación. arXiv : 1207.6365 .
- ^ Nelson, Jelani; Nguyen, Huy L. (2013). OSNAP: algoritmos de álgebra lineal numérica más rápidos a través de incrustaciones de subespacio más dispersas . FOCS '13. arXiv : 1211.1002 .
- ^ Sarlos, Tamas (2006). Algoritmos de aproximación mejorados para matrices grandes mediante proyecciones aleatorias . FOCS'06.
- ^ Song, Zhao; Woodruff, David P .; Zhong, Peilin (2017). Aproximación de rango bajo con error de norma L1 de entrada . STOC '17 Actas del cuadragésimo noveno simposio anual de ACM sobre Teoría de la Computación. arXiv : 1611.00898 .
- ^ Bringmann, Karl; Kolev, Pavel; Woodruff, David P. (2017). Algoritmos de aproximación para aproximación de rango bajo L0 . NIPS'17. arXiv : 1710.11253 .
- ^ Chierichetti, Flavio; Gollapudi, Sreenivas; Kumar, Ravi; Lattanzi, Silvio; Panigrahy, Rina; Woodruff, David P. (2017). Algoritmos para la aproximación de rango bajo de Lp . ICML'17. arXiv : 1705.06730 .
- ^ Bakshi, Ainesh L .; Woodruff, David P. (2018). Aproximación de tiempo sublineal de rango bajo de matrices de distancia . NeurIPS. arXiv : 1809.06986 .
- ^ Indyk, Piotr; Vakilian, Ali; Wagner, Tal; Woodruff, David P. (2019). Aproximación de matrices de distancia de rango bajo óptimo de muestra . POTRO.
- ^ Boutsidis, Christos; Woodruff, David P .; Zhong, Peilin (2016). Análisis óptimo de componentes principales en modelos distribuidos y de transmisión . STOC. arXiv : 1504.06729 .
- ^ G. Golub y V. Pereyra, Mínimos cuadrados no lineales separables: el método de proyección variable y sus aplicaciones, Instituto de Física, Problemas inversos, Volumen 19, 2003, Páginas 1-26.
- ^ Chu, Moody T .; Funderlic, Robert E .; Plemmons, Robert J. (2003). "aproximación estructurada de rango bajo" . Álgebra lineal y sus aplicaciones . 366 : 157-172. doi : 10.1016 / S0024-3795 (02) 00505-0 .
- ^ "Un sistema general para la solución heurística de problemas convexos sobre conjuntos no convexos" (PDF) .
- MT Chu, RE Funderlic, RJ Plemmons, Aproximación estructurada de bajo rango, Álgebra lineal y sus aplicaciones, Volumen 366, 1 de junio de 2003, Páginas 157–172 doi : 10.1016 / S0024-3795 (02) 00505-0
enlaces externos
- Paquete C ++ para aproximación estructurada de rango bajo