Tato bakalářská práce je zaměřena na rekonstrukci řídkého vektoru z jeho komprimovaného pozorování. Pro rekonstrukci se využívá optimalizačního problému LASSO a jeho řešení pomocí proximálních algoritmů. Po vytvoření takového algoritmu, který je schopen původní signál rekonstruovat, se využívá metody Monte Carlo pro pozorování závislosti chyby řešení na parametru lambda. U takto získaného výpočtu je zjištěna kvadratická chyba řešení LASSO vzhledem k původnímu vektoru dat.
Vypracování bylo rozděleno do několika navazujících částí. Prvním a také nejdůležitějším krokem bylo nastudování vlastností proximálních algoritmů a výpočet proximálního operátora při různých vstupních funkcích. Po takto provedené rešerši proximálních algoritmů proběhla také rešerše vlastností optimalizační úlohy LASSO a jejích variant. V dalším kroku bylo možné přistoupit k implementaci algoritmu v programovacím jazyce a vývojovém prostředí MATLAB. Při postupné implementaci byl algoritmus upraven tak, aby vždy zkonvergoval ke správnému nebo alespoň co nejbližšímu přibližnému řešení optimalizačního problému. Z tohoto důvodu byl algoritmus rozšířen o podmínky optimality, jež ukončují výpočet při dosažení poměrně přesné aproximace. Dále byl algoritmus rozšířen o výpočet dynamické velikosti kroku, aby uživatel nemusel zadávat tento parametr, který velice ovlivňuje celkový chod algoritmu. S takto připraveným algoritmem mohla být použita metodika Monte Carlo k vytvoření numerické simulace, jež generuje nekomprimovaný řídký vektor dat, měřící matice s prvky, které mají Gaussovo rozložení a parametr lambda v zadaném rozsahu s logaritmickým rozdělením. Závěrečnou fází této práce bylo vytvoření metod vytvářející analytickou předpověď spolu s numerickou simulací pro rešeršní účely.
Zároveň tato práce navrhuje způsoby, jak může být pokračováno s nástroji, jež byly vytvořeny v průběhu jejího zpracování a získat tak přesnější výsledky.
Anotace v angličtině
This bachelor thesis is focused on the reconstruction of a sparse vector from its compressed observation. For the reconstruction, the LASSO problem is used and its solution using proximal algorithms. After the implementation of an algorithm that is able to restore the original signal, Monte Carlo method is used to analyze the dependence of computation error of the lambda parameter.
Realization was divided into several parts. The very first and the most important step was a study of the properties of proximal algorithms and the evaluation of proximal operator for different functions. After the study on proximal algorithms there was also survey on the properties of LASSO and its variants. After that is was possible to implement an algorithm using the MATLAB language and its development environment. The algorithm was modified during the implementation so it always converges to the correct or, at least, approximate solution of LASSO. Because of this reason optimality conditions were added that terminates the optimization process if the approximation is sufficiently accurate. Then a computation of dynamical step size was added that affects the whole algorithm so the user does not have to choose it. This algorithm could be numerically analysed using the Monte Carlo approach that generates uncompressed sparse vector of data, random measurement matrix with Gaussian distribution, and a lambda parameter within an interval with logarithmic spacing. The last step was to study methods for analytic prediction of the numerical simulation.
At the same time, this bachelor thesis suggests how it can be used to continue with prepared tools that were created during this project and how to arrive at more accurate results.
Klíčová slova
MATLAB, proximální algoritmus, proximální operátor, LASSO, Monte Carlo
Klíčová slova v angličtině
MATLAB, Proximal Algorithm, Proximal Operator, LASSO, Monte Carlo
Rozsah průvodní práce
51 s.
Jazyk
CZ
Anotace
Tato bakalářská práce je zaměřena na rekonstrukci řídkého vektoru z jeho komprimovaného pozorování. Pro rekonstrukci se využívá optimalizačního problému LASSO a jeho řešení pomocí proximálních algoritmů. Po vytvoření takového algoritmu, který je schopen původní signál rekonstruovat, se využívá metody Monte Carlo pro pozorování závislosti chyby řešení na parametru lambda. U takto získaného výpočtu je zjištěna kvadratická chyba řešení LASSO vzhledem k původnímu vektoru dat.
Vypracování bylo rozděleno do několika navazujících částí. Prvním a také nejdůležitějším krokem bylo nastudování vlastností proximálních algoritmů a výpočet proximálního operátora při různých vstupních funkcích. Po takto provedené rešerši proximálních algoritmů proběhla také rešerše vlastností optimalizační úlohy LASSO a jejích variant. V dalším kroku bylo možné přistoupit k implementaci algoritmu v programovacím jazyce a vývojovém prostředí MATLAB. Při postupné implementaci byl algoritmus upraven tak, aby vždy zkonvergoval ke správnému nebo alespoň co nejbližšímu přibližnému řešení optimalizačního problému. Z tohoto důvodu byl algoritmus rozšířen o podmínky optimality, jež ukončují výpočet při dosažení poměrně přesné aproximace. Dále byl algoritmus rozšířen o výpočet dynamické velikosti kroku, aby uživatel nemusel zadávat tento parametr, který velice ovlivňuje celkový chod algoritmu. S takto připraveným algoritmem mohla být použita metodika Monte Carlo k vytvoření numerické simulace, jež generuje nekomprimovaný řídký vektor dat, měřící matice s prvky, které mají Gaussovo rozložení a parametr lambda v zadaném rozsahu s logaritmickým rozdělením. Závěrečnou fází této práce bylo vytvoření metod vytvářející analytickou předpověď spolu s numerickou simulací pro rešeršní účely.
Zároveň tato práce navrhuje způsoby, jak může být pokračováno s nástroji, jež byly vytvořeny v průběhu jejího zpracování a získat tak přesnější výsledky.
Anotace v angličtině
This bachelor thesis is focused on the reconstruction of a sparse vector from its compressed observation. For the reconstruction, the LASSO problem is used and its solution using proximal algorithms. After the implementation of an algorithm that is able to restore the original signal, Monte Carlo method is used to analyze the dependence of computation error of the lambda parameter.
Realization was divided into several parts. The very first and the most important step was a study of the properties of proximal algorithms and the evaluation of proximal operator for different functions. After the study on proximal algorithms there was also survey on the properties of LASSO and its variants. After that is was possible to implement an algorithm using the MATLAB language and its development environment. The algorithm was modified during the implementation so it always converges to the correct or, at least, approximate solution of LASSO. Because of this reason optimality conditions were added that terminates the optimization process if the approximation is sufficiently accurate. Then a computation of dynamical step size was added that affects the whole algorithm so the user does not have to choose it. This algorithm could be numerically analysed using the Monte Carlo approach that generates uncompressed sparse vector of data, random measurement matrix with Gaussian distribution, and a lambda parameter within an interval with logarithmic spacing. The last step was to study methods for analytic prediction of the numerical simulation.
At the same time, this bachelor thesis suggests how it can be used to continue with prepared tools that were created during this project and how to arrive at more accurate results.
Klíčová slova
MATLAB, proximální algoritmus, proximální operátor, LASSO, Monte Carlo
Klíčová slova v angličtině
MATLAB, Proximal Algorithm, Proximal Operator, LASSO, Monte Carlo
Zásady pro vypracování
Nastudujte vlastnosti optimalizační úlohy LASSO a metodiku jejího řešení pomocí proximálních algoritmů.
Implementujte varianty proximálních algoritmů v Matlabu. Porovnejte jejich vlastnosti při různé volbě délky kroku.
Pomocí metody Monte Carlo simulujte rekonstrukci řídkého vektoru z jeho komprimovaného pozorování, kdy měřící matice má Gaussovo rozložení a různý počet řádků. Sledujte závislost kvadratické chyby řešení LASSO od správného řešení v závislosti na parametru lambda. Porovnejte tuto závislost s teoretickou chybou.
Zásady pro vypracování
Nastudujte vlastnosti optimalizační úlohy LASSO a metodiku jejího řešení pomocí proximálních algoritmů.
Implementujte varianty proximálních algoritmů v Matlabu. Porovnejte jejich vlastnosti při různé volbě délky kroku.
Pomocí metody Monte Carlo simulujte rekonstrukci řídkého vektoru z jeho komprimovaného pozorování, kdy měřící matice má Gaussovo rozložení a různý počet řádků. Sledujte závislost kvadratické chyby řešení LASSO od správného řešení v závislosti na parametru lambda. Porovnejte tuto závislost s teoretickou chybou.
Seznam doporučené literatury
\renewcommand{\labelenumi}{[\arabic{enumi}]}
N. Parikh and S. Boyd, ?Proximal Algorithms,? Foundations and Trends in Optimization, vol. 1, no. 3, pp. 123?231, Nov. 2013.
Babak Hassibi, Recovering Structured Signals in Noise: Comparison Lemmas and the Performance of Convex Relaxation Methods, Eusipco, 2015.
S. J. Wright, R. D. Nowak, M. A. T. Figueiredo, ?Sparse Reconstruction by Separable Approximation,? IEEE Transactions on Signal Processing, vol. 57, no. 7, pp. 2479?2493, July 2009.
Seznam doporučené literatury
\renewcommand{\labelenumi}{[\arabic{enumi}]}
N. Parikh and S. Boyd, ?Proximal Algorithms,? Foundations and Trends in Optimization, vol. 1, no. 3, pp. 123?231, Nov. 2013.
Babak Hassibi, Recovering Structured Signals in Noise: Comparison Lemmas and the Performance of Convex Relaxation Methods, Eusipco, 2015.
S. J. Wright, R. D. Nowak, M. A. T. Figueiredo, ?Sparse Reconstruction by Separable Approximation,? IEEE Transactions on Signal Processing, vol. 57, no. 7, pp. 2479?2493, July 2009.
Přílohy volně vložené
1 CD
Přílohy vázané v práci
grafy, schémata
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Průběh obhajoby je zveřejněn pouze přihlášenému uživateli.