On Theory of Compressive Sensing via L1-Minimization:

Yin Zhang (yzhangrice.edu)

Abstract: Compressive (or compressed) sensing (CS) is an emerging methodology in computational signal processing that has recently attracted intensive research activities. At present, the basic CS theory includes recoverability and stability: the former quantifies the central fact that a sparse signal of length n can be exactly recovered from much less than n measurements via L1-minimization or other recovery techniques, while the latter specifies how stable is a recovery technique in the presence of measurement errors and inexact sparsity. So far, most analyses in CS rely heavily on a matrix property called Restricted Isometry Property (RIP). In this paper, we present an alternative, non-RIP analysis for CS via L1-minimization. Our purpose is three-fold: (a) to introduce an elementary treatment of the CS theory free of RIP and easily accessible to a broad audience; (b) to extend the current recoverability and stability results so that prior knowledge can be utilized to enhance recovery via L1-minimization; and (c) to substantiate a property called uniform recoverability of L1-minimization; that is, for almost all random measurement matrices recoverability is asymptotically identical. With the aid of two classic results, the non-RIP approach enables us to derive from scratch all basic results for the extended theory with short and simple derivations.

Keywords: Compressive Sensing, L1-minimization, non-RIP analysis, recoverability and stability

Category 1: Applications -- Science and Engineering

Category 2: Convex and Nonsmooth Optimization

Citation: CAAM Technical Report TR08-11, Rice University

Download: [PDF]

Entry Submitted: 07/30/2008
Entry Accepted: 07/30/2008
Entry Last Modified: 09/08/2008

Modify/Update this entry