Theorem 10 of On polar polytopes and the recovery of sparse representations

In an attempt to figure out why orthogonal matching pursuit (OMP) performs better than the guarantees that have been found, I am working my way through this illuminating paper: M. D. Plumbley, “On polar polytopes and the recovery of sparse representations”, IEEE Trans. Info. Theory, vol. 53, no. 9, pp. 3188-3195, Sep. 2007.
In particular, I was struck by Theorem 10. But first, some background.

Recall Tropp’s exact recovery condition (ERC) here or here, or alternatively here.
Suppose we have some matrix \(\MD\) with unit norm columns (for notational convenience), and measurements \(\vx\), and we know \(\vx\) is a linear combination of \(s > 0\) columns of \(\MD\), specifically the ones indexed by \(\Phi\).
In other words, \(\vx\) has an \(s\)-term representation.
Orthogonal matching pursuit (or basis pursuit) is guaranteed to find these \(s\) columns composing \(\vx\) if
$$
\max_{i \in \Psi} ||\MD_\Phi^\dagger \vd_i ||_1 < 1
$$
where \(\MD_\Phi\) is a matrix of the \(s\) columns of \(\MD\) indexed by \(\Phi\),
and \(\Psi\) indexes the columns of \(\MD\) that are not participating in \(\vx\),
(\(\vd_i\) is the \(i\)th column of \(\MD\)).
Note that this means OMP (or BP) can recover any \(s\)-term representation from \(\vx\) only when the above is true for every \(s\)-size subset of columns from \(\MD\).
When this is true, OMP (or BP) is a "correct algorithm" for \(s\)-term representations in \(\MD\).

Now Theorem 10 in this paper states that the fact a dictionary satisfies ERC for all \(s\)-term representations is not sufficient to guarantee it satisfies ERC for all representations involving \(k 1
$$
and thus the ERC fails. However, with OMP (or BP), or good eyeballing,
we can always recover a \(\vs\) if \(\vx\) is composed of one column of this \(\MD\).
The take-home point of this example is: just because the ERC is satisfied for all measurements involving \(s\) columns of \(\MD\) doesn’t mean it is also satisfied for all measurements involving fewer columns.

That is a strange result, and one deserving to be inspected.

Advertisements

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 )

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