Subspace Pursuit for Compressive Sensing: Closing the Gap ...

1 1 Subspace Pursuit for Compressive sensing : Closingthe Gap between Performance and Complexity Wei Dai and Olgica MilenkovicDepartment of Electrical and Computer EngineeringUniversity of Illinois at Urbana-ChampaignAbstract We propose a new method for reconstruction ofsparse signals with and without noisy perturbations, termed thesubspace Pursuit algorithm. The algorithm has two importantcharacteristics: low computational complexity, comparable tothat of orthogonal matching Pursuit techniques, and reconstruc-tion accuracy of the same order as that of LP optimizationmethods. The presented analysis shows that in the noiselesssetting, the proposed algorithm can exactly reconstruct arbitrarysparse signals provided that the sensing matrix satisfies therestricted isometry property with a constant parameter.

2 In thenoisy setting and in the case that the signal is not exactly sparse,it can be shown that the mean squared error of the reconstructionis upper bounded by constant multiples of the measurement andsignal perturbation Terms Compressive sensing , orthogonal matching pur-suit, reconstruction algorithms, restricted isometry property,sparse signal reconstructionI. INTRODUCTIONC ompressive sensing (CS) is a method closely connectedtotransform coding, a compression technique widely usedin modern communication systems involving large scale datasamples. A transform code converts input signals, embeddedin a high dimensional space, into signals that lie in a space ofsignificantly smaller dimension. Examples of transform codersinclude the well known wavelet transforms and the ubiquitousFourier sensing techniques perform transform cod-ing successfully whenever applied to so-called compressibleand/orK-sparse signals, , signals that can be represented byK Nsignificant coefficients over anN-dimensional of aK-sparse, discrete-time signalxof dimensionNis accomplished by computing a measurement vectorythat consists ofm Nlinear projections of the vectorx,compactly described viay= , represents anm Nmatrix, usually over the fieldof real numbers.

3 Within this framework, the projection basisis assumed to beincoherentwith the basis in which the signalhas a sparse representation [2].This work is supported by NSF Grants CCF 0644427, 0729216 and theDARPA Young Faculty Award. At the time of writing this manuscript, the authors became aware ofthe related work by J. Tropp, D. Needell and R. Vershynin [1], wheresimilar reconstruction algorithms are designed. Our results were developedindependently, and we believe that there are significant differences in thesetwo proposed reconstruction the reconstruction of the signalx RNfrom thepossibly noisy random projections is an ill-posed problem, thestrong prior knowledge of signal sparsity allows for recoveringxusingm Nprojections only.

4 One of the outstandingresults in CS theory is that the signalxcan be reconstructedusing optimization strategies aimed at finding the sparsestsignal that matches with themprojections. In other words,the reconstruction problem can be cast as an`0minimizationproblem [3]. It can be shown that to reconstruct aK-sparsesignalx,`0minimization requires onlym=K+ 1randomprojections when the signal and the measurements are noise-free. Unfortunately, solving the`0optimization is known tobe NP-hard. This issue has led to a large body of work in CStheory and practice centered around the design of measurementand reconstruction algorithms with tractable work by Donoho and Cand s et. al. [2], [4] [6].

5 Demonstrated that CS reconstruction is, indeed, a polynomialtime problem albeit under the constraint that more thanK+1measurements are used. The key observation behind thesefindings is that it is not necessary to resort to`0optimizationto recoverxfrom the under-determined inverse problem; amuch easier`1optimization, based on Linear Programming(LP) techniques, yields an equivalent solution, as long as thesampling matrix satisfies the so calledrestricted isometryproperty(RIP) with a constant LP techniques play an important role in designingcomputationally tractable CS decoders, their complexity isstill highly impractical for many applications. In such cases,the need for faster decoding algorithms - preferably operatingin linear time - is of critical importance, even if one hasto increase the number of measurements.

6 Several classes oflow-complexity reconstruction techniques were recently putforward as alternatives to linear programming (LP) basedrecovery, which include group testing methods [7], and al-gorithms based on belief propagation [8].Recently, a family of iterative greedy algorithms receivedsignificant attention due to their low complexity and simplegeometric interpretation. They include the Orthogonal Match-ing Pursuit (OMP), the Regularized OMP (ROMP) and theStagewise OMP (StOMP) algorithms. The basic idea behindthese methods is to find the support of the unknown signalsequentially. At each iteration of the algorithms, one or severalcoordinates of the vectorxare selected for testing basedon the correlation values between the columns of andthe regularized measurement vector.

7 If deemed sufficientlyReport Documentation PageForm ApprovedOMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering andmaintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information,including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, ArlingtonVA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if itdoes not display a currently valid OMB control number.

8 1. REPORT DATE 2008 2. REPORT TYPE 3. DATES COVERED 00-00-2008 to 00-00-2008 4. TITLE AND SUBTITLE Subspace Pursuit for Compressive sensing : Closing the Gap BetweenPerformance and Complexity 5a. CONTRACT NUMBER 5b. GRANT NUMBER 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) Department of Electrical and Computer Engineering,University of Illinoisat Urbana-Champaign,Urbana-Champaign,IL 8. PERFORMING ORGANIZATIONREPORT NUMBER 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR S ACRONYM(S) 11. SPONSOR/MONITOR S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13.

9 SUPPLEMENTARY NOTES 14. ABSTRACT We propose a new method for reconstruction of sparse signals with and without noisy perturbations,termed the Subspace Pursuit algorithm. The algorithm has two important characteristics: lowcomputational complexity, comparable to that of orthogonal matching Pursuit techniques, andreconstruction accuracy of the same order as that of LP optimization methods. The presented analysisshows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signalsprovided that the sensing matrix satisfies the restricted isometry property with a constant parameter. Inthe noisy setting and in the case that the signal is not exactly sparse it can be shown that the mean squarederror of the reconstruction is upper bounded by constant multiples of the measurement and signalperturbation energies.

10 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATIONOF ABSTRACT Same asReport (SAR) 18. NUMBEROF PAGES 18 19a. NAME OFRESPONSIBLE PERSON a. REPORT unclassified b. ABSTRACT unclassified c. THIS PAGE unclassified Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 2reliable, the candidates are subsequently added to the currentestimate of the support set ofx. The Pursuit algorithms iteratethis procedure until all the coordinates in the correct supportare in the estimated support. The computational complexity ofOMP strategies depends on the number of iterations neededfor exact reconstruction: standard OMP always runs throughKiterations, and therefore its reconstruction complexity isroughlyO(KmN).