Poster of the Day (Po’D): Signal Synthesis with Conic Matching Pursuit Edition

Hello, and welcome to Poster of the Day (Po’D): Signal Synthesis with Conic Matching Pursuit Edition.
With this poster, we add yet another greedy sparse approximation method with the acronym CMP: First, there was Cyclic MP; then there was Complementary MP. Then there was Consensus MP. And now we have Conic MP:
J. Carmichael, “Signal Synthesis with Conic Matching Pursuit,” presented somewhere and sometime, perhaps at the Alumni Reunion and Celebration of Applied Mathematics of at the University of Washington?

I don’t know precisely all that is going on in this poster, but I think it could be of interest to designing dictionaries for audio signal decomposition. I have never thought of cones before, so this is a good learning experience.
A cone in \(\mathcal{R}^K\) is defined as a set of unit norm vectors having projections that are positive enough onto some unit norm vector \(\vw \in \mathcal{R}^K\)
$$\mathcal{C}(\vw, \rho) := \{ \vx \in \mathcal{R}^K : \langle \vx, \vw \rangle \ge \rho, || \vx || = 1 \}$$
where \(\rho > 0\).
Every linear combination of vectors in \(\mathcal{C}(\vw, \rho)\) also belongs to \(\mathcal{C}(\vw, \rho)\), and so it is convex and closed (its complement is open, I think).
The larger we define \(\rho\), the more tight our cone becomes around \(\vw\).
(What about in a complex space? Maybe then we talk about \(\mathcal{R}^{2K}\).)
We define the projection of some \(\vx\) onto a cone \(\mathcal{C}(\vw, \rho)\) by finding the closest vector in the cone and then projecting
$$ \MP_{\mathcal{C}}\vx := \vy \langle \vx, \vy \rangle$$
where $$ \vy := \arg \min_{\vy’ \in \mathcal{C}(\vw, \rho)} || \vx – \vy’ ||.$$
Now, given a set of \(N\) non-overlapping convex cones, each defined by a \(\rho_n\),
$$D_N = \{\mathcal{C}_n(\vw_n,\rho_n) : \langle \vw_n, \vx \rangle > \langle \vw_l, \vx \rangle \; \forall \vx \in \mathcal{C}_n(\vw_n,\rho_n), n \ne l, n, l = 1, \ldots, N\}$$
and given that \(\textrm{span} \{ D_N \} = \textrm{span} \{ \{\vw_n\}_N \} = \mathcal{R}^K\),
we can always express any \(\vx \in \mathcal{R}^K\) as a linear combination of vectors from these cones.
And this inspires using matching pursuit (MP) with a dictionary of cones,
where in the limit that each \(\rho_n \to 1\), is just MP with the dictionary \(\{\vw_n\}_N\).

So the procedure is the following.
Given an \(n\)th order representation of some \(\vx \in \mathcal{R}^K\),
expressed \(\mathcal{X}_n = \bigl \{ \MH(n), \va(n), \vr(n) \bigr \}\),
and a dictionary of cones, we update this representation by
\mathcal{X}_{n+1} = \left \{
\MH(n+1) = & [ \MH(n) | \vh_{n} ], \\
\va(n+1) = & [\va^T(n), \langle \vr(n), \vh_n \rangle ]^T, \\
\vr(n+1) = & \vx – \MH(n+1)\va(n+1)
\right \}$$
where we select the vector from one cone such that
$$\vh_n := \arg \min_{\vh \in \mathcal{C}_n(\vw_i,\rho_i) \in D_N}
|| \vr(n) – \MP_{\mathcal{C}}\vr(n) ||.$$
As this iterative procedure is just MP it is no surprise that it has all the properties of MP, e.g., “energy conservation,” monotonic decreasing residual energy, convergence to the orthogonal projection, etc.
The only difference between this CMP and standard MP is that here we are first finding the closest cone, and then the closest vector in that cone. I do not agree with the author that “cones capture more signal energy.” We are just selecting a vector in a cone, rather than the central vector of each cone. In other words, as each \(\rho_n\) becomes smaller we are embiggening the dictionary, and thus including more vectors closer to the residual.

What I think is interesting here is that the idea of cones appears an interesting way to structure a dictionary into groups of functions that are generalized to some extent, or tuned by the projection thresholds \(\{\rho_n\}_N\). The author appears to do this with seismic signals, but without a proper paper I am lost in figuring out how he constructs the cones.


Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s