(T.Werner, V.Franc 2014+)

Tato domácí úloha má tři podúlohy. Zadání se může zdát dlouhé, ale každou požadovanou funkci lze napsat na pár řádků. Výstupem domácí úlohy budou .m soubory a zpráva (společná pro všechny podúlohy) v PDF. Ve zprávě nemusí být nic víc, než co je požadováno v zadání. Zabalte soubory .pdf a .m do souboru .zip (bez podadresářů) a nahrajte do Brute. Podpůrné funkce a data nemusíte do zipu přidávat.

Jsou dány body $\_a_1,\ldots,\_a_n\in\R^m$ a přirozené číslo $k\le m$. Najděte body $\_b_1,\ldots,\_b_n\in\R^m$ takové, aby ležely v nějakém (lineárním) podprostoru dimenze $k$ prostoru $\R^m$ a byly co nejblíže bodům $\_a_1,\ldots,\_a_n$ ve smyslu nejmenších čtverců, tj. minimalizovaly výraz \begin{equation} \sum_{i=1}^n\|\_a_i-\_b_i\|^2. \label{eq:obj} \end{equation} Zdůrazněme, že zmíněný podprostor je také neznámý, máme ho najít zároveň s body $\_b_1,\ldots,\_b_n$. Tento podprostor budeme reprezentovat jeho ortonormální bází $\_u_1,\ldots,\_u_k\in\R^m$. Dále máme najít souřadnice $c_{11},\ldots,c_{kn}$ nalezených bodů $\_b_1,\ldots,\_b_n$ v této bázi, tedy \begin{equation} \_b_j = \sum_{i=1}^k c_{ij}\_u_i = \_U\_c_j \qquad\forall j=1,\dots,n \label{eq:coords} \end{equation} kde $\_U\in\R^{m\x k}$ je matice se sloupečky $\_u_1,\ldots,\_u_k$ (splňující $\_U^T\_U=\_I$) a $\_c_j\in\R^k$ je vektor s prvky $c_{1j},\dots,c_{kj}$.

Někdy řešíme pozměněnou úlohu: k daným bodům $\_a_1,\ldots,\_a_n\in\R^m$ hledáme body $\_b_1,\ldots,\_b_n\in\R^m$, které leží v afinním podprostoru dimenze $k$ a minimalizují chybu \eqref{eq:obj} Pak místo \eqref{eq:coords} máme \begin{equation} \_b_j = \_b_0 + \_U\_c_j \qquad\forall j=1,\dots,n , \label{eq:coords-aff} \end{equation} kde $\_b_0\in\R^m$ je (neznámé) posunutí afinního podprostoru vůči počátku.

Nahrazení sekvence $\_a_1,\ldots,\_a_n$ sekvencí $\_c_1,\dots,\_c_n$ lze vnímat jako kompresi dat: druhá sekvence obsahuje typicky daleko méně čísel než první (velikost báze $\_U$ je zanedbatelná).

Je výhodné uspořádat vektory $\_a_1,\ldots,\_a_n\in\R^m$, $\_b_1,\ldots,\_b_n\in\R^m$, $\_c_1,\ldots,\_c_n\in\R^k$ do sloupců matic $\_A\in\R^{m\x n}$, $\_B\in\R^{m\x n}$, $\_C\in\R^{k\x n}$ (pozor: ve skriptech jsme je dávali do řádků). Pak účelovou funkci \eqref{eq:obj} můžeme napsat jako $\|\_A-\_B\|^2$ (kde $\|\cdot\|$ je zde Frobeniova norma) a rovnici \eqref{eq:coords} příp. \eqref{eq:coords-aff} jako $\_B = \_U\_C$ příp. $\_B=\_b_0\_1^T+\_U\_C$.

Úkoly:

1. Nastudujte příslušnou látku z přednášek. Navrhněte řešení popsaných úloh (včetně vzorce pro matici $\_C$).
   Výstup úkolu (do zprávy): popis algoritmu a jeho odůvodnění
