Sunday, January 03, 2010

CS: Finding the Restricted isometry Constant, Part Deux.

Gabriel Peyré sent me the following:
Dear Igor,

...Regarding your last post, you might be interested in a recent paper I co-authored with Charles Dossa and Jalal Fadili

[the pdf is here]
that presents a greedy algorithm to estimate RIP constants. In practice, for matrix of size ~10000 measures, it gets quite close to the asymptotic upper bounds of Blanchard et al, that are thus quite sharp.

It is fast, and does not requires any convex optimization, but does a much better job than picking sub-dictionary at random using Monte Carlo. It can also be used to find vectors that cannot be recovered by L1 minimization, and gets very close to the asymptotic bounds of Donoho and Tanner....


I covered that paper last March and when I gave my answer in the last entry, I knew there was something newer. This is fixed. Thanks Gabriel ! As a result of this query, I will also alter the section starting the measurement matrix paragraph of the big picture.

No comments:

Printfriendly