Compressive Sensing

Report
An Introduction to
Compressive Sensing
Speaker: Ying-Jou Chen
Advisor: Jian-Jiun Ding
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.
More about low coherence…
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
(Gradient projection for sparse reconstruction)
– 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.
https://sites.google.com/site/igorcarron2/cs#sparse
http://videolectures.net/mlss09us_candes_ocsssrl1m/
Thanks a lot!
Key Points
1. Nyquist’s Rate
2. CS and Transform coding…
3. Sampling in time V.S. Sampling as inner
products
4. About compressibility
5. About designing sampling matrix
6. About L1 norm explanation by geometry!
7. Application( MRI, One-pixel camera…)

similar documents