2. Implementujte matlabskou funkci [U,C]=fitlin(A,k), jejímž vstupem je matice $\_A$ a číslo $k$ a výstupem jsou matice $\_U$ a $\_C$, které minimalizují \eqref{eq:obj} za podmínky \eqref{eq:coords}.
   Výstup úkolu: soubor fitlin.m.
3. Implementujte funkci [U,C,b0]=fitaff(A,k), jejímž vstupem je matice $\_A$ a číslo $k$ a výstupem jsou matice $\_U,\_C$ a vektor $\_b_0$, které minimalizují \eqref{eq:obj} za podmínky \eqref{eq:coords-aff}.
   Výstup úkolu: soubor fitaff.m.

Poznámky:

• Předpokládejte, že nejen $k\le m$ ale i $k\le n$.
• Neměli byste nikde vytvořit matici rozměru $n\x n$, protože počet bodů $n$ může být veliký.
• Implementované funkce nemají nic vypisovat ani vykreslovat, mají jen vrátit požadovaný výstup.
• Smíte používat jen základní funkce Matlabu (tedy žádné tooboxy), viz stránka cvičení.
• Funkci fitlin lze napsat na 4 řádky, funkci fitaff na 3 řádky.

Nyní použijete výsledek výše na prokládání množiny bodů v rovině přímkou ($m=2$ a $k=1$), která nemusí procházet počátkem. Představte si např., že někdo body naklikal myší v grafickém rozhraní (to můžete udělat v Matlabu sami příkazem ginput) a vaším úkolem je proložit jimi nejlepší přímku.

Úkoly:

1. Implementujte funkci drawfitline(A), která má na vstupu matici $\_A\in\R^{2\x n}$ se zadanými body a nakreslí optimální přímku zeleně, body $\_a_1,\dots,\_a_n$ jako červené křížky, a $n$ červených úseček kde $i$tá úsečka spojuje bod $\_a_i$ s bodem $\_b_i$. Funkci si můžete vyzkoušet na matici $\_A$ v souboru line.mat (nahrajete ho příkazem load line).
   Výstup úkolu: soubor drawfitline.m.
   Poznámky:
   • Uvědomte si, že místo přímky musíte vlastně nakreslit úsečku (protože přímka je nekonečná a na obrazovku se nevejde) a tedy musíte nějak rozumně zvolit koncové body této úsečky.
   • Pro vykreslení použijte příkazy plot, hold on, hold off. Po vykreslení zavolejte příkaz axis equal, aby měřítko obou os bylo stejné.
   • Uvintř funkce neotvírejte ani nezavírejte matlabský obrázek (tj. nevolejte funkce figure ani close).
   • Funkci lze napsat do 15 řádků.
2. Nalezněte požadovanou přímku pro body ze souboru line.mat ve dvou různých reprezentacích: \begin{equation}\{\, \_b_0+\_uc \mid c\in \R \,\} = \{\,\_b\in\R^2\mid \_x^T\_b = y \,\}. \end{equation} Vektory zvolte tak, aby $\|\_x\|=\|\_u\|=1$ a aby norma $\|\_b_0\|$ byla nejmenší možná (tj. aby $\|\_b_0\|$ byla vzdálenost přímky od počátku $\_0$).
   Výstup úkolu (do zprávy): teoretický postup, vektory $\_b_0,\_u,\_x\in\R^2$ a skalár $y\in\R$.

Při tvorbě počítačových her nebo filmů se používá technologie motion capture. Na živého herce se připevní terčíky odrážející infračervené světlo. Terčíky se připevňují na významné body na těle, jako klouby apod. Speciální soustava kamer snímají polohy terčíků a z těch se počítá poloha každého terčíku v třírozměrném prostoru pro každý snímek. Polohy terčíků v prostoru se pak použijí např. pro animaci postav syntetizovaných počítačovou grafikou. Viz např. wikipedie.

Pro získání plynulého pohybu je třeba snímat s vysokou frekvencí. Například data použitá v naší úloze byla snímána s vzorkovací frekvencí 120 Hz. Ve výsledku je pak třeba pracovat s velkými objemy dat, což je nevýhoda. Naším úkolem bude snížit objem dat tak, abychom ztratili co nejméně informace.

