SparseCoding.tex

\section*{Sparse Coding}
\subsection*{Orthogonal Basis}
Transform: For $\mathbf{x}$ and orthog. mat. $\mathbf{U}$ compute $\mathbf{z} = \mathbf{U}^\top \mathbf{x} $. For compression, can drop small values: $ \mathbf{\hat{x}} = \mathbf{U\hat{z}}$, $\hat{z}_i = z_i$ if $ \lvert z_i \rvert > \epsilon$ else 0.
Pros: fast inverse; preserves energy. 
or $\mathbf{x}$ and orthog. mat. $\mathbf{U}$ compute $\mathbf{z} = \mathbf{U}^\top \mathbf{x} $ else 0.
Reconstr. Error $\|\mathbf{x}-\mathbf{\hat{x}}\|^2 = \sum_{d\notin\sigma}\langle\mathbf{x},\mathbf{u}_d\rangle ^2$ for a subset of basis $\sigma$.\\
\textbf{Haar Wavelets:} scaling function $\phi(x)=[1,1,1,1]$, mother $W(x)=[1,1,-1,-1]$, dilated $W(2x)=[1,-1,0,0]$, translated $W(2x-1)=[0,0,1,-1]$. Do not forget to normalize.\\
\textbf{Comparison to Fourier basis:} local (not global) support, good for localized (not $\sin$ like, repeating) signals.
\textbf{PCA basis:} data-dependent, but optimal for given $\Sigma$. $\mathbf{\hat x} = \mathbf{U}_K \mathbf{z}_{[1:K]} $
\subsection*{Overcomplete Dictionaries}
Use more atoms than dimensions, then choose the best representation. (e.g.Gabor wavelets use Fourier like features in a localized Gaussian window). \\ Linear dependency measure:  \textbf{Coherence}\\
\begin{inparaitem}[\color{gray}\textbullet]
	\item $m(\mathbf{U}) = \max_{i,j:\, i \neq j} | \mathbf{u}_i^\top \mathbf{u}_j |$
	\item $m(\mathbf{B}) = 0$ if $\mathbf{B}$ orth. mat.
	\item $m([\mathbf{B}, \mathbf{u}]) \geq \frac{1}{\sqrt{D}}$ if atom $\mathbf{u}$ is added to $\mathbf{B}$
\end{inparaitem}\\
\textbf{Signal Reconstruction:} orthonormal: $\mathbf{x} = \mathbf{Uz}$, spanning basis (linearly independent): $\mathbf{x} = (\mathbf{U}^T)^{-1}\mathbf{z}$ (can be ill-conditioned), overcomplete: solve $\mathbf{z}^* \in \argmin_\mathbf{z} ||\mathbf{z}||_0$ s.t. $\mathbf{x}=\mathbf{Uz}$. (NP hard). Can convexify with $L_1$ norm or greedy approx.: \\
\textbf{Matching Pursuit (MP)}
\begin{inparaenum}[\color{gray}1.]
	\item init: $\hat z \leftarrow 0, r \leftarrow x$
	\item while $\|\mathbf{z}\|_0 < K$ do
	\item select atom with smallest angle $j^* = \argmax_j |\langle \mathbf{u}_j, \mathbf{r} \rangle|$
	\item update coefficients: $\hat z\leftarrow \hat z + \langle \mathbf{u}_{i^\star}, \mathbf{r} \rangle \mathbf{u_{j^*}}$
	\item update residual: $\mathbf{r} \leftarrow \mathbf{r} - \langle \mathbf{u}_{i^\star}, \mathbf{r} \rangle \mathbf{u}_{i^\star}$.
\end{inparaenum}
\textbf{Exact recovery} when: $K<1/2( 1+1/m(\mathbf{U}))$ \\
\textbf{Instance when MP never exactly match x}: Idea: if we always just half residual and start with a pos. number, we will never arrive at $0$. Start with (0,1). u1 = (1,0) u2 = ($\sqrt 2$/2, $\sqrt 2$/2), u3 = ($\sqrt 3$/2, 1/2). \\
\textbf{Instance where MP does not have best solution:} u1 = (1,0), u2 = (0,1), u3 = (sqrt(2)/2, sqrt(2)/2). x = (2,1), will have largest correlation with u3, but residual then cannot be expressed with only u1 or u2, so we will use all 3 vectors instead of only u1 \& u2.
\subsection*{Compressive Sensing}
Aquire set $\mathbf{y}$ of $M$ linear combinations of signal, then reconstruct from it. $y_k = \langle \mathbf{w}_k, \mathbf{x} \rangle, k=1,...,M $
$\mathbf{y}=\mathbf{Wx}=\mathbf{WUz} =: \Theta\mathbf{z}$ with $\Theta = \mathbf{WU} \in \mathbb{R}^{M\times D}$.
Any orthonormal basis $\mathbf{U}$ can obtain a stable reconstr. for any $K$-sparse compressible signal if: \begin{inparaitem}[\color{gray}\textbullet]
\item $\mathbf{W}$ is Gaussian random projection, i.e. $w_{ij}\sim \mathcal{N}(0,\frac{1}{D})$
\item $M\geq cK \log \frac{D}{K}$(some constant $c$).
\end{inparaitem}
Reconstruct as before: $\mathbf{z}^\star \in \argmin_{\mathbf{z}}\|\mathbf{z}\|_0$, s.t. $\mathbf{y} = \Theta\mathbf{z}$