Signal Processing - September 2016 - 54

Spectral estimation (Prony's Method)
Given 2K contiguous measurements z n~0 = / Kk =- 01 C k e jnw0 t k,
n e [m, 2K + m), Prony's method aims to estimate unknowns
" C k, d k ,Kk =- 01 from a system of equations that is linear in reflection coefficients C k but nonlinear in depths t k = 2d k /c . The
solution to this problem relies on an underlying annihilation
equation. Let us define a polynomial of degree K ,
q m z -m

Toeplitz Matrix

K-1

whose roots are " e j~0 t k ,k = 0 . Observe that filtering sequence
" q m ,Km = 0 with measurements " z m~ 0 ,Km-=10 results in nullity,
^ q m ) z m~ 0h =

=

K

/ ql z

l=0
K-1

~ 0 ^m - l h

K

=

/ Ck e / ql e

k=0

K

K-1

l=0

k=0

With filter " q m ,mm == K0 known, we construct Q ^z h , and its
roots lead to the K estimates, " t k ,Kk =- 01 . With the depths
known, estimating " C k ,Kk =- 01 is the usual linear least-squares
problem since C k 's are linearly constrained in the definition of z n~0 .

/ q l / C k e j^ m - l h

~0 tk

o e jm~0 t k = 0.
1444jm2
4443
~ t
-jl~ 0 t k

l=0

Q^ e

0 kh

=0

SRF parameters " C k, t k ,Kk =-01 are consistent with the experimental setup.
Imaging transient phenomenon may be used for several
applications. For example, consider the experimental setup in
Figure 7. A diffusive, semitranslucent sheet covers a placard
that reads "Time of Flight." A conventional digital camera is
not able to image through the diffuse/scattering object. However, in the context of a TD-ToF imaging setup, this scene has
a sparse SRF with K = 2 . In fact, the case of K = 2 described
in Figure 6 uses measurements directly from the example in
Figure 7 under consideration. By applying the sparse signal

with sampling rate T = 70 ps. In each case, we recover the K-sparse
SRF, h K in the following steps:
1) Obtain the discrete Fourier transform of sampled measuret *, .
r n , that is m
ments m
*
t , with the sampling kernel zt , to obtain
2) Deconvolve m
t *, /zt ,, , ! 6- M 0, M 0@, M 0 $ K .
ht K ^,~ 0 h = m
3) Use Prony's method [cf. "Spectral Estimation (Prony's
Method)"] to estimate the sparse SRF " C k, t k ,Kk =-01 given
ht K ^,~ 0 h.
We plot the sampled, time-reversed measurements m
n
together with the real part of ht K ^,~ 0 h in Figure 6. The resulting

Sparse Sampling

Time Domain

Fourier Domain
Γ1

K=2

1
0.5

Γ0

0
1

0.8

φ

Γ1

mn
Γ0

Σ

n∈

δ (t − nT )

1.2

1.4

1

Γ2

0.5

K=3

0
1.6

1.8 2
2.2 2.4 2.6 2.8
Time (Nanoseconds) × 10-7

× 10-4
6
4
2
0
-2
10

20

30

Estimated

40

50

Amplitude (a.u.)

m=0

× 10-4

10 20 30 40
Fourier Harmonics

8
6
4
2
0
50

Amplitude (a.u.)

K

/

Measured

k=1

h = zK

Amplitude (a.u.)

~0 tk

m # n 1 m + 2K,
R z^m + K h~ 0 z^m + K - 1h~ 0 g
z m~ 0 VWRS q 0 VW
S
g
z
z
z
S ^m + K + 1h~ 0
^m + K h~ 0
^m + 1h~ 0 WS q 1 W
WS h W = 0.
S
h
h
j
h
WS W
SS
z^m + 2K - 1h~ 0 z^m + 2K - 2h~ 0 g z^m + K - 1h~ 0WXSTq K WX
T14444444444
244444444443

Amplitude (a.u.)

K

% ^z - e j

Q ^z h =

n 1 m + 2K
, in vector-matrix notation, the soluGiven " z n~0 ,m # n
tion to the previous equation is achieved by solving for

Figure 6. Time-domain ToF can be reinterpreted as a sparse sampling problem in the case of transient imaging. The goal is to recover the sparse scene
response function given its low-pass-filtered samples with bandwidth M 0 = 25 . In the context of sampling theory, the low-pass kernel z is an autocorrelation of the probing function. We discuss the recovery of sparse signal for the case K = 2 and K = 3 . We also show the real part of the measured and
estimated Fourier transform of the scene response function ht K ^,~ 0h .

54

IEEE SIgnal ProcESSIng MagazInE

|

September 2016

|
Table of Contents for the Digital Edition of Signal Processing - September 2016
