Nadměrnost - Overcompleteness

tento článek poskytuje nedostatečný kontext pro ty, kteří danému tématu nejsou obeznámeni. Prosím pomozte vylepšit článek podle poskytuje čtenáři více kontextu. (Listopad 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Nadměrnost je koncept z lineární algebra který je široce používán v matematice, informatice, strojírenství a statistikách (obvykle ve formě neúplných údajů) rámy ). To bylo představeno R. J. Duffin a A. C. Schaeffer v roce 1952.^[1]

Formálně podmnožina vektorů ${ displaystyle { phi _ {i} } _ {i v J}}$ a Banachův prostor ${ displaystyle X}$, někdy nazývaný „systém“, je kompletní pokud každý prvek v ${ displaystyle X}$ lze v normě libovolně dobře aproximovat konečnými lineárními kombinacemi prvků v ${ displaystyle { phi _ {i} } _ {i v J}}$.^[2] Takový kompletní systém je neúplné pokud odstranění a ${ displaystyle phi _ {j}}$ ze systému vznikne systém (tj. ${ displaystyle { phi _ {i} } _ {i v J zpětné lomítko {j }}}$), který je stále kompletní.

V oblastech výzkumu, jako je zpracování signálu a aproximace funkcí, může nadměrná úplnost pomoci vědcům dosáhnout stabilnějšího, robustnějšího nebo kompaktnějšího rozkladu než použití základny.^[3]

Vztah mezi nadměrností a rámy

Overcompleteness je obvykle diskutována jako vlastnost overcomplete snímků. Teorie rámu vychází z článku Duffina a Schaeffera o neharmonických Fourierových řadách.^[1] Rámec je definován jako sada nenulových vektorů ${ displaystyle { phi _ {i} } _ {i v J}}$ tak, že pro svévolné ${ displaystyle f in { mathcal {H}}}$,

${ displaystyle A | f | ^ {2} leq sum _ {i in J} | langle f, phi _ {i} rangle | ^ {2} leq B | f | ^ {2}}$

kde ${ displaystyle langle cdot, cdot rangle}$ označuje vnitřní produkt, ${ displaystyle A}$ a ${ displaystyle B}$ jsou kladné konstanty zvané hranice rámce. Když ${ displaystyle A}$ a ${ displaystyle B}$ lze zvolit tak, že ${ displaystyle A = B}$, rám se nazývá těsný rám.^[4]

Je to vidět ${ displaystyle { mathcal {H}} = operatorname {span} { phi _ {i} }}$Příklad rámečku lze uvést následovně. Nechť každý z nich ${ displaystyle { alpha _ {i} } _ {i = 1} ^ { infty}}$ a ${ displaystyle { beta _ {i} } _ {i = 1} ^ { infty}}$ být ortonormálním základem ${ displaystyle { mathcal {H}}}$, pak

${ displaystyle { phi _ {i} } _ {i = 1} ^ { infty} = { alpha _ {i} } _ {i = 1} ^ { infty} pohár { beta _ {i} } _ {i = 1} ^ { infty}}$

je rám z ${ displaystyle { mathcal {H}}}$ s mezemi ${ displaystyle A = B = 2}$.

Nechat ${ displaystyle S}$ být operátorem rámce,

${ displaystyle Sf = součet _ {i in J} langle f, phi _ {i} rangle phi _ {i}}$

Rámeček, který není a Rieszův základ, v takovém případě se skládá ze sady funkcí více než na základě, se říká, že je neúplný. V tomto případě dáno ${ displaystyle f in { mathcal {H}}}$, může mít různé rozklady založené na rámci. Rámec uvedený v příkladu výše je příliš nedokončený rámec.

Když se pro odhad funkce používají snímky, může být vhodné porovnat výkon různých snímků. Parsimony aproximačních funkcí různými snímky lze považovat za jeden způsob, jak porovnat jejich výkony.^[5]

Vzhledem k toleranci ${ displaystyle epsilon}$ a rám ${ displaystyle F = { phi _ {i} } _ {i v J}}$ v ${ displaystyle L ^ {2} ( mathbb {R})}$, pro jakoukoli funkci ${ displaystyle f in L ^ {2} ( mathbb {R})}$, definujte sadu všech aproximačních funkcí, které splňují ${ displaystyle | f - { hat {f}} | < epsilon}$

