0
$\begingroup$

In this post:

Compensating Loudspeaker frequency response in an audio signal

I derive the Wiener-Hopf equations for least squares equalization (and channel estimation if we swap Tx and Rx) from the convolution matrix. This is used to equalize a waveform from distortions receiver over a multipath channel or where similar distortions occur (multiple copies of a transmitted signal arriving at different delays). It was pointed out to me (correctly I believe) that actually solving for the required autocorrelation matrix from the convolution matrix is less numerically stable than solving for the inverse channel directly.

What would be the channel conditions where the numerical instability results? The best answer will include an example and show both approaches to demonstrate the unstable condition and best approach (for least squares solutions).

This will help provide further intuition into how much we need to be concerned with this and under what conditions, and alternate approaches to solving the same problem.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

The problem is given by:

$$ \arg \min_{\boldsymbol{h}} \frac{1}{2} {\left\| \boldsymbol{X} \boldsymbol{h} - \boldsymbol{y} \right\|}_{2}^{2} $$

Where $ \boldsymbol{X} $ is the convolution matrix (Toeplitz Matrix) composed of the samples of $ \boldsymbol{x} $, $ \boldsymbol{h} $ are the channel coefficient to estimate and $ \boldsymbol{y} $ are the measured samples.

This solution is available using Least Squares solver of linear system.
The accuracy of the solution depends on the condition number of the matrix $ \boldsymbol{X} $.

The least squares solution is also the solution to the Normal Equations (Which matches solving for the correlation matrix instead of directly):

The problem with solving the normal equations form, which matches the solution by the correlation matrix, namely:

$$ \boldsymbol{X}^{T} \boldsymbol{X} \boldsymbol{h} = \boldsymbol{X}^{T} \boldsymbol{y} $$

The problem with solving this for is doubling the condition number. Since this case solves a linear system with respect to $ \boldsymbol{X}^{T} \boldsymbol{X} $ which has a condition number which doubled compared to $ \boldsymbol{X} $.

Why is that?
It is easy to see using the Singular Value Decomposition (SVD).
If the SVD of $ \boldsymbol{X} $ is given by $ \boldsymbol{X} = \boldsymbol{U} \boldsymbol{S} \boldsymbol{V}^{T} $ then the condition number is given by $ \frac{\max \left( \operatorname{diag} \left( \boldsymbol{S} \right) \right)}{\min \left( \operatorname{diag} \left( \boldsymbol{S} \right) \right)} $.

The SVD of $ \boldsymbol{X}^{T} \boldsymbol{X} $ is given by:

$$ \boldsymbol{X}^{T} \boldsymbol{X} = \boldsymbol{V} \boldsymbol{S} \boldsymbol{U}^{T} \boldsymbol{U} \boldsymbol{S} \boldsymbol{V}^{T} = \boldsymbol{V} \boldsymbol{S}^{2} \boldsymbol{V}^{T} $$

Since the singular values are doubled the condition number it doubled.

In practice, it means, if you have $ \boldsymbol{X} $ and $ \boldsymbol{y} $ do not calculate the correlation matrix and doucble the condition number. Just do X \ y in MATLAB or np.linalg.solve(X, y) in Python.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Related to dsp.stackexchange.com/questions/55284. $\endgroup$
    – Royi
    Jul 20 at 19:58
  • 1
    $\begingroup$ @DanBoschen, Directly means you neither calculate the correlation matrix nor its inverse. You just do H \ y in MATLAB or np.linalg.solve(H, y) in Python. As we talked, if deconvolution it periodic, you may do it in the spectrum domain (Or with proper padding). Just don't use the correlation matrix. You double the condition number. $\endgroup$
    – Royi
    Jul 21 at 7:22
  • $\begingroup$ ok that is what I initially thought you intended so did not misunderstand. An example showing the difference and the channel conditions that would result in the higher instability would be ideal to add to this answer as I was looking for further practical insight as well. Understood on periodic FFT solutions. $\endgroup$
    – Dan Boschen
    Jul 21 at 11:05
  • $\begingroup$ @DanBoschen, I can derive this mathematically, namely show how the error of the solution of a linear system depends on the condition number. Will that be enough? As it is more general than a specific example. $\endgroup$
    – Royi
    Jul 21 at 11:35
  • 1
    $\begingroup$ @DanBoschen. In cases the correlation matrix has an eigen value which is close to 0 you'll have some issues. You may see in the related question how it works for low pass filter. $\endgroup$
    – Royi
    Jul 21 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.