Average

performance of the sparsest approximation in a dictionary François Malgouyres⋆ and Mila Nikolova• Abstract—Given data d ∈ RN, we consider its represen-tation u ∗ involving the least number of non-zero elements (denoted by ℓ0(u∗)) using a dictionary A (represented by a matrix) under the constraint ‖Au − d ‖ ≤ τ, for τ> 0 and a norm ‖.‖. This (nonconvex) optimization problem leads to the sparsest approximation of d. We assume that data d are uniformly distributed in θBfd (1) where θ>0 and Bfd (1) is the unit ball for a norm fd. Our main result is to estimate the probability that the data d give rise to a K−sparse solution u∗: we prove that P (ℓ0(u ∗) ≤ K) = CK