AdamátorZápiskyHlášky

Komprimované snímání

Přednášejícíprof. RNDr. Jan Vybíral, Ph.D.
WebWebová stránka předmětu
Semestrzima 2024
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.
Lemma Nechť ω1,…,ωm jsou nezávislé s rozdělením 𝒩(0,1) a ε∈(0,1). Potom
𝐏(∑i=1mωi2≥(1+ε)m)≤exp(−m2⋅(ε22−ε33)).
Důkaz Laplaceovou metodou Označme β≔1+ε a zvolme nějaké λ∈(0,12).
𝐏(∑i=1mωi2≥βm)=𝐏(∑i=1mωi2−βm≥0)=𝐏(λ∑i=1mωi2−λβm≥0)=𝐏(exp(λ∑i=1mωi2−λβm)≥1)≤Markov𝐄exp(λ∑i=1mωi2−λβm)=exp(−λβm)⋅𝐄∏i=1mexp(λωi2)=nezávislostexp(−λβm)⋅(𝐄exp(λω12))m=exp(−λβm)⋅(1−2λ)m2
Pomocí derivace snadno zjistíme, že tento výraz nabývá maxima pro λ=ε2β. To je skutečně v intervalu (0,12), takže to můžeme dosadit a dostaneme
𝐏(∑i=1mωi2≥βm)=exp(−mε2)⋅(1+ε)m2=exp(−m2(ε−ln(1+ε))).
Použitím odhadu ln(1+ε)≤ε−ε22+ε33 dostaneme kýženou rovnost.
Poznámka Toto lemma se občas označuje jako „neasymptotické“, protože nás nezajímá, co se děje, když m→∞.
Poznámka Analogicky se dá dokázat
𝐏(∑i=1mωi2≤(1−ε)m)≤exp(−m2⋅(ε22−ε33)).
Lemma můžeme přeformulovat jako
𝐏(|∑i=1mωi2−m|≥εm)≤2⋅exp(−m2⋅(ε22−ε33))
nebo
𝐏(|1m∑i=1mωi2−1|≥ε)≤2⋅exp(−m2⋅(ε22−ε33)).
Věta RIP pro jeden bod Nechť ω je náhodná matice řádu m×N s nezávislými prvky s rozdělením 𝒩(0,1), A≔ωm a x∈ℝN,‖x‖2=1. Potom
𝐏(|‖Ax‖22−1|≥t)≤2⋅exp(−m2(t22−t33)).
Důkaz Máme
‖Ax‖22=1m∑i=1m∑j=1N(ωi,jxj)2∼1m∑i=1m(‖x‖2⋅ωi,1)2.
Nyní stačí použít lemma.
Poznámka Snadno odhadneme
2⋅exp(−m2(t22−t33))≤2⋅exp(−mt224).
Definice Jednotková sféra dimenze d−1 je 𝕊d−1≔{x∈ℝd|‖x‖2=1}.
Definice Nechť t>0. Množina 𝒩⊂M je t-síť množiny M, pokud ∀z∈M,∃x∈𝒩:‖z−x‖2≤t.
Lemma Nechť t>0. Potom existuje t-síť 𝒩∈𝕊d−1 s #𝒩≤(1+2t)d.
Důkaz Síť budeme konstruovat hladovým algoritmem – postupně přidáváme body x1,x2,… tak, že bod xi není pokrytý body x1,…,xi−1. Jelikož 𝕊d−1 je kompaktní, jistě někdy skončíme. Nechť N je počet bodů sítě. Koule B(xi,t2), jsou zjevně disjunktní podmnožiny B(0,1+t2). Jelikož objem d-rozměrného tělesa je úměrná d-té mocnině jeho velikosti, máme
N⋅V(B(0,t2))=∑i=1NV(B(xi,t2))≤V(B(0,1+t2))=(1+t2t2)dV(B(0,t2))=(1+2t)dV(B(0,t2)).
Podělením dostaneme kýženou nerovnost.
TBD: doplnit zápisky

