Average Performance of the Sparsest Approximation Using a General Dictionary

作者：Malgouyres Francois; Nikolova Mila^*

来源：Numerical Functional Analysis and Optimization, 2011, 32(7): 768-805.

DOI：10.1080/01630563.2011.580876

• Approximation
• Best K-term approximation
• Compression
• Constrained minimization
• Dictionary
• Estimation
• Frames
• 0 norm
• Measure theory
• Nonconvex nonsmooth functions
• Sparse representations

Let A be a matrix of size NxM (a dictionary) and let center dot be a norm on N. For any data d N, we consider the sparsest vector (i.e., the one with the smallest number of nonzero entries) u M such that Au-d , for a parameter 0. We say that u is a K-sparse solution if it has less than K nonzero entries. In this article, we give a precise geometrical description of the data sets d N yielding a K-sparse solution. We parameterize and measure these sets. More precisely, we measure their intersection with a ball defined by any given norm and a radius . These measures are expressed in terms of the constituents of the optimization problemnamely A, center dot, , and and they enable these constituents to be rated. This is the core of a new methodology, called Average Performance in Approximation (APA), inaugurated in this work. By way of application, we give the probability of obtaining a K-sparse solution, when d is uniformly distributed in the -ball of radius . Analyzing the obtained formulas reveals what are the most important features of the dictionary and the norm defining the data fidelity, to obtain sparse solutions. This crucial question is largely discussed. We also provide an example when both center dot and are the Euclidian norm. Some among the wide-ranging perspectives raised by the new APA methodology are described as well.

• 出版日期2011