V poslední době se hodně zabývám věcmi souvisejícími s normou a je na čase o tom promluvit. V tomto příspěvku se budeme zabývat celou rodinou norem.
Co je to norma?
Matematicky je norma celková velikost nebo délka všech vektorů ve vektorovém prostoru nebo matic. Pro zjednodušení můžeme říci, že čím vyšší je norma, tím větší je (hodnota v) matici nebo vektoru. Norma může mít mnoho podob a mnoho názvů, včetně těchto populárních názvů: Euklidovská vzdálenost, Střední kvadratická chyba atd.
Většinou se setkáte s tím, že norma se objeví v rovnici takto:
kde 
může být vektor nebo matice.
Například euklidovská norma vektoru 
je 
, což je velikost vektoru 
Výše uvedený příklad ukazuje, jak vypočítat euklidovskou normu, nebo formálně nazývanou 
norma. Existuje mnoho dalších typů norem, které přesahují náš výklad zde, vlastně pro každé reálné číslo existuje norma, která mu odpovídá (Všimněte si zdůrazněného slova reálné číslo, to znamená, že není omezeno pouze na celé číslo.)
Formálně je 
-norma 
definována jako:
kde 
To je vše! P-tý kořen součtu všech prvků na p-tou mocninu je to, čemu říkáme norma.
Zajímavé je, že i když všechny -normy vypadají navzájem velmi podobně, jejich matematické vlastnosti jsou velmi odlišné, a proto se dramaticky liší i jejich použití. Tímto se na některé z těchto norem podíváme podrobněji.
l0-norma
První normou, kterou se budeme zabývat, je 
-norma. Podle definice -norma je
Přísně vzato -norma vlastně není normou. Je to funkce kardinality, která má svou definici ve tvaru -norma, i když ji mnoho lidí nazývá normou. Práce s ní je trochu ošemetná, protože je v ní přítomna nulová mocnina a nulový kořen. Je zřejmé, že jakýkoli 
se jím stane, ale problémy s definicí nulové mocniny a zejména nulového kořene zde dělají zmatek. Ve skutečnosti tedy většina matematiků a inženýrů místo toho používá tuto definici -normy:
to je celkový počet nenulových prvků ve vektoru.
Protože jde o počet nenulových prvků, existuje tolik aplikací, které -normu používají. V poslední době je ještě více v centru pozornosti kvůli vzniku schématu Compressive Sensing, které se snaží nalézt nejřidší řešení nedeterminovaného lineárního systému. Nejřidším řešením se rozumí řešení, které má nejméně nenulových položek, tj. nejnižší -normu. Tento problém se obvykle považuje za problém optimalizace -normy nebo -optimalizace.
l0-optimalizace
Mnoho aplikací, včetně kompresního snímání, se snaží minimalizovat -normu vektoru odpovídajícího určitým omezením, proto se nazývá „-minimalizace“. Standardní minimalizační problém je formulován jako:
s podmínkou 
Toto však není snadný úkol. Protože -norma nemá matematickou reprezentaci, je -minimalizace považována informatiky za NP-těžký problém, což jednoduše říká, že je příliš složitá a téměř neřešitelná.
V mnoha případech je problém -minimalizace rozvolněn na problém norem vyššího řádu, jako je 
-minimalizace a -minimalizace.
l1-norma
Podle definice normy je -norma definována jako
Tato norma je mezi rodinou norem poměrně běžná. Má mnoho jmen a mnoho podob mezi různými obory, konkrétně manhattanská norma je její přezdívka. Pokud se norma počítá pro rozdíl dvou vektorů nebo matic, tedy
, nazývá se mezi odborníky na počítačové vidění Sum of Absolute Difference (SAD).
V obecnějším případě měření rozdílu signálů jej lze škálovat na jednotkový vektor pomocí:
kde 
je velikost .
která je známá jako střední absolutní chyba (MAE).
l2-norma
Nejpopulárnější ze všech norem je norma. Používá se téměř ve všech oblastech techniky a vědy jako celku. Podle základní definice je -norma definována jako
-norma je dobře známá jako euklidovská norma, která se používá jako standardní veličina pro měření rozdílu vektorů. Stejně jako u -normy, pokud se euklidovská norma počítá pro vektorový rozdíl, je známá jako euklidovská vzdálenost:
nebo ve své čtvercové podobě, která je mezi vědci zabývajícími se počítačovým viděním známá jako suma čtvercových rozdílů (SSD):
Její nejznámější aplikací v oblasti zpracování signálů je měření střední kvadratické chyby (MSE), které se používá k výpočtu podobnosti, kvality nebo korelace mezi dvěma signály. MSE je
Jak již bylo uvedeno v části -optimalizace, kvůli mnoha problémům z výpočetního i matematického hlediska se mnoho -optimalizačních problémů uvolňuje, aby se místo toho staly – a -optimalizací. Z tohoto důvodu se nyní budeme zabývat optimalizací .
l2-optimalizace
Stejně jako v případě -optimalizace je problém minimalizace -normy formulován
s výhradou
Předpokládáme, že matice omezení 
má plnou hodnost, tento problém je nyní nederminovaný systém, který má nekonečně mnoho řešení. Cílem je v tomto případě z těchto nekonečně mnoha řešení vytáhnout nejlepší řešení, tj. má nejnižší normu. To by mohla být velmi zdlouhavá práce, pokud by se měla vypočítat přímo. Naštěstí existuje matematický trik, který nám v této práci může velmi pomoci.
Pomocí triku s Lagrangeovými multiplikátory pak můžeme definovat Lagrangián
kde 
je zavedený Lagrangeův multiplikátor. Derivací této rovnice rovnou nule nalezneme optimální řešení a dostaneme
doplníme-li toto řešení do omezení, dostaneme
a nakonec
Pomocí této rovnice můžeme nyní okamžitě vypočítat optimální řešení optimalizačního problému. Tato rovnice je dobře známá jako Mooreova-Penroseova pseudoinverze a samotný problém je obvykle znám jako problém nejmenšího čtverce, regrese nejmenšího čtverce nebo optimalizace nejmenšího čtverce.
I když se však řešení metody nejmenšího čtverce snadno vypočítá, nemusí být nutně nejlepším řešením. Vzhledem k hladké povaze samotné normy je obtížné najít jediné, nejlepší řešení problému.
Naopak optimalizace může poskytnout mnohem lepší výsledek než toto řešení.
l1-optimalizace
Jako obvykle je problém -minimalizace formulován jako
s výhradou
Protože charakter -normy není hladký jako v případě -normy, je řešení tohoto problému mnohem lepší a jednoznačnější než -optimalizace.
Přestože má problém -minimalizace téměř stejný tvar jako -minimalizace, je jeho řešení mnohem obtížnější. Protože tento problém nemá hladkou funkci, trik, který jsme použili při řešení -problému, již neplatí. Jediný způsob, který zbývá k nalezení jeho řešení, je hledat ho přímo. Hledání řešení znamená, že musíme vypočítat všechna možná řešení, abychom z množiny „nekonečně mnoha“ možných řešení našli to nejlepší.
Protože neexistuje jednoduchý způsob, jak najít řešení tohoto problému matematicky, je užitečnost -optimalizace na desetiletí velmi omezená. Až nedávný pokrok počítačů s vysokým výpočetním výkonem nám umožňuje „projít“ všechna řešení. Pomocí mnoha užitečných algoritmů, konkrétně algoritmu konvexní optimalizace, jako je lineární programování nebo nelineární programování atd. je nyní možné najít nejlepší řešení této otázky. Mnoho aplikací, které se opírají o optimalizaci, včetně kompresního snímání, je nyní možné
V dnešní době je k dispozici mnoho sad nástrojů pro optimalizaci. Tyto toolboxy obvykle používají různé přístupy a/nebo algoritmy k řešení stejné otázky. Příkladem těchto toolboxů jsou l1-magic, SparseLab, ISAL1,
Nyní jsme probrali mnoho členů rodiny norem, počínaje -normou, -normou a -normou. Je čas přejít k dalšímu. Protože jsme si hned na začátku řekli, že může existovat libovolná l-tice norem, která se řídí stejnou základní definicí normy, bude trvat dlouho, než si povíme o všech. Naštěstí kromě -, – , a -normy jsou ostatní obvykle neobvyklé, a proto na nich není tolik zajímavého. Podíváme se tedy na extrémní případ normy, kterým je 
-norma (l-nekonečná norma).
l-nekonečná norma
Jako vždy, definice pro -normu je
Nyní tato definice vypadá opět složitě, ale ve skutečnosti je docela přímočará. Uvažujme vektor 
, řekněme, je-li 
nejvyšší položkou vektoru , podle vlastnosti nekonečna sám o sobě, můžeme říci, že
pak
tedy
Nyní můžeme jednoduše říci, že -norma je
to je velikost maximální položky tohoto vektoru. Tím jsme jistě demystifikovali význam -normy
Nyní jsme probrali celou rodinu norem od až po , doufám, že tato diskuse pomůže pochopit význam normy, její matematické vlastnosti a její reálné důsledky.
Reference a další literatura:
Matematická norma – wikipedia
Matematická norma – MathWorld
Michael Elad – „Sparse and Redundant Representations : From Theory to Applications in Signal and Image Processing“ , Springer, 2010.
Linear Programming – MathWorld
Compressive Sensing – Rice University
Edit (15/02/15) : Opraveny nepřesnosti obsahu.