Optimalita

Je zřejmé, že k rekonstrukci vektorů z ℝsN potřebujeme minimálně m≥s. Zároveň jsme si již dokázali, že stačí m≥C⋅s⋅lnN. Ale nemohlo by to jít i lépe?
Lemma Nechť s≤N∈ℕ. Potom existují množiny T1,…,TM⊂N^ takové, že
Důkaz Použijeme hladový algoritmus. Budeme postupně volit libovolné množiny tak, aby poslední dvě vlastnosti zůstaly zachované. Skončíme, až nebude existovat další množina, kterou bychom mohli použít. Stačí dokázat, že jsme jich vybrali aspoň (N4s)s2. Počet množin, které se zablokují po vybrání každé nové množiny, je nanejvýš
∑j=⌈s2⌉s(sj)⋅(N−ss−j)≤(∑j=⌈s2⌉s(sj))⋅max⌈s2⌉≤j≤s(N−ss−j)≤2s⋅(N−s⌊s2⌋).
Tedy po vybrání m množin jich stále zbývá alespoň
(Ns)−m⋅2s⋅(N−s⌊s2⌋).
Z toho plyne
M≥(Ns)2s⋅(N−s⌊s2⌋)≥2−s⋅(Ns)(N−⌈s2⌉⌊s2⌋)=2−s⋅n!s!⋅⌊s2⌋!(N−⌈s2⌉)!=2−s⋅N⋅(N−1)⋅⋯⋅(N−⌈s2⌉+1)s⋅(s−1)⋅⋯⋅(s−⌈s2⌉+1)≥2−s⋅(Ns)⌈s2⌉≥(N4s)s2.
Věta Nechť s≤m≤N,A∈ℝm×N a zobrazení Δ:ℝm→ℝN splňuje
∀x∈ℝN:‖x−Δ(Ax)‖2≤C⋅σs(x)1s.
Potom m≥C′⋅s⋅lneNs.
Důkaz Předpokládejme, že C≥1,s≤N8. Najdeme množiny T1,…,TM podle předchozího lemmatu. Definujeme body
x1,…,xM∈ℝsN,xi≔χTi⋅1s.
Z konstrukce plyne ‖xi‖2=1, ‖xi‖1=s a ‖xi−xj‖2>1.Definujme
ℬ≔{z∈ℝN|‖z‖1≤s4C∧‖z‖2≤14}.
Máme xi∈4⋅C⋅ℬ. Dokážeme, že množiny A(xi+ℬ) jsou po dvou disjunktní. Nechť pro spor existují i≠j a zi,zj∈ℬ taková, že A(xi+zi)=A(xj+zj). Potom
1<‖xi−xj‖2=‖((xi+zi)−Δ(A(xi+zi)))−((xj+zj)−Δ(A(xj+zj)))−zi+zj‖2≤‖(xi+zi)−Δ(A(xi+zi))‖2+‖(xj+zj)−Δ(A(xj+zj))‖2+‖zi‖2+‖zj‖2≤14+14+14+14=1.
Dále A(xi+ℬ)⊂A((4C+1)ℬ). Nechť bez újmy na obecnosti je h(A)=m. Použijeme objemový argument:
∑i=1MVm(A(xi+ℬ))≤Vm(A((4C+1)ℬ))
neboli
M⋅Vm(A(ℬ))≤Vm((4C+1)A(ℬ))≤(4C+1)m⋅Vm(A(ℬ)).
Podělením a drobnými úpravami dostaneme kýženou nerovnost.

Kashinův rozklad

Věta Existují konstanty α,β>0 takové, že pro každé m≥1 lze v ℝ2m najít E,E⟂⋐ℝ2m,dimE=m takové, že pro všechna x∈E∪E⟂ je
αm‖x‖2≤‖x‖1≤βm‖x‖2.