Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{float}
\algnewcommand\algorithmicforeach{\textbf{for each}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}
\makeatletter
\renewcommand{\ALG@beginalgorithmic}{\small}
\makeatother
\title{bolsonaro}
\date{September 2019}
\begin{document}
\maketitle
\section{Notation}
$S = \{(x_i, y_i)\}^n_{i=1}$ the dataset, with $x_i \in X$ and $y_i \in Y$. $T = \{t_1, t_2, \dots, t_d\}$ the random forest of $d$ trees, such that $t_j : X \rightarrow Y$.
\section{Orthogonal Matching Pursuit (OMP)}
$y \in \mathbb{R}^n$ a signal. $D \in \mathbb{R}^{n \times d}$ a dictionnary with $d_j \in \mathbb{R^n}$. Goal: find $w \in \mathbb{R}^d$, such that $y = Dw$ and $||w||_0 < k$. $\text{span}(\{v_1, \dots, v_n\}) \{u : u = \sum^n_{i=1} \alpha_i v_i \ | \ \alpha_i \in \mathbb{R}\}$.
\begin{algorithm}[htb]
\caption{Orthogonal Matching Pursuit}
\begin{algorithmic}[1]
\State $w_0 \gets 0$
\State $r \gets y$
\State $\lambda \gets \emptyset$
\ForEach {$k \in \{0, \dots, K\}$}
\State $d^* \gets \underset{d \in \{d_1, \dots, d_d\}}{\text{argmax}} \ |<d, r_k>|$
\State $\lambda \gets \lambda \cup \{d^*\}$
\State $w_{k+1} \gets \underset{\substack{\alpha \text{ s.c. } \\ D\alpha \ \in \ \text{span}(d) \\ \alpha \ \in \ \mathbb{R}^d}}{\text{argmin}} \ ||y - D\alpha||^2_2$
\State $r_{k + 1} \rightarrow y - D_{w_{k+1}}$
\EndFor
\end{algorithmic}
\end{algorithm}
\end{document}