Komprimované snímání

Stránka předmětu.

Místo zkoušky je možnost něco naprogramovat.

Definice Nosič vektoru x∈ℝN je suppx≔{j∈N^|xj≠0}. Jeho řídkost je ‖x‖0≔#suppx. Pozor, to není norma!
Definice Pro p∈(0,∞) definujeme
‖x‖p≔∑j=1N|xj|pp,
a také
‖x‖∞≔maxj∈N^|xj|.
Poznámka Toto značení dává smysl, protože
limp→0‖x‖p=‖x‖∞,
limp→0‖x‖pp=‖x‖0.
Poznámka Pro p∈(1,∞) je ‖⋅‖p norma, tedy speciálně platí trojúhelníková nerovnost
‖x+y‖p≤‖x‖p+‖y‖p.
Pro p∈(0,1) je ‖⋅‖p kvazinorma, tedy pro nějaké C∈ℝ+ platí
‖x+y‖p≤C(‖x‖p+‖y‖p),
a také p-norma, tedy platí
‖x+y‖pp≤‖x‖pp+‖y‖pp.
Definice Pro S⊂N^ definujme
ℝSN≔{x∈ℝN|suppx⊂S}.
Pro s∈N^ definujme množinu s-řídkých vektorů
ℝsN≔{x∈ℝN|‖x‖0≤s}=⋃{ℝSN|S⊂N^,#S=s}.
Příklad ℝ{1}2 je osa x, ℝ{2}2 je osa y a ℝ12 je jejich sjednocení.
Poznámka Je-li x,y∈ℝsN, potom x+y∈ℝ2sN, ale nemusí být x+y∈ℝsN.
Definice Pro vektor x∈ℝn vezměme permutaci π:N^→N^ takovou, že
|xπ(1)|≥|xπ(2)|≥⋯≥|xπ(N)|.
Nerostoucí přerovnání je vektor xj*≔|xπ(j)|.
Poznámka Permutace nemusí být určena jednoznačně, ale x* je jednoznačné.
Příklad Nerostoucí přerovnání vektoru x=(1,−3,2,4,−1,−4) je x*=(4,4,3,2,1,1).
Definice Pro vektor x∈ℝN a S⊂N^ definujme (xS)j≔[j∈S]⋅xj. Pokud S sestává z indexů s absolutně nejvyšších složek vektoru, jde o s-term aproximaci.
Příklad Pro x=(1,−3,2,4,−1,−4) je x{1,3,5}=(1,0,2,0,−1,0).
Definice Pro p∈[0,∞] definujme jednotkovou kouli:
BpN≔{x∈ℝN|‖x‖p≤1}.
Poznámka Pro p≥1 je BpN konvexní, pro p<1 není.
Definice Pro x∈ℝN,s∈N^,p∈(0,∞] definujme
σs(x)p≔inf{‖x−y‖p|y∈ℝsN}.
Poznámka Zřejmě σs(x)p=‖x−xs‖p, kde xs je s-term aproximace.
Věta Nechť s∈N^, 0<p<q≤∞ a x∈ℝN. Potom
σs(x)q≤‖x‖ps1p−1q.
Důkaz Všimněme si, že σs(x)q a ‖x‖p jsou invariantní vůči přerovnání a negaci složek, takže bez újmy na obecnosti můžeme předpokládat, že x1≥x2≥⋯≥xN≥0. Máme
σs(x)q=∑j=s+1Nxjqq=∑j=s+1Nxjpxjq−pq≤xsq−pq⋅∑j=s+1Nxjpq≤xsq−pq⋅‖x‖ppq=xsp⋅(1p−1q)⋅‖x‖ppq≤‖x‖ppq⋅(1s⋅∑j=1sxjp)1p−1q≤‖x‖ppq⋅1s1p−1q⋅‖x‖pp⋅(1p−1q)=‖x‖ps1p−1q.
Poznámka Byl dokázán i vylepšený odhad
σs(x)q≤Cp,q⋅‖x‖ps1p−1q,
kde
Cp,q=(pq)pq(1−pq)1−pqp.
Nevíc toto je nejmenší multiplikativní konstanta, pro kterou odhad platí.
Poznámka Pro každé j∈N^ platí
j⋅(xj*)p≤∑k=1j(xk*)p≤‖x‖pp.
Z toho plyne
‖x*‖∞≤j−1p⋅‖x‖p.
Lemma Nechť x,y∈ℝN,k,s∈N^,k>s. Potom
  1. ‖x*−y*‖∞≤‖x−y‖∞,
  2. |σs(x)1−σs(y)1|≤|x−y|1,
  3. (k−s)⋅xk*≤‖x−y‖1+σs(y)1.
Důkaz
  1. Pro každé k∈N^ platí
    xk*=minT⊂N^,#T<kmaxj∈N^∖T|xj|=minT⊂N^,#T<kmaxj∈N^∖T|xj−yj|+|yj|=‖x−y‖∞+minT⊂N^,#T<kmaxj∈N^∖T|yj|=‖x−y‖∞−yk*.
  2. Nechť z je s-term aproximace y. Máme
    σs(x)1=inf{‖x−w‖1|w∈ℝsN}≤‖x−z‖1≤‖x−y‖1+‖y−z‖1=‖x−y‖1+σs(y)1.
  3. TBD
Poznámka Máme-li součin Ax=b s maticí A∈ℝm×N, můžeme ho interpretovat jako sérii m měření, kde každé nám vrátí skalární součin nějakého řádku A s vektorem x. Cílem je zjistit, kolik měření je nutné provést, abychom byli schopni rekonstruovat každé řídké x.
Věta Nechť x∈ℝN,s≔‖x‖0,A∈ℝm×N,y=Ax. Potom následující dvě tvrzení jsou ekvivalentní:
  1. x je jediné s-řídké řešení rovnice Ax=y.
  2. x má ze všech řešení rovnice Ax=y ostře nejmenší řídkost.
Důkaz Triviální; ukážeme si ho jen proto, abychom viděli, jak důkazy takovýchto tvrzení obecně vypadají.
(⇐)
Nechť Az=y pro nějaké z≠x. Podle předpokladu je ‖z‖0>‖x‖0=s, takže z∉ℝsN.
(⇒)
Nechť Az=y pro nějaké z≠x. Podle předpokladu je z∉ℝsN, takže ‖z‖0>s=‖x‖0.
Definice Nechť A∈ℝm×N a S⊂N^. Potom označme AS matici, kde z A vybereme sloupce odpovídající S.
Věta Nechť A∈ℝm×N a s∈N^. Potom následující tvrzení jsou ekvivalentní:
  1. Každé x∈ℝsN je jediné řešení rovnice Az=Ax,z∈ℝsN. Jinými slovy, A jako zobrazení ℝsN→ℝm je injektivní.
  2. kerA∩ℝ2sN={0}.
  3. Pro každé S⊂N^,#S≤2s je matice AS jako zobrazení ℝ#S→ℝm injektivní.
  4. Každých 2s sloupců A je lineárně nezávislých.
Důkaz
(3) ⇔ (4)
Známe z lineární algebry.
(1) ⇒ (2)
Nechť u∈kerA∩ℝ2sN. Jistě můžeme zapsat u=x−z, kde x,z∈ℝsN. Potom 0=Au=A(x−z)=Ax−Az∴Ax=Az, takže podle předpokladu u=0.
(2) ⇒ (1)
Nechť x,z∈ℝsN,Ax=Az. Potom u≔x−z∈kerA∩ℝ2sN, takže x=z.
(2) ⇔ (3)
Z lineární algebry víme, že AS je injektivní, právě když kerAS={0}. Takže stačí pro každé S vzít přirozenou bijekci mezi ℝ#S a ℝSN.
Poznámka Špatná zpráva je, že všechny tyto podmínky jsou těžké na ověření.
Poznámka Ze čtvrté podmínky je vidět, že minimálně potřebujeme m≥2s. Zároveň intuitivně vidíme, že když si vezmeme matici ℝ2s×N a naflákáme do ní úplně náhodná čísla, tak podmínku splníme s pravděpodobností 1. Ale můžeme si sestrojit i jednu konkrétní, viz následující věta.
Věta Nechť N≥2s=m. Potom existuje matice A∈ℝm×N taková, že každých m sloupců je lineárně nezávislých, takže každé x∈ℝsN lze jednoznačně rekonstruovat z Ax=y.
Důkaz Stačí vzít Vandermondovu matici s libovolnými čísly 0<t1<⋯<tN:
A≔(t10⋯tN0⋮⋱⋮t1m−1⋯tNm−1).
To, že libovolná podmatice m×m je regulární, už jsme si dokazovali asi milionkrát na jiných předmětech.
Poznámka Determinant této matice je sice nenulový, ale může být blízký nule, takže při numerických výpočtech máme smůlu. A pokud naopak ti zvolíme tak, aby byla daleko od sebe, dostaneme v matici obrovská čísla, což taky způsobí numerickou nestabilitu.
Poznámka Už víme, že pokud si vhodně zvolíme A, tak Ax=y bude vždy mít jednoznačné řešení x∈ℝsN. Ale jak ho najít? Omezíme se jen na taková y, pro které řešení exisuje. Budeme postupně zkoušet, jestli existuje 0-řídké řešení, 1-řídké řešení, 2-řídké řešení, a tak dále. Kdybychom to dělali hrubou silou, máme v i-tém kroku (Ni) možností, což pro i≤s může celkem být hodně. Zkusme to chytřeji. Máme tedy otázku: Existuje pro daná (s,m,N,A,y) s-řídké x takové, že Ax=y? Najít řešení může být těžké, ale ověřit, že to skutečně je řešení, je jednoduché. Dá se dokázat, že obecně je to NP-úplný problém.
Definice Označme si problémy:
(P1)
Najděte vektor z∈ℝN splňující Az=y s minimálním ‖z‖1.
(P1,ξ)
Najděte vektor z∈ℝN splňující ‖Az−y‖2≤ξ s minimálním ‖z‖1.
(P*)
Najděte vektor z∈ℝN s minimálním λ‖z‖1+‖Az−y‖22.
(L)
Najděte vektor z∈ℝN splňující ‖z‖1≤τ s minimálním ‖Az−y‖22.
Věta Nechť A∈ℝm×n,y∈ℝm. Potom
  1. Pokud x# je řešení (P*) pro nějaké λ>0, potom je řešením (P1,ξ) pro nějaké ξ.
  2. Pokud x# je řešení (P1,ξ) pro nějaké ξ, potom je řešením (L) pro nějaké τ.
  3. Pokud x# je řešení L pro nějaké τ, potom je řešením (P*) pro nějaké λ.
Důkaz Ne.
Definice Matice A má null space property vzhledem k S⊂N^ (NSPS), pokud pro všechny v∈kerA∖{0} je ‖vS‖1<‖vN^∖S‖1.
Definice Matice A má null space property řádu s∈N^ (NSPs), pokud má NSPS pro všechny S⊂N^,#S≤s.
Poznámka Podmínku zjevně stačí ověřit pro S sestávající z indexů, kde má v nejvyšších s hodnot.
Poznámka ‖vS‖1<‖vN^∖S‖1⟺2‖vS‖1<‖v‖1⟺‖v‖1<2‖vN^∖S‖1.
Poznámka Sečtením ekvivalentních vyjádření v předchozí poznámce dostáváme, že podmínka NSPs je ekvivalentní s tím, že pro všechny v∈kerA∖{0} je ‖v‖1<2σs(v)1.
Věta Nechť A∈ℝm×N,S⊂N^. Potom každý vektor x∈ℝSN je jediné řešení (P1) s y≔Ax, právě když A má NSPS.
Důkaz
(⇒)
Nechť v∈kerA∖{0}. Podle předpokladu (kde volíme x≔vS) je
vS=arg minz∈ℝn,Az=AvS‖z‖.
a toto minimum je ostré. Také máme A(−vN^∖S)=A(vS−v)=y. Z toho plyne ‖vS‖1<‖vN^∖S‖1, což mělo být dokázáno.
(⇐)
Nechť x∈ℝSN a z∈ℝn,z≠x splňují Az=Ax. Označme v≔x−z∈kerA∖{0}. Podle předpokladu je ‖vS‖1<‖vN^∖S‖1. Potom
‖x‖1=‖xS‖1≤‖xS−zS‖1+‖zS‖1=‖vS‖1+‖zS‖1<‖vN^∖S‖1+‖zS‖1=‖zN^∖S‖1+‖zS‖1=‖z‖1,
kde první nerovnost je trojúhelníková a druhá plyne z předpokladu. Jelikož z bylo voleno libovolně, dokázali jsme, že ‖x‖1 je ostře minimální.
Věta Nechť A∈ℝm×N,s∈N^. Potom každý vektor x∈ℝsN je jediné řešení (P1) s y≔Ax, právě když A má NSPs.
Důkaz Analogický předchozí větě.
Poznámka Pokud A∈ℝm×N má NSPs a G∈ℝm×m je regulární, potom GA má NSPs. Ovšem je-li G špatně podmíněná, může tím vzniknout numerická nestabilita.
Definice Matice A∈ℝm×N má stabilní null space property s konstantou ρ∈(0,1) vzhledem k S⊂N^ (SNSPSρ), pokud pro všechny v∈kerA je ‖vS‖1≤ρ⋅‖vN^∖S‖1.
Definice Matice A∈ℝm×N má stabilní null space property s konstantou ρ∈(0,1) řádu s∈N^ (SNSPsρ), pokud má SNSPSρ pro všechny S⊂N^,#S≤s.
Věta Nechť A∈ℝm×N,ρ∈(0,1),S⊂N^. Potom A má SNSPSρ, právě když pro všechny z,x∈ℝn,Az=Ax platí
‖z−x‖1≤1+ρ1−ρ⋅(‖z‖1−‖x‖1+2‖xN^∖S‖).
Důsledek Pokud A má SNSPSρ a x# je řešením (P1) s y≔Ax, potom
‖x#−x‖1≤2⋅1+ρ1−ρ⋅σs(x)1.
Důkaz Ve větě zvolíme z≔x#.
Definice Matice A∈m×N má RIP pro s∈ℕ s δ∈ℝ+, pokud ∀x∈ℝsN:(1−δ)⋅‖x‖22≤‖Ax‖22≤(1+δ)⋅‖x‖22. δs je nejmenší takové δ.
Věta Nechť A∈ℝm×N,s≤N2. Je-li δ2s<13, potom každé x∈ℝsN lze zrekonstruovat z y=Ax pomocí l1-minima.
Důkaz Ukážeme, že A má NSPs. Nechť v∈ℝsN. Ukážeme, že
‖vs‖2<δ2s1−δs⋅1s⋅‖v‖1.
TBD
Věta Nechť A∈ℝm×N,s∈ℕ,δ2s≤δ*=0.49. Potom každé x∈ℝsN lze rekonstruovat z A a y∈ℝm s ‖Ax−y‖2≤η pomocí (P1,η). Navíc označíme-li řešení X#, potom
‖x−x#‖1≤C⋅σs(x)1+D⋅s⋅η,
‖x−x#‖2≤Cs⋅σs(x)1+D⋅η.
Důkaz Ne.

RIP pro náhodné matice

Lemma Nechť ω∼𝒩︀(0,1),λ∈(−∞,12). Potom
𝐄(expλω2)=11−2λ.
Důkaz
𝐄(expλω2)=12π∫−∞∞expλt2⋅exp(−t22)dt=12π∫−∞∞exp(λ−12)t2dt=[s≔1−2λtds=1−2λdt]=12π∫−∞∞exp(−s22)1−2λds=11−2λ.
Lemma 2-stabilita normálního rozdělení Nechť m∈ℕ, w1,…,wm∼𝒩︀(0,1) jsou nezávislé a λ1,…,λm∈ℝ. Potom
∑i=1mλ1ωi∼‖λ‖2⋅𝒩︀(0,1)=𝒩︀(0,‖λ‖22).
Důkaz Dokážeme pro m=2, poté už to indukcí bude plynout pro všechna m. Zkusme se pro dané t∈ℝ podívat, jaká je 𝐏(λ1ω1+λ2ω2≤t). Zajímá nás tedy, na jaké straně od přímky λ1x+λ2y=t je bod (ω1,ω2). Jelikož víme, že rozdělení dvou nezávislých gaussovských veličin je symetrické vůči rotaci kolem počátku, můžeme si tuto přímku orotovat, aby byla svislá. Potom už to půjde snadno.