000087166 001__ 87166
000087166 005__ 20190316233749.0
000087166 037__ $$aREP_WORK
000087166 245__ $$aTree-Based Pursuit: Algorithm and Properties
000087166 269__ $$a2005
000087166 260__ $$c2005$$aEcublens
000087166 336__ $$aReports
000087166 500__ $$aITS
000087166 520__ $$aThis paper proposes a tree-based pursuit algorithm that efficiently trades off complexity and approximation performance for overcomplete signal expansions. Finding the sparsest representation of a signal using a redundant dictionary is, in general, a NP-Hard problem. Even sub-optimal algorithms such as Matching Pursuit remain highly complex. We propose a structuring strategy that can be applied to any redundant set of functions, and which basically groups similar atoms together. A measure of similarity based on coherence allows for representing a highly redundant sub-dictionary of atoms by a unique element, called molecule. When the clustering is applied recursively on atoms and then on molecules, it naturally leads to the creation of a tree structure. We then present a new pursuit algorithm that uses the structure created by clustering as a decision tree. This tree-based algorithm offers important complexity reduction with respect to Matching Pursuit, as it prunes important parts of the dictionary when traversing the tree. Recent results on incoherent dictionaries are extended to molecules, while the true highly redundant nature of the dictionary stays hidden by the tree structure. We then derive recovery conditions on the structured dictionary, under which tree-based pursuit is guaranteed to converge. Experimental results finally show that the gain in complexity offered by tree-based pursuit does in general not have a high penalty on the approximation performance. They show that the dimensionality of the problem is reduced thanks to the tree construction, without significant loss of information at hand.
000087166 6531_ $$aLTS2
000087166 6531_ $$aLTS4
000087166 700__ $$0241006$$g114569$$aJost, P.
000087166 700__ $$0240428$$g120906$$aVandergheynst, P.
000087166 700__ $$aFrossard, P.$$g101475$$0241061
000087166 8564_ $$uhttps://infoscience.epfl.ch/record/87166/files/Jost2005_1280.pdf$$zn/a$$s555191
000087166 909C0 $$xU10380$$0252392$$pLTS2
000087166 909C0 $$pLTS4$$xU10851$$0252393
000087166 909CO $$qGLOBAL_SET$$pSTI$$preport$$ooai:infoscience.tind.io:87166
000087166 937__ $$aEPFL-REPORT-87166
000087166 970__ $$aJost2005_1280/LTS
000087166 973__ $$sPUBLISHED$$aEPFL
000087166 980__ $$aREPORT