Let
Φ(
ω),
ωΩ, be a family of
n×
N random matrices whose entries
i,j are independent realizations of a symmetric, real random variable
η with expectation
and variance
. Such matrices are used in compressed sensing to encode a vector
by
y=
Φx. The information
y holds about
x is extracted by using a decoder
. The most prominent decoder is the
ℓ1-minimization decoder
Δ which gives for a given
the element
which has minimal
ℓ1-norm among all
with
Φz=
y. This paper is interested in properties of the random family
Φ(
ω) which guarantee that the vector
will with high probability approximate
x in
to an accuracy comparable with the best
k-term error of approximation in
for the range
kan/log
2(
N/
n). This means that for the above range of
k, for each signal
, the vector
satisfies
with high probability on the draw of
Φ. Here,
Σk consists of all vectors with at most
k nonzero coordinates. The first result of this type was proved by Wojtaszczyk [P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math., in press] who showed this property when
η is a normalized Gaussian random variable. We extend this property to more general random variables, including the particular case where
η is the Bernoulli random variable which takes the values
with equal probability. The proofs of our results use geometric mapping properties of such random matrices some of which were recently obtained in [A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005) 491–523].
相似文献