Restrictions

Up to now, I only spoke of the overdetermined problem, which implies the inversion of the matrix L^TL. Things are different in the underdetermined case, where we have to invert LL^T. Effectively, this matrix is not Toeplitz, even for a regular sampling in offset. The expression of a component of LL^T is:

$$(LL^T)_{ik}=\sum_p\exp(j\omega p(h_i^2-h_k^2)) \;.$$

With a regular sampling $\delta h$ in offset, supposing h₀=0, this term becomes:

$$(LL^T)_{ik}=\sum_p\exp(j\omega p(i^2-k^2)(\delta h)^2) \;.$$

Consequently, (LL^T)_ik does not depend only on $i\!-\!k$, and the structure of the matrix LL^T is not Toeplitz. So, it is not possible to use Levinson algorithm in the underdetermined transformation $d(t,h)\rightarrow U(t_0,p)$, where we have more parameters p than offsets h.

We can reason similarly for the transform $U(t_0,p)\rightarrow d(t,h)$. Suppose that, rather than using simply the modeling matrix L, we want to compute the least-squares inverse of L^T: (LL^T)^-1L in the overdetermined case, (L^TL)^-1L^T in the underdetermined case. Thus, Levinson algorithm could only be applied in the underdetermined case.