Últimamente estoy trabajando mucho en cosas relacionadas con la norma y ya es hora de hablar de ella. En este post vamos a hablar de toda una familia de normas.
¿Qué es una norma?
Matemáticamente una norma es un tamaño o longitud total de todos los vectores de un espacio vectorial o matrices. Para simplificar, podemos decir que cuanto más alta es la norma, más grande es la matriz o el vector (valor en). La norma puede tener muchas formas y muchos nombres, incluyendo estos nombres populares: distancia euclidiana, error cuadrático medio, etc.
La mayoría de las veces verás que la norma aparece en una ecuación como esta:
donde 
puede ser un vector o una matriz.
Por ejemplo, una norma euclidiana de un vector 
es 
que es el tamaño del vector 
El ejemplo anterior muestra cómo calcular una norma euclidiana, o formalmente llamada norma 
. Hay muchos otros tipos de normas que van más allá de nuestra explicación aquí, en realidad para cada número real, hay una norma que le corresponde (Nótese el énfasis en la palabra número real, que significa que no se limita sólo a los números enteros.)
Formalmente la 
-norma de 
se define como:
donde 
¡Eso es todo! Una raíz p-ésima de una suma de todos los elementos a la potencia p-ésima es lo que llamamos una norma.
El punto interesante es que aunque todas las -normas son muy similares entre sí, sus propiedades matemáticas son muy diferentes y, por lo tanto, su aplicación es dramáticamente diferente también. Aquí vamos a ver algunas de estas normas en detalle.
norma l0
La primera norma que vamos a discutir es una 
-norma. Por definición, la -norma de es
En sentido estricto, la -norma no es realmente una norma. Es una función de cardinalidad que tiene su definición en la forma de -norma, aunque mucha gente la llama norma. Es un poco difícil de trabajar porque hay una presencia de zeroth-power y zeroth-root en ella. Obviamente, cualquier 
se convertirá en una, pero los problemas de la definición de la potencia cero y, especialmente, de la raíz cero, están complicando las cosas. Así que en realidad, la mayoría de los matemáticos e ingenieros utilizan esta definición de -norma en su lugar:
que es un número total de elementos distintos de cero en un vector.
Porque es un número de elementos distintos de cero, hay tantas aplicaciones que utilizan -norma. Últimamente es aún más en el foco debido a la aparición del esquema de detección de compresión, que es tratar de encontrar la solución más escasa del sistema lineal sub-determinado. La solución más escasa significa la solución que tiene menos entradas distintas de cero, es decir, la norma más baja. Este problema se suele considerar como un problema de optimización de -norma o -optimización.
l0-optimización
Muchas aplicaciones, entre ellas la de Detección Compresiva, tratan de minimizar la -norma de un vector correspondiente a unas restricciones, por lo que se denomina «-minimización». Un problema de minimización estándar se formula como:
sujeto a 
Sin embargo, hacerlo no es una tarea fácil. Debido a la falta de representación matemática de la norma, la minimización es considerada por los informáticos como un problema NP-duro, lo que significa simplemente que es demasiado complejo y casi imposible de resolver.
En muchos casos, el problema de -minimización se relaja para ser un problema de norma de orden superior como 
-minimización y -minimización.
l1-norma
Siguiendo la definición de norma, -norma de se define como
Esta norma es bastante común entre la familia de normas. Tiene muchos nombres y muchas formas entre varios campos, concretamente la norma Manhattan es su apodo. Si la norma se calcula para una diferencia entre dos vectores o matrices, es decir
se llama Suma de la Diferencia Absoluta (SAD) entre los científicos de la visión por ordenador.
En el caso más general de la medición de la diferencia de la señal, se puede escalar a un vector unitario por:
donde 
es un tamaño de .
que se conoce como Error Medio-Absoluto (MAE).
l2-norma
La más popular de todas las normas es la -norma. Se utiliza en casi todos los campos de la ingeniería y la ciencia en general. Siguiendo la definición básica, -norma se define como
-norma es bien conocida como una norma euclidiana, que se utiliza como una cantidad estándar para medir una diferencia vectorial. Al igual que la norma , si la norma euclidiana se calcula para una diferencia de vectores, se conoce como distancia euclidiana:
o en su forma cuadrada, conocida como Suma de Diferencias Cuadradas (SSD) entre los científicos de la visión por ordenador:
Su aplicación más conocida en el campo del procesamiento de señales es la medición del error cuadrático medio (MSE), que se utiliza para calcular una similitud, una calidad o una correlación entre dos señales. El MSE es
Como se discutió anteriormente en la sección de-optimización, debido a muchas cuestiones tanto desde un punto de vista computacional como matemático, muchos problemas de-optimización se relajan para convertirse en– y-optimización. Debido a esto, ahora discutiremos sobre la optimización de.
l2-optimización
Como en el caso de -optimización, el problema de minimizar -norma se formula por
sujeto a
Supongamos que la matriz de restricción 
tiene rango completo, este problema es ahora un sistema subderterminado que tiene infinitas soluciones. El objetivo en este caso es sacar la mejor solución, es decir, tiene la menor -norma, de estas infinitas soluciones. Esto podría ser un trabajo muy tedioso si se tuviera que calcular directamente. Por suerte hay un truco matemático que nos puede ayudar mucho en este trabajo.
Utilizando un truco de multiplicadores de Lagrange, podemos entonces definir una lagrangiana
donde 
es el multiplicador de Lagrange introducido. Tomar la derivada de esta ecuación igual a cero para encontrar una solución óptima y obtener
conectar esta solución en la restricción para obtener
y, finalmente,
Por medio de esta ecuación, ahora podemos calcular instantáneamente una solución óptima del problema de optimización . Esta ecuación se conoce como la Pseudoinversa de Moore-Penrose y el problema en sí se suele conocer como problema de mínimos cuadrados, regresión de mínimos cuadrados u optimización de mínimos cuadrados.
Sin embargo, aunque la solución del método de mínimos cuadrados es fácil de calcular, no es necesario que sea la mejor solución. Debido a la naturaleza suave de la propia -norma, es difícil encontrar una única y mejor solución para el problema.
Por el contrario, la optimización de puede proporcionar un resultado mucho mejor que esta solución.
l1-optimización
Como es habitual, el problema de -minimización se formula como
sujeto a
Debido a que la naturaleza de -norma no es suave como en el caso de -norma, la solución de este problema es mucho mejor y más única que la -optimización.
Sin embargo, aunque el problema de -minimización tiene casi la misma forma que el de -minimización, es mucho más difícil de resolver. Como este problema no tiene una función suave, el truco que utilizamos para resolver el problema ya no es válido. La única forma que nos queda para encontrar su solución es buscarla directamente. Buscar la solución significa que tenemos que calcular todas las soluciones posibles para encontrar la mejor del conjunto de «infinitas» soluciones posibles.
Dado que no hay una forma fácil de encontrar la solución de este problema matemáticamente, la utilidad de la optimización de es muy limitada durante décadas. Hasta hace poco, el avance de los ordenadores con alta potencia de cálculo nos permite «barrer» todas las soluciones. Mediante el uso de muchos algoritmos útiles, a saber, el algoritmo de optimización convexa como la programación lineal, o la programación no lineal, etc. ahora es posible encontrar la mejor solución a esta cuestión. Muchas aplicaciones que se basan en -optimización, incluyendo el Compressive Sensing, son ahora posibles.
Hay muchas cajas de herramientas para -optimización disponibles hoy en día. Estas cajas de herramientas suelen utilizar diferentes enfoques y/o algoritmos para resolver la misma cuestión. El ejemplo de estas cajas de herramientas son l1-magic, SparseLab, ISAL1,
Ahora que hemos discutido muchos miembros de la familia de la norma, a partir de -norma, -norma, y -norma. Es hora de pasar a la siguiente. Como ya dijimos al principio que puede haber cualquier norma l que siga la misma definición básica de norma, nos va a llevar mucho tiempo hablar de todas ellas. Afortunadamente, aparte de -, – , y -norma, el resto suelen ser poco comunes y por lo tanto no tienen tantas cosas interesantes que ver. Así que vamos a ver el caso extremo de la norma que es una 
-norma (norma l-infinita).
norma l-infinita
Como siempre, la definición de -norma es
Ahora esta definición parece complicada de nuevo, pero en realidad es bastante sencilla. Consideremos el vector 
, digamos que si 
es la entrada más alta del vector , por la propiedad del propio infinito, podemos decir que
entonces
entonces
Ahora podemos decir simplemente que la -norma es
que es la magnitud de las entradas máximas de ese vector. Esto ha desmitificado el significado de -norma
Ahora hemos discutido toda la familia de normas desde hasta , espero que esta discusión ayude a entender el significado de norma, sus propiedades matemáticas, y su implicación en el mundo real.
Referencias y lecturas adicionales:
Norma matemática – wikipedia
Norma matemática – MathWorld
Michael Elad – «Sparse and Redundant Representations : From Theory to Applications in Signal and Image Processing» , Springer, 2010.
Programación lineal – MathWorld
Señalización compresiva – Rice University
Edición (15/02/15) : Corregidas inexactitudes del contenido.