ANALYSIS VS.

SYNTHESIS
Numerical study on CRSI-based seismic interpolation with NESTA

Tim Lin
final project Eosc512 Term 2009W
 Why are they adversaries?

Analysis and synthesis forms are based two subtly

different signal priors for a general inverse problem:

y = T (x) + noise

where given y the goal is to find x, usually involving

some sort of inverse of T
(noise is additive pure Gaussian noise)
 Why are they adversaries?

if we use a totally uninformed (uniform prior) on x

Prob(X) = uniform(x)
xML = argmax Prob(Y |X)
x
1
= argmax exp( ||y T (x)|| )2
x 2
= argmin ||y T (x)||2
2
x

least-squares solution pops out as Maximum

Likelihood solution
 Why are they adversaries?
similarily:

Analysis prior Synthesis prior

Prob(X) = C · exp( ||Wx||pp ) Prob(X) = C · exp( ||w(x)||pp )
w = arg min ||w||pp
w x

max Prob(X|Y ) MAP assumption

X

xMAP = xMAP =
arg min ||y T (x)||22 + ||Wx||pp W† arg min ||y T (W† w)||22 + ||w||pp
x w
 Lambda form and constrained form

Analysis prior solution

arg min ||y T (x)||22 + ||Wx||pp
x

arg min ||Wx||pp s.t. ||y T (x)||22 <

x

Synthesis prior solution

W† arg min ||y T (W† w)||22 + ||w||pp
w

W† arg min ||w||pp s.t. ||y T (W† x)||22 <

w
 Geometric interpretation
max Prob(X) s.t. ||X||2 = 1
X

unit 2-norm ball

{W† w | ||w|| 1}

Synthesis prior polytope

synthesis prior polytope have vertex of columns of W† and W†

 Geometric interpretation
max Prob(X) s.t. ||X||2 = 1
X

unit 2-norm ball

Analysis prior polytope

?
analysis prior polytope have vertices of null( ) where is submatrix made from
N 1 rows of W, which is of dimension L N, L > N
 Synthesis at a glance

Advantages
• Clear, explicit, constructive, intuitive description of
the solution
• Vast empirical evidence that natural image is
generally a sparse combination of atomic elements
(results lacking for analysis prior)
• Informally assumed to provide higher quality result
• Benefit from more redundant dictionaries
Disadvantages
• Slower to constrain energy
• More sensitive to bad atoms and cascading effects
 Analysis at a glance

Advantages
• Much less sensitive to bad atoms and cascading effects
• Faster to constrain energy

Disadvantages

• very little algorithms developed for analysis priors

• lacks general theoretical results
• might not benefit from dictionary redundancy
 A word on algorithms

For large-scale problems, need a first-order method

IST is not guaranteed to converge to a solution

for the analysis case

Emerging algorithm called NESTA that has

guarantees to converge superlinearly using both
kinds of priors (due to special form of
objective function)
 Application to CRSI

CRSI-based interpolation assumes:

T (x) = Rx
p=1
W = 2D or 3D Curvelet

We set:
= 0.01||xo ||2
2
 Application to CRSI

Operator is trace removal from seismic data

50 50
time sample

time sample
100 100

150 150

200 200

250 250
50 100 150 200 250 50 100 150 200 250
trace number trace number

xo Rxo
 Application to CRSI

Analysis and Synthesis forms:

Analysis prior
xMAP-A = arg min ||Cx||1 s.t. ||y Rx||2
2
<
x

Synthesis prior
xMAP-S = C arg min ||w||1 s.t. ||y
T
C T
w||2
2
<
w

= 0.01||xo ||2
2
 CRSI intuitions

• Randomly subsampled Fourier basis is a known,

well-behaved compressive sensing projector
• 2D Curvelet representation can be thought of as a
partitioned representation of 2D Fourier
• Randomly subsampled 2D Curvelet basis should
behave similarly to randomly subsampled 2D
Fourier (rough statement)
• Curvelet atoms “bridges gaps in the traces”
Application to CRSI, results 25%

50
time sample

100

150

200

250
50 100 150 200 250
trace number

25% traces missing

 Application to CRSI, results 25%

50 50
time sample

100

time sample
100

150 150

200
200

250
250
50 100 150 200 250
trace number 50 100 150 200 250
trace number

Analysis result 42.3dB Synthesis result 44.9dB

time: 83.5s time: 936.6s
94 iterations 478 iterations
(0.89s per iter) (1.96s per iter)
 Application to CRSI, results 25%
20

15

10

Original signal
5
amplitude

−5 curvelet coefficients
−10

−15

−20
0 1 2 3 4 5
coefficient number 5
x 10
20 60

15 40

10
20
5
amplitude

amplitude
0
0
−20
−5
−40
−10

−15 −60

−20 −80
0 1 2 3 4 5 0 1 2 3 4 5
coefficient number x 10
5 coefficient number 5
x 10

Analysis result Cx Synthesis result w

Application to CRSI, results 40%

50
time sample

100

150

200

250
50 100 150 200 250
trace number

40% traces missing

 Application to CRSI, results 40%

50 50
time sample

time sample
100 100

150 150

200 200

250 250
50 100 150 200 250 50 100 150 200 250
trace number trace number

Analysis result 25.0dB Synthesis result 27.1dB

time: 94.6s time: 870.6s
110 iterations 487 iterations
(0.86s per iter) (1.79s per iter)
 Application to CRSI, results 40%

50 50
time sample

time sample
100 100

150 150

200 200

250 250
50 100 150 200 250 50 100 150 200 250
trace number trace number

SPGL1 synthesis result 24.3dB NESTA synthesis result 27.1dB

time: 66.3s time: 870.6s
51 iterations 487 iterations
(1.3s per iter) (1.79s per iter)
Application to CRSI, results 55%

50
time sample

100

150

200

250
50 100 150 200 250
trace number

40% traces missing

 Application to CRSI, results 55%

50 50
time sample

100

time sample
100

150 150

200 200

250 250
50 100 150 200 250 50 100 150 200 250
trace number trace number

Analysis result 18.1dB Synthesis result 16.9dB

time: 120.8s time: 908.4s
128 iterations 494 iterations
(1.00s per iter) (1.84 per iter)
 Application to CRSI, results 55%
20

15

10

Original signal
5
amplitude

−5 curvelet coefficients
−10

−15

−20
0 1 2 3 4 5
coefficient number 5
x 10

20 80

15 60

10 40

5 20
amplitude

amplitude
0 0

−5 −20

−10 −40

−15 −60

−20 −80
0 1 2 3 4 5 0 1 2 3 4 5
coefficient number 5
x 10 coefficient number 5
x 10

Analysis result Cx Synthesis result w

 Discussion

• Analysis case has shorter iteration time, which is

easily understandable from looking at the details of
NESTA (2-norm constraint is more expensive than
obtaining a gradient on objective)
• Nontrivially there is better convergence behaviour
for analysis priors for CRSI
• Seemingly for CRSI using NESTA there is no reason
to use synthesis prior (unless really picky about
SNR)
 Future Work

• Why does the analysis problem experience better

convergence? Is this specific to CRSI or to NESTA?
• Try other types of R (ex. simultaneous seismic
sources) to see if this behaviour is specific to the
Curvelet frame on seismic signals
• Try other future reconstruction algorithms