Average performance of the sparsest approximation using a general dictionary

Details Average performance of the sparsest approximation using a general dictionary Average performance of the sparsest approximation using a general dictionary

2008-03-04

arxiv.org/abs/0803.0524v1

Numerical Functional Analysis and Optimization 32, 7 (2011) 768-805

Mathematics

Optimization and Control

Scientific paper

We consider the minimization of the number of non-zero coefficients (the $\ell_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 (nonconvex) optimization problem naturally leads to the sparsest representations, compared with other functionals instead of the $\ell_0$ "norm". Our goal is to measure the sets of data yielding a $K$-sparse solution--i.e. involving $K$ non-zero components. Data are assumed uniformly distributed on a domain defined by any norm--to be chosen by the user. A precise description of these sets of data is given and relevant bounds on the Lebesgue measure of these sets are derived. They naturally lead to bound the probability of getting a $K$-sparse solution. We also express the expectation of the number of non-zero components. We further specify these results in the case of the Euclidean norm, the dictionary being arbitrary.

Affiliated with

Also associated with

No associations

Rating

Average performance of the sparsest approximation using a general dictionary does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Average performance of the sparsest approximation using a general dictionary, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Average performance of the sparsest approximation using a general dictionary will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-406875