${ displaystyle N (f, epsilon) = {{ hat {f}}: { hat {f}} = součet _ {i = 1} ^ {k} beta _ {i} phi _ {i}, | f - { hat {f}} | < epsilon }}$

Pak nechte

${ displaystyle k_ {F} (f, epsilon) = inf {k: { hat {f}} v N (f, epsilon) }}$

${ displaystyle k (f, epsilon)}$ označuje šetrnost využití rámce ${ displaystyle F}$ přiblížit ${ displaystyle f}$. Odlišný ${ displaystyle f}$ může mít různé ${ displaystyle k}$ na základě tvrdosti, která má být aproximována s prvky v rámu. Nejhorší případ pro odhad funkce v ${ displaystyle L ^ {2} ( mathbb {R})}$ je definován jako

${ displaystyle k_ {F} ( epsilon) = sup _ {f v L ^ {2} ( mathbb {R})} {k_ {F} (f, epsilon) }}$

Pro jiný snímek ${ displaystyle G}$, pokud ${ displaystyle k_ {F} ( epsilon)$, pak rám ${ displaystyle F}$ je lepší než rám ${ displaystyle G}$ na úrovni ${ displaystyle epsilon}$. A pokud existuje ${ displaystyle gamma}$ to pro každého ${ displaystyle epsilon < gamma}$, my máme ${ displaystyle k_ {F} ( epsilon)$, pak ${ displaystyle F}$ je lepší než ${ displaystyle G}$ široce.

Přeplněné rámy jsou obvykle konstruovány třemi způsoby.

1. Zkombinujte sadu základen, jako je například vlnková základna a Fourierova základna, a získáte tak neúplný rámec.
2. Zvětšit rozsah parametrů v nějakém rámci, například v Gaborově rámci a vlnka snímek, aby byl snímek neúplný.
3. Přidejte některé další funkce k existujícímu úplnému základu a dosáhnete tak neúplného rámce.

Níže je uveden příklad neúplného rámce. Shromážděná data jsou v dvourozměrném prostoru a v tomto případě by základna se dvěma prvky měla být schopna vysvětlit všechna data. Pokud je však v datech zahrnut šum, základ nemusí být schopen vyjádřit vlastnosti dat. Pokud se k vyjádření dat použije překompletovaný rámec se čtyřmi prvky odpovídajícími čtyřem osám na obrázku, každý bod by byl schopen mít dobrý výraz překomplikovaným rámcem.

• 

  Příklad neúplného rámečku

Flexibilita překomplikovaného rámce je jednou z jeho klíčových výhod při použití při vyjádření signálu nebo aproximaci funkce. Kvůli této redundanci však funkce může mít více výrazů v rámci neúplného rámce.^[6] Když je rám konečný, lze rozklad vyjádřit jako

${ displaystyle f = Sekera}$

kde ${ displaystyle f}$ je funkce, kterou chce člověk aproximovat, ${ displaystyle A}$ je matice obsahující všechny prvky v rámci a ${ displaystyle x}$ je koeficienty ${ displaystyle f}$ pod zastoupením ${ displaystyle A}$. Bez dalších omezení se rám rozhodne dát ${ displaystyle x}$ s minimální normou v ${ displaystyle L ^ {2} ( mathbb {R})}$. Na základě toho lze při řešení rovnice vzít v úvahu i některé další vlastnosti, například řídkost. Takže různí vědci pracovali na řešení této rovnice přidáním dalších omezení do objektivní funkce. Například omezení na minimum ${ displaystyle x}$je norma v ${ displaystyle L ^ {1} ( mathbb {R})}$ lze použít při řešení této rovnice. To by mělo odpovídat Laso regrese v komunitě statistik. Bayesiánský přístup se také používá k eliminaci nadbytečnosti v neúplném rámci. Lweicki a Sejnowski navrhli algoritmus pro neúplný snímek tím, že jej považovali za pravděpodobnostní model pozorovaných dat.^[6] V poslední době byl neúplný Gaborův rám kombinován s metodou výběru bayesovských proměnných, aby se dosáhlo jak malých koeficientů expanze normy v ${ displaystyle L ^ {2} ( mathbb {R})}$ a řídkost v prvcích.^[7]

Příklady neúplných snímků

V moderní analýze v oblasti zpracování signálů a dalších technických oborů jsou navrženy a použity různé neúplné rámce. Zde jsou představeny a diskutovány dva běžně používané rámce, rámce Gabor a rámce wavelet.

Gaborové rámy

Při obvyklé Fourierově transformaci je funkce v časové doméně transformována do frekvenční domény. Transformace však ukazuje pouze vlastnost frekvence této funkce a ztrácí informace v časové doméně. Pokud je funkce okna ${ displaystyle g}$, který má nenulovou hodnotu pouze v malém intervalu, se před provedením Fourierovy transformace znásobí původní funkcí, informace ve časové a frekvenční doméně mohou zůstat ve zvoleném intervalu. Při posloupnosti překladu ${ displaystyle g}$ Při transformaci se používá informace, informace o funkci v časové doméně se uchovávají i po transformaci.

Nechte operátory

${ displaystyle T_ {a}: L ^ {2} (R) rightarrow L ^ {2} (R), (T_ {a} f) (x) = f (x-a)}$

${ displaystyle E_ {b}: L ^ {2} (R) rightarrow L ^ {2} (R), (E_ {b} f) (x) = e ^ {2 pi ibx} f (x) }$

${ displaystyle D_ {c}: L ^ {2} (R) rightarrow L ^ {2} (R), (D_ {c} f) (x) = { frac {1} { sqrt {c} }} f left ({ frac {x} {c}} right)}$

Gaborův rám (pojmenovaný po Dennis Gabor a také volal Weyl -Heisenberg rámeček) ${ displaystyle L ^ {2} (R)}$ je definován jako forma ${ displaystyle {E_ {mb} T_ {na} g } _ {m, n v Z}}$, kde ${ displaystyle a, b> 0}$ a ${ displaystyle g v L ^ {2} (R)}$ je pevná funkce.^[8] Ne však pro každého ${ displaystyle a}$ a ${ displaystyle b}$ ${ displaystyle {E_ {mb} T_ {na} g } _ {m, n v Z}}$tvoří rám na ${ displaystyle L ^ {2} (R)}$. Například když ${ displaystyle ab> 1}$, není to rám pro ${ displaystyle L ^ {2} (R)}$. Když ${ displaystyle ab = 1}$, ${ displaystyle {E_ {mb} T_ {na} g } _ {m, n v Z}}$ je možné být rámem, v takovém případě se jedná o Rieszův základ. Možná situace pro ${ displaystyle {E_ {mb} T_ {na} g } _ {m, n v Z}}$ být neúplným rámcem je ${ displaystyle ab <1}$Rodina Gaborů ${ displaystyle {E_ {mb / c} T_ {nac} g_ {c} } _ {m, n v Z}}$ je také rámec a sdílí stejné hranice rámce jako ${ displaystyle {E_ {mb} T_ {na} g } _ {m, n v Z}.}$

Různé druhy okenních funkcí ${ displaystyle g}$ lze použít v rámu Gabor. Zde jsou zobrazeny příklady tří funkcí okna a podmínka pro odpovídající systém Gabor, který je rámem, je zobrazena následovně.

• 

  Tři okenní funkce používané při generování rámce Gabor.

(1) ${ displaystyle g (x) = e ^ {- x ^ {2}}}$, ${ displaystyle {E_ {mb} T_ {na} g } _ {m, n v Z}}$ je rám, když${ displaystyle ab <0,994}$

(2) ${ displaystyle g (x) = { frac {1} {cosh ( pi x)}}}$, ${ displaystyle {E_ {mb} T_ {na} g } _ {m, n v Z}}$ je rám, když${ displaystyle ab <1}$

(3) ${ displaystyle g (x) = já _ {[0, c)} (x)}$, kde ${ displaystyle I (x)}$ je indikátorová funkce. Situace pro${ displaystyle {E_ {mb} T_ {na} g } _ {m, n v Z}}$ být rámem stojí následovně.

1) ${ displaystyle a> c}$ nebo ${ displaystyle a> 1}$, ne rám

2) ${ displaystyle c> 1}$ a ${ displaystyle a = 1}$, ne rám

