I’m working on things related to norm much lately and it is time to talk about it. Neste post vamos discutir sobre toda uma família de normas.
O que é uma norma?
matematicamente uma norma é um tamanho total ou comprimento de todos os vetores em um espaço vetorial ou matrizes. Para simplificar, podemos dizer que quanto maior for a norma, maior é a (valor em) matriz ou vetor. A norma pode vir em muitas formas e muitos nomes, incluindo estes nomes populares: Euclidean distance, Mean-squared Error, etc.
Maior do tempo em que verá a norma aparecer numa equação como esta:
onde 
pode ser um vector ou uma matriz.
Por exemplo, uma norma euclidiana de um vector 
é 
que é o tamanho do vector 
O exemplo acima mostra como calcular uma norma euclidiana, ou formalmente chamada 
-norma. Existem muitos outros tipos de norma que além da nossa explicação aqui, na verdade para cada número real, existe uma norma que lhe corresponde (Repare na palavra sublinhada número real, que significa que não se limita apenas ao inteiro.)
Formalmente a 
-norma de 
é definida como:
onde 
>É isso! Uma p-t-root de uma soma de todos os elementos para a p-t-potência é o que chamamos de norma.
O ponto interessante é que apesar de cada -norma ser muito parecida entre si, as suas propriedades matemáticas são muito diferentes e, portanto, a sua aplicação também é dramaticamente diferente. Assim, vamos analisar algumas destas normas em detalhes.
l0-norma
A primeira norma que vamos discutir é uma 
-norma. Por definição, -norma de é
estritamente falando, -norma não é realmente uma norma. É uma função de cardinalidade que tem a sua definição na forma de -norma, embora muitas pessoas lhe chamem norma. É um pouco complicado de se trabalhar porque há uma presença de zeroth-power e zeroth-root nela. Obviamente qualquer 
se tornará uma, mas os problemas da definição de zeroth-power e especialmente zeroth-root estão bagunçando as coisas por aqui. Assim, na realidade, a maioria dos matemáticos e engenheiros usam esta definição de -norma:
que é um número total de elementos não-zero num vector.
Por ser um número de elementos não-zero, há tantas aplicações que usam -norma. Ultimamente está ainda mais em foco devido ao aumento do esquema de Sensoriamento Compressivo, que é tentar encontrar a solução mais escassa do sistema linear sub-determinado. A solução mais sparsest significa a solução que tem menos entradas não zero, ou seja, a mais baixa -norma. Este problema é geralmente considerado como um problema de optimização de -norma ou -optimização.
l0-optimização
Muitas aplicações, incluindo a Compressive Sensing, tentam minimizar a -norma de um vector correspondente a algumas restrições, daí o chamado “-minimização”. Um problema padrão de minimização é formulado como:
sujeito a 
No entanto, fazer isso não é uma tarefa fácil. Porque a falta de representação matemática de -norma, -minimização é considerada pelos cientistas da computação como um problema NP-difícil, simplesmente diz que é demasiado complexa e quase impossível de resolver.
>
Em muitos casos, problema de minimização é relaxado para ser um problema de norma de ordem superior, como 
-minimização e -minimização.
>
l1-norma
>
Seguir a definição de norma, -norma de é definido como
>
>
>
>
Esta norma é bastante comum entre a família de normas. Ela tem muitos nomes e muitas formas entre vários campos, nomeadamente Manhattan norm é o seu apelido. Se a -norma é calculada para uma diferença entre dois vectores ou matrizes, ou seja
>
chama-se Soma da Diferença Absoluta (SAD) entre os cientistas de visão computacional.
>
Em caso mais geral de medição de diferença de sinal, ela pode ser escalada para uma unidade vetorial por:
onde 
é um tamanho de .
>
que é conhecido como Erro Médio-Absoluto (MAE).
l2-norma
A mais popular de todas as normas é a -norma. Ela é usada em quase todos os campos da engenharia e da ciência como um todo. Seguindo a definição básica, -norma é definida como
-norma é bem conhecida como uma norma Euclidiana, que é usada como uma quantidade padrão para medir uma diferença vetorial. Como em -norma, se a norma euclidiana é calculada para uma diferença vetorial, ela é conhecida como uma distância euclidiana:
ou na sua forma quadrada, conhecida como Soma da Diferença Quadrática (SSD) entre os cientistas da Computer Vision:
A aplicação mais conhecida no campo de processamento de sinais é a medição do erro médio quadrático (MSE), que é usado para calcular uma semelhança, uma qualidade, ou uma correlação entre dois sinais. MSE é
Como discutido anteriormente na seção -optimização, devido a muitas questões tanto de uma visão computacional quanto de uma visão matemática, muitos -optimização relaxam para se tornarem – e -optimização em seu lugar. Por causa disso, vamos agora discutir sobre a otimização de .
l2-optimisação
Como em -optimisação, o problema de minimizar -norma é formulado por
sujeito a
Assumir que a matriz de restrição 
tem uma classificação completa, este problema é agora um sistema subderterminado que tem soluções infinitas. O objetivo neste caso é extrair a melhor solução, ou seja, tem a menor -norma, destas infinitas soluções. Este poderia ser um trabalho muito enfadonho se fosse computado diretamente. Felizmente é um truque matemático que nos pode ajudar muito neste trabalho.
Usando um truque de multiplicadores de Lagrange, podemos então definir um Lagrangian
onde 
são os multiplicadores de Lagrange introduzidos. Pegue derivado desta equação igual a zero para encontrar uma solução ótima e obtenha
>
>plugue esta solução na restrição para obter
>
>
>
e finalmente
>
> Usando esta equação, podemos agora calcular instantaneamente uma solução ótima do problema de -optimização. Esta equação é bem conhecida como o Pseudoinverso Moore-Penrose e o problema em si é geralmente conhecido como problema do Menos Quadrado, regressão do Menos Quadrado, ou otimização do Menos Quadrado.
No entanto, mesmo que a solução do método do Menos Quadrado seja fácil de calcular, não é necessário ser a melhor solução. Devido à natureza suave de -norma em si, é difícil encontrar uma única e melhor solução para o problema.
>
>>-optimização pode proporcionar um resultado muito melhor do que esta solução.
>l1-optimização
Como de costume, o problema -minimização é formulado como
>
sujeito a >
>
Porque a natureza da -norma não é suave como no caso da -norma, a solução deste problema é muito melhor e mais única do que a -optimização.
No entanto, embora o problema de -minimização tenha quase a mesma forma que a -minimização, é muito mais difícil de resolver. Como este problema não tem uma função suave, o truque que usávamos para resolver -problema já não é válido. A única maneira de encontrar a sua solução é procurá-la directamente. Procurar a solução significa que temos de calcular todas as soluções possíveis para encontrar a melhor solução do conjunto de “infinitamente muitas” soluções possíveis.
Desde que não existe uma forma fácil de encontrar a solução para este problema matematicamente, a utilidade de -optimização é muito limitada durante décadas. Até recentemente, o avanço do computador com alto poder computacional nos permite “varrer” todas as soluções. Usando muitos algoritmos úteis, nomeadamente o algoritmo Convex Optimisation, como a programação linear, ou programação não linear, etc., é agora possível encontrar a melhor solução para esta questão. Muitas aplicações que dependem de -optimização, incluindo o Sensoriamento Compressivo, são agora possíveis.
Existem muitas caixas de ferramentas para -optimização disponíveis hoje em dia. Estas caixas de ferramentas normalmente utilizam diferentes abordagens e/ou algoritmos para resolver a mesma questão. O exemplo destas caixas de ferramentas são l1-magic, SparseLab, ISAL1,
Agora discutimos muitos membros da família de normas, começando de -norm, -norm, e -norm. É hora de passarmos para a próxima. Como discutimos logo no início que pode haver qualquer norma l – qualquer que seja a norma seguindo a mesma definição básica de norma, vai levar muito tempo para falar sobre todas elas. Felizmente, com exceção de -, – , e -norma, o resto delas geralmente são incomuns e, portanto, não têm tantas coisas interessantes para se ver. Então vamos olhar para o caso extremo da norma que é uma norma 
-norma (norma l-infinidade).
l-infinidade norma
Como sempre, a definição para -norma é
Agora esta definição parece complicada novamente, mas na verdade ela é bastante estrita. Considere o vector 
, digamos se 
é a entrada mais alta no vector , pela propriedade do próprio infinito, podemos dizer que
>
>
>
>
>
>
>Now podemos simplesmente dizer que a -norma é
>
é a magnitude máxima de entradas desse vector. Isso certamente desmistificou o significado de -norma
Agora discutimos toda a família de normas de a , espero que essa discussão ajude a entender o significado de norma, suas propriedades matemáticas e sua implicação no mundo real.
Referência e posterior leitura:
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.
Programação Linear – MathWorld
Sensoriamento Compressivo – Rice University
Editar (15/02/15) : Correção de imprecisões do conteúdo.