171
reads

Mila Nikolova

2008-04-11
10:30:00 - 11:20:00

Average performance of the sparsest approximation using a dictionary

405 , Mathematics Research Center Building (ori. New Math. Bldg.)

We consider the minimization of the number of non-zero coefficients (the ℓ0 norm) of the representation of a data set in terms of a dictionary under a fidelity constraint. (Both the dictionary and the norm defining the constraint are arbitrary.) This (non-convex) optimization problem naturally leads to the sparsest representations, compared with other objectives. Our goal is to measure the sets of data yielding a K-sparse or sparser solution - i.e. involving at most K non-zero components. Data are assumed uniformly distributed on a domain defined by a norm. Relevant bounds on the Lebesgue measure of these sets are derived. They naturally lead to bound the probability of getting a K-sparse (or sparser) solution. We specify these results in the case of the Euclidian norm and an arbitrary dictionary. Then we specialize the problem to orthogonal bases (e.g. splines or wavelets) and focus on popular choices for the two norms. We get sharper bounds that are easy to compute. These results have a considerable theoretical and practical importance.