Hello, and welcome to Paper of the Day (Po’D): Fast Orthogonal Sparse Approximation Algorithms over Local Dictionaries Edition. In the forthcoming weeks, I am preparing for the first part of my scientific mission at INRIA in Rennes, France (details to come). Today’s paper is co-authored by members of INRIA and IRISA in Rennes: B. Mailhé, R. Gribonval, P. Vandergheynst and F. Bimbot, “Fast Orthogonal Sparse Approximation Algorithms over Local Dictionaries,” Signal Processing, http://dx.doi.org/10.1016/j.sigpro.2011.01.004 (this paper appears in a forthcoming special issue of Signal Processing on “Advances in Multirate Filter Bank Structures and Multiscale Representations.”)
In the realm of the sparse approximation of audio signals, the pure greedy algorithm (PGA), a.k.a. the matching pursuit (MP), reigns alone because it is the only computationally feasible way to work with enormous (near) time-invariant time-frequency dictionaries. I am talking really large dictionaries; like 15 billion atoms large. (We could do iterative hard thresholding, as long as we avoid calculating the Gramian of the dictionary — which may not be too bad because it will be very sparse. I wonder how different the two approximations would be …) And of the tools useful for traveling in the realm of the sparse approximation of audio signals, Matching Pursuit Toolkit reigns supreme. Gribonval et al. have really done an excellent job at making MPTK “LeSoaSAS”, or the “least slow of all sparse approximation software”. They do this by sensibly structuring the dictionary into blocks, working in the frequency domain, implementing an efficient atom selection strategy, and removing as much redundant calculation as possible. Note that MPTK does not use the oft-quoted but impractical-to-implement trick of Mallat et al.
The PGA has a major problem though. It behaves like a self-centered relative at a buffet forgetful of what he has already put on his plate. He will return to the chicken and potatoes after he has already taken chicken and potatoes. And before you know it, he is asking for more chicken and potatoes than are actually at the buffet, and he is far from converging onto being satisfied with his meal. The uncle makes no attempt to orthogonalize his remaining appetite to what he has already eaten, which can embarrass the entire family. That is wherein comes the orthogonal greedy algorithm (OGA), a.k.a. the orthogonal matching pursuit (OMP). The OGA is the “better half” accompanying PGA. After placing each item on her plate, she considers how much of her appetite is satisfied by the selected items, and then looks at all the remaining items and chooses from among those. Her portions are more sensible and healthy than those of PGA, but geeze she takes a long time to make up her mind. This holds up the line, and embarrasses the entire family.
The authors of this paper propose and analyze a local approximation of OGA, which they call LoCOMP, in order to bring it into the realm of PGA-equivalent computability. (They also propose a local version of Gradient Pursuit, LoCGP.) The OGA is computationally expensive because it involves an orthogonal projection after each atom selection. LoCOMP takes advantage of the same tricks of MPTK, and approaches the orthogonal projection in a simplistic fashion. I have already reviewed two papers discussing LoCOMP here. And I have performed some experiments on simple signals here and here and here. I am satisfied from these experiments that LoCOMP can produce results quite comparable to those produced by OGA with a computational complexity on the order of PGA.
Sadly, the authors find that LoCOMP takes more computation than expected within MPTK. However, their experiments with LoCGP show an improvement in speed and residual energy decay w.r.t. MP. Still, they say, one must wait a day for what takes MP 10 minutes. I will be taking a closer look tomorrow at their theoretical analyses and interesting appendices.