A study on conditions for sparse solution recovery in compressive sensing

[摘要] It is well-known by now that tinder suitable conditions ℓ1 minimization can recover sparse solutions to under-determined linear systems of equations. More precisely, by solving the convex optimization problem min{∥ x∥1 : Ax = b}, where A is an m x n measurement matrix with m < n, one can obtain the sparsest solution x* to Ax = b provided that the measurement matrix A has certain properties and the sparsity level k of x* is sufficiently small. This fact has led to active research in the area of compressive sensing and other applications. The central question for this problem is the following. Given a type of measurements, a signal;;s length n and sparsity level k, what is the minimum measurement size m that ensures recovery? Or equivalently, given a type of measurements, a signal length n and a measurement size m, what is the maximum recoverable sparsity level k? The above fundamental question has been answered, with varying degrees of precision, by a number of researchers for a number of different random or semi-random measurement matrices. However, all the existing results still involve unknown constants of some kind and thus are unable to provide precise answers to specific situations. For example, let A be an m x n partial DCT matrix with n = 107 and m = 5 x 105 (n/m = 20). Can we provide a reasonably good estimate on the maximum recoverable sparsity k? In this research we attempt to provide a more precise answer to the central question raised above. By studying new sufficient conditions for exact recovery of sparse solutions, we propose a new technique to estimate recoverable sparsity for different kinds of deterministic, random and semi-random matrices. We will present empirical evidence to show the practical success of our approach, though further research is still needed to formally establish its effectiveness.

[发布机构] Rice University