Probabilistic Analysis for Basis Selection via lp Diversity Measures

Finding sparse representations of signals is an important problem in many application domains. Unfortunately, when the signal dictionary is overcomplete, finding the sparsest representation is NPhard without some prior knowledge of the solution. However, suppose that we have access to such information. Is it possible to demonstrate any performance bounds in this restricted setting? Herein, we will examine this question with respect to algorithms that minimize general `p-norm-like diversity measures. Using randomized dictionaries, we will analyze performance probabilistically under two conditions. First, when 0 ≤ p < 1, we will quantify (almost surely) the number and quality of every local minimum. Next, for the p = 1 case we will extend the deterministic results of Donoho and Elad (2003) by deriving explicit confidence intervals for a theoretical equivalence bound, under which the minimum `1-norm solution is guaranteed to equal the maximally sparse solution. These results elucidate our previous empirical studies applying `p measures to basis selection tasks.