3) ${ displaystyle a leq c leq 1}$, je rám

4) ${ displaystyle a <1}$ a je iracionální, a ${ displaystyle c v (1,2)}$, je rám

5) ${ displaystyle a = { frac {p} {q}} <1}$, ${ displaystyle p}$ a ${ displaystyle q}$ jsou relativně prvočísla, ${ displaystyle 2 - { frac {1} {q}}$, ne rám

6) ${ displaystyle { frac {3} {4}}$ a ${ displaystyle c = L-1 + L (1-a)}$, kde ${ displaystyle L geq 3}$ a být přirozeným číslem, ne rámečkem

7) ${ displaystyle a <1}$, ${ displaystyle c> 1}$, ${ displaystyle | c- [c] - { frac {1} {2}} | <{ frac {1} {2}} - a}$, kde ${ displaystyle [c]}$ je největší celé číslo nepřesahující ${ displaystyle c}$, je rám.

Výše uvedená diskuse je souhrnem kapitoly 8 v.^[8]

Wavelet rámy

Kolekce wavelet obvykle odkazuje na sadu funkcí založených na ${ displaystyle psi}$

${ displaystyle {2 ^ { frac {j} {2}} psi (2 ^ {j} x-k) } _ {j, k v Z}}$

To tvoří ortonormální základ pro ${ displaystyle L ^ {2} (R)}$. Kdy však ${ displaystyle j, k}$ může nabývat hodnot v${ displaystyle R}$, sada představuje překompletovaný rámec a nazývá se undecimovaný základ waveletů. Obecně je awavelet rámec definován jako rámec pro ${ displaystyle L ^ {2} (R)}$ formuláře

