Optimization Online


On RIC bounds of Compressed Sensing Matrices for Approximating Sparse Solutions Using Lq Quasi Norms

Hsia Yong(dearyxia***at***gmail.com)
Sheu Ruey-Lin(rsheu***at***mail.ncku.edu.tw)

Abstract: This paper follows the recent discussion on the sparse solution recovery with quasi-norms Lq; q\in(0,1) when the sensing matrix possesses a Restricted Isometry Constant \delta_{2k} (RIC). Our key tool is an improvement on a version of ``the converse of a generalized Cauchy-Schwarz inequality" extended to the setting of quasi-norm. We show that, if \delta_{2k}\le 1/2, any minimizer of the Lq minimization, at least for those q\in (0, 0.9181], is the sparse solution of the corresponding underdetermined linear system. Moreover, if \delta_{2k}\le 0.4931, the sparse solution can be recovered by any lq; q \in(0,1) minimization. The values 0.9181 and 0.4931 improves those reported previously in the literature.

Keywords: compressed sensing, restricted isometry constant, lq minimization, quasi norm

Category 1: Applications -- Science and Engineering (Basic Sciences Applications )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Global Optimization (Theory )

Citation: unpublished

Download: [PDF]

Entry Submitted: 09/19/2012
Entry Accepted: 09/19/2012
Entry Last Modified: 09/19/2012

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 Optimization Society