Optimization Online


On Theory of Compressive Sensing via L1-Minimization:

Yin Zhang (yzhang***at***rice.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society