${ displaystyle {a ^ { frac {j} {2}} psi (a ^ {j} x-kb) } _ {j, k v Z}}$

kde ${ displaystyle a> 1}$, ${ displaystyle b> 0}$, a ${ displaystyle psi v L ^ {2} (R)}$Horní a dolní mez tohoto rámečku lze vypočítat následovně ${ displaystyle { hat { psi}} ( gamma)}$ být Fourierovou transformací pro ${ displaystyle psi v L ^ {1} (R)}$

${ displaystyle { hat { psi}} ( gamma) = int _ {R} psi (x) e ^ {- 2 pi ix gamma} dx}$

Když ${ displaystyle a, b}$ jsou pevné, definujte

${ displaystyle G_ {0} ( gamma) = součet _ {j v Z} | { hat { psi}} (a ^ {j} gamma) | ^ {2}}$

${ displaystyle G_ {1} ( gamma) = součet _ {k neq 0} součet _ {j v Z} | { hat { psi}} (a ^ {j} gamma) { klobouk { psi}} (a ^ {j} gamma + { frac {k} {b}}) |}$

Pak

${ displaystyle B = { frac {1} {b}} sup _ {| gamma | v [1, a]} (G_ {0} ( gamma) + G_ {1} ( gamma)) < infty}$

${ displaystyle A = { frac {1} {b}} inf _ {| gamma | v [1, a]} (G_ {0} ( gamma) -G_ {1} ( gamma)) > 0}$

Kromě toho, když

${ displaystyle sum _ {j v Z} | { hat { psi}} (2 ^ {j} gamma) | ^ {2} = A}$

${ displaystyle sum _ {j = 0} ^ { infty} { hat { psi}} (2 ^ {j} gamma) { overline {{ hat { psi}} (2 ^ {j } ( gamma + q))}} = 0}$, pro všechna lichá celá čísla ${ displaystyle q}$

generovaný snímek ${ displaystyle { psi _ {j, k} } _ {j, k v Z}}$ je těsný rám.

Diskuse v této části je založena na kapitole 11 v.^[8]

Aplikace

Přeplněné rámce Gabor a rámce Wavelet byly použity v různých oblastech výzkumu, včetně detekce signálu, reprezentace obrazu, rozpoznávání objektů, redukce hluku teorie vzorkování, teorie operátorů, harmonická analýza, nelineární řídká aproximace, pseudodiferenciální operátory, bezdrátová komunikace, geofyzika, kvantové výpočty a filtrovat banky.^[3][8]

Reference