Orthogonal Matching Pursuit the QR Way

Continuing from the naive OMP and the Cholesky OMP, we now look at using QR decomposition to make OMP extremely efficient. I previously discussed this approach here, but below I make some additions.

Consider that in the \(k\)th step of OMP we have
\(\mathcal{I}_{0} = \{\langle \vu, \vphi_n \rangle/\|\vphi_n\| \}_{n \in \Omega}\),
\(\mathcal{I}_{k-1} = \{\langle \vr_{k-1}, \vphi_n \rangle/\|\vphi_n\| \}_{n \in \Omega}\),
the set of dictionary inner products
\(\Gamma_l = \{\langle \vphi_l, \vphi_n \rangle/\|\vphi_n\|\}_{n \in \Omega}\),
as well as the QR decomposition of the subdictionary produced thus far,
i.e., \(\MPhi_{\Omega_{k-1}} = \MQ_{k-1}\MR_{k-1}\).
The QR decomposition of a matrix will always exist,
but is not unique.

OMP searches through \(\mathcal{I}_{k-1}\)
to find a new atom index \(n_k\).
It then defines \(\vw = \MQ_{k-1}^H\vphi_{n_k}\)
and updates the QR decomposition by
\MR_k & = \left [ \begin{array}{cc}
\MR_{k-1} & \vw \\
\zerob^T & \sqrt{\|\vphi_{n_k}\|^2 – \|\vw\|^2}
\end{array} \right ] \\
\MQ_{k} & = \left [ \begin{array}{cc}
\MQ_{{k-1}} & \frac{\vphi_{n_k} – \MQ_{{k-1}}\vw}{ \sqrt{\|\vphi_{n_k}\|^2 – \|\vw\|^2}}
\end{array} \right ].
With the search, updating these matrices has complexity
\(\mathcal{O}(N + Mk)\).
OMP computes the residual energy recursively
\|\vr_k\|^2 & = \|\vu – \MQ_{{k-1}}\MQ_{{k-1}}^H \vu – \vq_k \vq_k^H\vu\|^2 \\
& = \|\vr_{k-1}\|^2 – |\langle \vu,\vq_k\rangle|^2
where \(\vq_k\) is the last column of
the orthonormal basis in \(\MQ_k\).
OMP can then update the projections
without computing the residual since
\(\vr_k = \vr_{k-1} – \vq_k \vq_k^H\vu\):
\mathcal{I}_{k} = \left \{\frac{\langle \vr_{k}, \vphi_n \rangle}{\|\vphi_n\|} \right\}_{n \in \Omega} =
\left \{\frac{\langle \vr_{k-1},\vphi_n \rangle}{\|\vphi_n\|} –
\frac{\langle\vq_k \vq_k^H\vu, \vphi_n \rangle}{\|\vphi_n\|} \right\}_{n \in \Omega} \\
= \left \{\mathcal{I}_{k-1}(n) – \langle \vu,\vq_k \rangle\frac{\langle\vq_k, \vphi_n \rangle}{\|\vphi_n\|} \right\}_{n \in \Omega}.
This has a complexity of \(\mathcal{O}(NM)\).

Once finished, OMP finds the solution at iteration \(K\) by
solving two triangular systems
\MR_K^H \vy & = \MPhi_{\Omega_K}^H \vu \\
\MR_K \vx_K & = \vy
where the right hand side of the first system comes from \(\mathcal{I}_{0}\).
Solving both of these with back-substitution
has complexity \(\mathcal{O}(K^2)\).
In this way, the total complexity of OMP in its \(k\)th iteration
is \(\mathcal{O}(NM + Mk)\),
which is linear in \(k\).
Notice that in this implementation
OMP does not compute the solution or the residual
during decomposition.

If instead, OMP updates the set of projections using
\mathcal{I}_{k} = \left \{\frac{\langle \vr_{k}, \vphi_n \rangle}{\|\vphi_n\|} \right\}_{n \in \Omega} =
\left \{\frac{\langle \vu,\vphi_n \rangle}{\|\vphi_n\|} – \frac{\langle\MPhi_{\Omega_k} \vx_k, \vphi_n \rangle}{\|\vphi_n\|} \right\}_{n \in \Omega} \\
= \left \{\mathcal{I}_{0}(n) – \sum_{l=1}^k x_{l} \frac{\langle\vphi_{n_l}, \vphi_n \rangle}{\|\vphi_n\|} \right\}_{n \in \Omega} \\
= \left \{\mathcal{I}_{0}(n) – \sum_{l=1}^k x_{l} \Gamma_{n_l}(n) \right \}_{n \in \Omega}
then it might reduce the complexity at the cost of
computing the solution at each iteration.
After computing the solution at complexity \(\mathcal{O}(k^2)\),
OMP can update the projections using the above,
and update the residual energy using
\|\vr_k\|^2 & = \|\vu – \MPhi_{\Omega_k} \vx_k\|^2 \\
& = \|\vu\|^2 + \|\MPhi_{\Omega_k} \vx_k\|^2 – 2\text{Re}\{\vx_k^H \MPhi_{\Omega_k}^H\vu\} \\
& = \|\vu\|^2 + \vx_k^H \ML_{k}\ML_{k}^H \vx_k – 2\text{Re}\{\vx_k^H \ML_{k} \vy\} \\
& = \|\vu\|^2 – \|\vy\|^2.
Thus, using this approach, the total complexity of its \(k\)th iteration is
\(\mathcal{O}((N+M)k + k^2)\).

Here is my code: ompdQR.m


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s