Prostorová poloha jednoho terčíku v jednom snímku je dána trojicí souřadnic. V našem případě máme $\ell=41$ terčíků. Poloha všech terčíků v jednom snímku je dána vektorem $\_a\in\R^m$ kde $m=3\ell$. Ten si lze představit jako bod v $m$-rozměrném prostoru. Celkově máme $n$ snímků, tedy vektory $\_a_1,\ldots,\_a_n\in\R^m$.

Hledáme body, které co nejlépe aproximují původní body a zároveň se dají reprezentovat menším objemem dat. Přesněji, hledáme body $\_b_1,\ldots,\_b_n$, které leží v afinním podprostoru dané dimenze $k<m$ a minimalizují chybu \eqref{eq:obj}.

Úkoly:

1. Stáhněte si data (tanec Macarena nastudujte zde a zde). Každý soubor obsahuje jednu matici $\_A$, nahrajete ji příkazem A=load('soubor.txt')' (pozor na transpozici). Pro vizualizaci sekvencí použijte příkaz playmotion(conn,A) (vyžaduje funkci playmotion.m a soubor connected_points.txt, který nahrajete příkazem conn=load('connected_points.txt')).
   Výstup úkolu: nic.
2. Aproximujte sekvenci příkazem [U,C,b0]=fitaff(A,k) pro různě zvolená $k\in\{1,\dots,m\}$, aproximovaná sekvence je pak dána vzorcem \eqref{eq:coords-aff}. Obě sekvence zároveň si přehrajte příkazem playmotion(conn,A,B). Pokud máte vše správně, sekvence si budou podobné. Zkoušejte, jak se mění kvalita aproximace pro různá $k$ a různé sekvence. Dumejte, proč se některé sekvence lépe komprimují (stačí menší $k$) než jiné.
   Výstup úkolu: nic.
3. Nahrazení sekvence $\_a_1,\dots,\_a_n$ sekvencí $\_c_1,\dots,\_c_k$ může mít i jiné výhody než kompresi: protože druhá sekvence 'žije' v prostoru nižší dimenze, dá se např. snadněji zobrazit (vizualizace dat) či rozpoznat z ní typ pohybu herce (pattern recognition). Zkuste si to: pro $k\in\{2,3\}$ si zobrazte trajektorii bodu $\_c_i$ v rovině jako funkci času $i$, kde po sobě jdoucí body spojíte úsečkami (použijte příkaz plot příp. plot3; pro $k=3$ si na matlabském okně s obrázkem zvolte rotaci a točte si 3-D grafem v prostoru). Všimněte si, jak se trajektorie liší pro různé vstupní sekvence (walk1, makarena1, …). Implementujte funkci plottraj2(C) se vstupem $\_C\in\R^{2\x n}$, která zobrazí tuto trajektorii pro $k=2$.
   Výstup úkolu: soubor plottraj2.m.
4. Chceme spočítat optimální chybu aproximace \eqref{eq:obj} pro všechny dimenze $k=1,\dots,m$ afinního podprostoru. Dostaneme tedy čísla $d_1,\dots,d_k$, kde $d_k$ je chyba aproximace pro dimenzi $k$. Jaký vztah mají tato čísla k vlastním a singulárním číslům (a jakých matic)? Implementujte funkci d=erraff(A), která pro sekvenci $\_A\in\R^{m\x n}$ spočítá tato čísla a uloží je do vektoru $\_d\in\R^m$ (funkce nemá nic vypisovat ani vykreslovat). Ve funkci erraff smíte zavolat matlabskou funkci eig příp. svd jen jednou.
   Výstup úkolu: vysvětlení (do zprávy), soubor erraff.m.
5. Uvažujte že postava dělá čistý translační pohyb, tj. konfigurace bodů se nemění a jejich souřadnice se pohybují po přímce. Jaká je minimální dimenze $k$ afinního podprostoru, aby aproximační chyba \eqref{eq:obj} byla nulová?
   Výstup úkolu (do zprávy): číslo a teoretické odůvodnění.