El problema de encontrar matrices de rango mínimo que satisfagan un conjunto de restricciones de medición lineal es NP-hard, lo que significa que nadie conoce un algoritmo de tiempo polinómico para abordar todas las instancias de este problema. Sin embargo, es un problema increíblemente útil: presentaré algunos ejemplos en los siguientes párrafos. Si no nos preocupamos por los peores casos, la minimización de la norma nuclear proporciona un proxy que recupera de manera sorprendente y demostrable el mismo resultado que la minimización de bajo rango para una gran cantidad de casos típicos. Además, la norma nuclear es una función convexa que se puede minimizar de manera eficiente utilizando varios algoritmos.
(La respuesta de Chi Feng es acertada sobre las aplicaciones, pero la elección de la norma realmente importa en este caso. Es cierto que las normas son equivalentes en espacios de alta dimensión, sin embargo, la norma de Frobenius o la minimización de rango espectral no dan soluciones de bajo rango !)
Aplicaciones: Muchos problemas pueden formularse en términos de un modelo matricial de bajo rango. En todas estas configuraciones, hay una matriz subyacente de bajo rango que no conocemos, pero vemos algún otro conjunto de números que están relacionados linealmente con ella. Aquí hay algunos ejemplos típicos:
- Sistemas de recomendación y finalización de matriz: un caso interesante de mediciones lineales de una matriz es el muestreo de las entradas de la matriz. Por lo tanto, esto se llama el problema de terminación de matriz donde su objetivo es completar las entradas de una matriz (al igual que resuelve sudoku) y se le dan algunas de las entradas (puede ser aproximadamente) y sabe que es de bajo rango.
- Matrices de distancia euclidianas: las matrices de distancia tienen una estructura de matriz especial de bajo rango y podemos usar la norma nuclear para recuperarlas de información parcial.
- Identificación del sistema de series de tiempo: El problema de encontrar un modelo de serie de tiempo o un sistema lineal cuando observamos algunas respuestas del sistema puede formularse como una estimación de una matriz de Hankel de bajo rango y también puede resolverse utilizando la norma nuclear.
Referencias: El uso de esta norma nuclear como heurística convexa se propuso en Page on washington.edu: la tesis también cataloga una serie de aplicaciones. La página en berkeley.edu demuestra que la minimización de la norma nuclear puede recuperar el resultado de la minimización de rango cuando las mediciones lineales son aleatorias y satisfacen algunas propiedades simples. Esta página en springer.com muestra que la minimización de la norma nuclear puede hacer un buen trabajo al completar Matrix.
- ¿Existe una interpretación física del producto cruzado de dos vectores ‘documento’?
- ¿Cuáles son las ventajas de los clasificadores lineales?
- ¿Son todos los núcleos definidos positivos funciones definidas positivas?
- ¿Cuál es la importancia del álgebra lineal para la formación teórica general de la informática?
- ¿Cuál es la interpretación de los valores propios / vectores generalizados en la teoría de grafos espectrales?
Generalización: La historia en el primer párrafo puede resultarle familiar si reemplaza la matriz de norma mínima con un vector disperso y la norma nuclear con la norma l1. Hay dos formas de pensar en esta analogía:
- Puedes pensar en la norma nuclear (que es la suma de valores singulares) como la norma l1 de los valores singulares. Luego, si agita las manos con la fuerza suficiente, puede convencer a alguien de que se deduce que la minimización nuclear produciría una solución con valores escasos y singulares y, por lo tanto, devolvería matrices de bajo rango.
- Un truco común en la optimización para “convexificar” un problema no convexo es una técnica llamada relajación convexa. En lugar de minimizar una función, minimiza la envoltura convexa de la función, es decir, una función convexa que es el mejor límite inferior para la función original que desea minimizar. De hecho, puede demostrar que la norma nuclear es la envoltura convexa del “rango” no convexo de una matriz cuando considera las matrices en la bola de la unidad. Entonces, minimización de la norma nuclear
- Una forma inteligente de generalizar esto es darse cuenta de que las matrices de bajo rango están compuestas de un pequeño número de posibles matrices de rango 1 potencialmente infinitas. Por lo tanto, es escaso con respecto al diccionario infinito de todas las matrices de rango de norma de unidad 1. Al generalizar así la dispersión a infinitos diccionarios, el concepto de norma atómica le permite construir relajaciones convexas para una clase mucho más amplia de problemas y generaliza la norma l1 para vectores dispersos, normas nucleares para matrices de bajo rango, norma l1-l2 para vectores dispersos grupales, etc. ., Recomiendo mirar la página en caltech.edu y las secuencias de eliminación de ruido y descomposición de momentos usando la optimización convexa para obtener más información al respecto.