New Bounds for RIC in Compressed Sensing
- PDF / 482,192 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 225 Views
New Bounds for RIC in Compressed Sensing Shenglong Zhou · Lingchen Kong · Naihua Xiu
Received: 29 November 2012 / Revised: 23 March 2013 / Accepted: 28 March 2013 / Published online: 25 April 2013 © The Author(s) 2013. This article is published with open access at Springerlink.com
Abstract This paper gives new bounds for restricted isometry constant (RIC) in compressed sensing. Let Φ be an m × n real matrix and k be a positive integer with k n. The main results of this paper show that if the restricted isometry constant of Φ satisfies δ8ak < 1 and 3 1 + (4a + 3)2 − 8 δk+ak < − 2 8a for a > 38 , then k-sparse solution can be recovered exactly via l1 minimization in the noiseless case. In particular, when a = 1, 1.5, 2 and 3, we have δ2k < 0.5746 and δ8k < 1, or δ2.5k < 0.7046 and δ12k < 1, or δ3k < 0.7731 and δ16k < 1 or δ4k < 0.8445 and δ24k < 1. Keywords Compressed sensing · Restricted isometry constant · Bound · l1 minimization · Exact recovery 1 Introduction The concept of compressed sensing (CS) was first introduced by Donoho [12], Candès, Romberg and Tao [8] and Candès and Tao [9] with the involved essential idea– This work was partially supported by the National Basic Research Program of China (No. 2010CB732501), the National Natural Science Foundation of China (No. 11171018), and the Fundamental Research Funds for the Central Universities (No. 2013JBM095). S. Zhou () · L. Kong · N. Xiu Department of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, P.R. China e-mail: [email protected] L. Kong e-mail: [email protected] N. Xiu e-mail: [email protected]
228
S. Zhou et al.
recovering some original n-dimensional but sparse signal\image from linear measurement with dimension far fewer than n. Recently, large numbers of researchers, including applied mathematicians, computer scientists and engineers, have begun to pay their attention to this area owing to its wide applications in signal processing, communications, astronomy, biology, medicine, seismology and so on, see, e.g., survey papers [1, 2, 19] and a monograph [14]. The fundamental problem in compressed sensing is reconstructing a highdimensional sparse signal from remarkably small number of measurements. We assume to recover a sparse solution x ∈ Rn of the underdetermined system of the form Φx = y, where y ∈ Rm is the available measurement and Φ ∈ Rm×n is a known measurement matrix (with m n). The mathematical model would be to minimize the number of the non-zero components of x, i.e., to solve the following l0 -norm optimization problem: min x0 ,
s.t.
Φx = y,
(1)
where x0 is l0 -norm of the vector x ∈ Rn , i.e., the number of nonzero entries in x (this is not a true norm, as · 0 is not positive homogeneous). A vector x with at most k nonzero entries, x0 k, is called k-sparse. However, (1) is combinatorial and computationally intractable and one popular and powerful approach is to solve it via 1 minimization (its convex relaxation) min x1 ,
s.t. Φx = y.
(2)
One of the most commonly used frameworks for sparse
Data Loading...
