Open Problems On Sparse Representations In Unions Of Orthogonal Bases

In this thesis,we study sparse representation of signals from redundant dictionaries which are union of several orthonormal bases.The spark introduced by Donoho and Elad plays an important role in sparse representations.However,numerical computations of sparks are generally combinatorial and thus hard.For dictionaries,unions of several orthonormal bases,two lower bounds on the spark via the mutual coherence were established in previous work.We constructively prove that both of them are tight.Our main results give positive answers to Gribonval and Nielsen’s open problem on sparse representations in unions of orthonormal bases.Orthogonal matching pursuit(OMP)and basis pursuit(BP)are two commonly used methods for solving the sparse representation of signals.For dictionaries,unions of several orthonormal bases,Gribonval and Nielsen have provided a sufficient mutual coherence condition for BP to recover every sparse vector in noiseless case.Then Tropp extended this condition from BP to OMP.We establish here the sharpness of Gribonval and Nielsen’s sufficient condition for both OMP and BP by constructing several families of counterexamples.Our main tools are Hadamard matrices and mutually unbiased bases from quantum information theory.