压缩感知理论综述
需积分: 50 24 浏览量
2013-09-10
20:07:18
上传
评论
收藏 418KB PDF 举报
IEEE SIGNAL PROCESSING MAGAZINE [118] JULY 2007
[
lecture NOTES
]
1053-5888/07/$25.00©2007IEEE
Richard G. Baraniuk
Compressive Sensing
IEEE SIGNAL PROCESSING MAGAZINE [118] JULY 2007
T
he Shannon/Nyquist sam-
pling theorem specifies that
to avoid losing information
when capturing a signal, one
must sample at least two
times faster than the signal bandwidth. In
many applications, including digital
image and video cameras, the Nyquist rate
is so high that too many samples result,
making compression a necessity prior to
storage or transmission. In other applica-
tions, including imaging systems (medical
scanners and radars) and high-speed ana-
log-to-digital converters, increasing the
sampling rate is very expensive.
This lecture note presents a new
method to capture and represent com-
pressible signals at a rate significantly
below the Nyquist rate. This method,
called compressive sensing, employs
nonadaptive linear projections that pre-
serve the structure of the signal; the sig-
nal is then reconstructed from these
projections using an optimization
process [1], [2].
RELEVANCE
The ideas presented here can be used to
illustrate the links between data acquisi-
tion, compression, dimensionality reduc-
tion, and optimization in undergraduate
and graduate digital signal processing,
statistics, and applied mathematics
courses.
PREREQUISITES
The prerequisites for understanding this
lecture note material are linear algebra,
basic optimization, and basic probability.
PROBLEM STATEMENT
COMPRESSIBLE SIGNALS
Consider a real-valued, finite-length,
one-dimensional, discrete-time signal
x
,
which can be viewed as an
N × 1
column
vector in
R
N
with elements
x[n]
,
n = 1, 2,...,N
. (We treat an image or
higher-dimensional data by vectorizing it
into a long one-dimensional vector.) Any
signal in
R
N
can be represented in terms
of a basis of
N × 1
vectors
{ψ
i
}
N
i=1
. For
simplicity, assume that the basis is
orthonormal. Using the
N × N
basis
matrix
= [ψ
1
|ψ
2
| ...|ψ
N
]
with the
vectors
{ψ
i
}
as columns, a signal
x
can
be expressed as
x =
N
i =1
s
i
ψ
i
or x = ψs (1)
where
s
is the
N × 1
column vector of
weighting coefficients
s
i
=x,ψ
i
=ψ
T
i
x
and
·
T
denotes transposition. Clearly,
x
and
s
are equivalent representations of
the signal, with
x
in the time or space
domain and
s
in the
domain.
The signal
x
is
K
-sparse if it is a linear
combination of only
K
basis vectors; that
is, only
K
of the
s
i
coefficients in (1) are
nonzero and
(N − K)
are zero. The case
of interest is when
K N
. The signal
x
is compressible if the representation (1)
has just a few large coefficients and many
small coefficients.
TRANSFORM CODING
AND ITS INEFFICIENCIES
The fact that compressible signals are
well approximated by
K
-sparse represen-
tations forms the foundation of trans-
form coding [3]. In data acquisition
systems (for example, digital cameras)
transform coding plays a central role: the
full
N
-sample signal
x
is acquired; the
complete set of transform coefficients
{s
i
}
is computed via
s =
T
x
; the
K
largest coefficients are located and the
(N − K)
smallest coefficients are dis-
carded; and the
K
values and locations of
the largest coefficients are encoded.
Unfortunately, this sample-then-com-
press framework suffers from three
inherent inefficiencies. First, the initial
number of samples
N
may be large even
if the desired
K
is small. Second, the set
of all
N
transform coefficients
{s
i
}
must
be computed even though all but
K
of
them will be discarded. Third, the loca-
tions of the large coefficients must be
encoded, thus introducing an overhead.
THE COMPRESSIVE
SENSING PROBLEM
Compressive sensing address these ineffi-
ciencies by directly acquiring a com-
pressed signal representation without
going through the intermediate stage of
acquiring
N
samples [1], [2]. Consider a
general linear measurement process that
computes
M < N
inner products
between
x
and a collection of vectors
{φ
j
}
M
j=1
as in
y
j
=x,φ
j
. Arrange the
measurements
y
j
in an
M × 1
vector
y
and the measurement vectors
φ
T
j
as rows
in an
M × N
matrix
. Then, by substi-
tuting
from (1),
y
can be written as
y = x = s = s (2)
where
=
is an
M × N
matrix. The
measurement process is not adaptive,
meaning that
is fixed and does not
depend on the signal
x
. The problem
consists of designing a) a stable meas-
urement matrix
such that the salient
information in any
K
-sparse or com-
pressible signal is not damaged by the
dimensionality reduction from
x ∈
R
N
to
y ∈
R
M
and b) a reconstruction algo-
rithm to recover
x
from only
M ≈ K
measurements
y
(or about as many
measurements as the number of coeffi-
cients recorded by a traditional trans-
form coder).
评论0