Compressive Sensing

An Introduction to
Compressive Sensing
Speaker: Ying-Jou Chen
Outline
•
•
•
•
•
•
•
Conventional Sampling & Compression
Compressive Sensing
Why it is useful?
Framework
When and how to use
Recovery
Simple demo
Review…
Sampling and Compression
Nyquist’s Rate
• Perfect recovery
•  ≥ 2
Transform Coding
• Assume: signal is sparse in some domain…
• e.g. JPEG, JPEG2000, MPEG…
1. Sample with frequency  .
Get signal of length N
2. Transform signal  K (<< N) nonzero
coefficients
3. Preserve K coefficients and their locations
Compressive Sensing
Compressive Sensing
• Sample with rate lower than  !!
• Can be recovered PERFECTLY!
Comparison
Nyquist’s Sampling
Compressive Sensing
Sampling
Frequency
≥ 2
< 2
Recovery
Low pass filter
Convex Optimization
Some Applications
• ECG
• One-pixel Camera
• Medical Imaging: MRI
Framework
=

M
N
=
M
Φ
N: length for signal sampled with Nyquist’s rate
M: length for signal with lower rate
Φ: Sampling matrix

N
When? How?
Two things you must know…
When….
• Signal is compressible, sparse…

M
N
=
M
Φ

N
Ψ
Example… ECG
: 心電圖訊號
Ψ: DCT (discrete cosine transform)
How…
• How to design the sampling matrix?
• How to decide the sampling rate (M)?

N
=M
Φ
Ψ
Sampling Matrix
• Low coherence
Low coherence

=

Φ
Ψ
Coherence
• Describe similarity
,  =  ∙
,
– High coherence  more similar
Low coherence  more different
–  ,  ∈ [1, ]

Example: Time and Frequency
• For example,   and
1
•  = ( − ), ℎ =
2 /

1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
0
10
20
30
40
50
60
70
80
90
100
0
10
20
30
40
50
60
70
80
90
100
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Fortunately…
• Random Sampling
– iid Gaussian N(0,1)
– Random ±1
• Low coherence with deterministic basis.
Random Sampling
Sampling Rate
Theorem

≥  ∙  ,  ∙  ∙
C : constant
μ: coherence
S: sparsity
n: signal length
• Can be exactly recovered with high
probability.
Recovery
y = Φf
f = Φ−1 y

M
x
s. t. y = ΦΨx
N
=M
Φ
BUT….

N
Ψ
N
ℓ1 Recovery
• Many related research…
– GPSR
– L1-magic
– SparseLab
– BOA
(Bound optimization approach)
…..
Total Procedure
Sampling (Assume f is spare somewhere)
f
Find an incoherent matrix Φ
e.g. random matrix
Sample signal y = Φf

Recovering

. .  =
=
Demo Time
Reference
•
•
•
•
•
Candes, E. J. and M. B. Wakin (2008). "An Introduction To Compressive Sampling."
Signal Processing Magazine, IEEE 25(2): 21-30.
Baraniuk, R. (2008). Compressive sensing. Information Sciences and Systems, 2008.
CISS 2008. 42nd Annual Conference on.
Richard Baraniuk, Mark Davenport, Marco Duarte, Chinmay Hegde. An
Introduction to Compressive Sensing.