Maximum likelihood estimation complexity computation

I have a basic question about maximum likelihood (ML) estimator and its implementation.

I am trying to simulate a communication system, while using ML at the receiver side to find the transmit sequence. The received signal is given by:

$$y=Hx+n$$

$$y, H, x$$ and $$n$$ indicates the received signal, MIMO channel of $$N_t$$x$$N_r$$ transmit and receive antennas, transmitted signal and AWGN, respectively.

I'm trying to detecto $$x$$ based on ML detector, so the estimated signal $$x$$ can be written :

where $$h_{ln}$$ represent the $$l^{th}$$ column of the channel $$H$$. I have read in some books and papers, such as in This paper that the complexity computation of the above equation is $$6N_rN_tM$$, where M represent the constellation order of signal, where it was mentioned that $$h_{ln}x$$ requires $$4N_r$$ for $$Hx$$ and $$2N_r$$ for $$|y_n-h_{ln}x|^2$$.

My question, in $$4N_r$$ and $$2N_r$$ what do the $$4$$ and $$2$$ represent?? In other words, the comlexity computation doesn't depend on $$x$$ too? for example, if we up-sampled the signal $$x$$ in transmitter or we spread it using Walsh code, the complexity computation won't change as long as we are using the same number of $$N_t$$ and $$N_r$$ ??

thank you

• there's something wrong with your $\hat x$ formula: there's a sum with a counter $n$, but $n$ doesn't appear anywhere in the formula. Make sure you're actually asking the question you've meant to ask! – Marcus Müller Apr 18 '19 at 6:22
• @MarcusMüller .. Thank you for your note. I modified it. it's clear now. The question is about the complexity that it taken by ML. – New_student Apr 18 '19 at 7:27
• Then the paper you're referring to is pretty much unrelated to your problem! The title of the paper is "Low-complexity MPSK estimator for spatial modulations", and what you're looking for is the ML – which is neither specific to MPSK nor low-complexity. – Marcus Müller Apr 19 '19 at 9:59

Ordinary Least Squares problem

Your

$$\hat x = \arg\min_x \sum_{n=1}^{N_r} \left\lvert y_n - h_n x\right\rvert^2$$

is just a way of saying

$$\hat x = \arg\min_x \left\| y - Hx \right \|$$ and that is called an Ordinary Least Squares estimation problem.

Its objective function is of a quadratic form, so we don't have to actually iteratively optimize or anything. There's an analytic solution to the above equation:

$$\hat x = \left(H^T H\right)^{-1}H^T y\text.$$

As you can see, this has absolutely nothing to do with the constellation order so far – and it doesn't have to. The constellation order only makes a difference to the decision complexity, and by the orthogonality principle, that's a step to be done after you've estimated the transmit signal.

Don't invert that matrix

Now, it's practically never desirable to calculate a matrix inverse, so the thing that you actually solve is

$$\left(H^T H\right)\hat x = H^T y\text.$$

How complex the solution to that is depends on the properties of your MIMO channel matrix!

The quadratic / full-rank MIMO case

In the (very special) case that $$H$$ is normal (that implies among other things quadratic, ie. as many receive as transmit antennas $$N_r=N_t=:N$$), you do that by applying a QR decomposition to $$H^T H$$:

\begin{align} \left(H^T H\right)\hat x &= H^T y\\ QR \hat x &= H^T y\\ R\hat x &= Q^T H^T y\tag{1}\\ &= \nu y\tag{2} \end{align}

Since $$R$$ is a triangular matrix, $$(1)$$ s the point where you just backsubstitute. Luckily, $$R$$, $$Q^T$$ and $$H^T$$ only need to be calculated once ever, so we can estimate many $$\hat x$$ from many $$y$$ as long as the channel doesn't change at fixed complexity.

Complexity

You do the usual paper trick of ignoring the fact that you need to acquire $$H$$ first. That can, and quite possibly will, dominate the complexity of this (so don't be a bad scientist – figure out how you get your $$H$$ and how compelx that is, if you're writing some kind of publication).

So, assuming you already have the $$H$$, the operations you are doing per channel realization (i.e. only once every time $$H$$ changes, which probably doesn't happen very often):

1. calculating one half of the hermitian matrix $$H^TH$$ (no need to calculate the whole thing, it's redundant).
2. a QR decomposition of a hermitian matrix ($$H^TH$$)
3. calculating $$\nu = Q^TH^T$$

The operation you do per receive vector (i.e. for every symbol time step, typically, so pretty often):

1. Backsubstituting in $$R\hat x$$ to finally get $$\hat x$$.

The complexities per channel realization are:

1. $$\frac{N^3}2$$
2. depends very much on your QR decomposition algorithm (which depends on matrix size, and need for numerical stability, and your platform), but typically no worse than $$N^4$$
3. $$N^3$$

So that's a total of $$C_H = \mathcal O \left(\frac 32 N^3 + N^4\right)$$ multiply-accumulates.

1. $$\frac12 N^2$$

So, $$C_y = \mathcal O \left(\frac12 N^2\right)$$.

If we introduce a coherence time (measured in symbol durations) $$T_C$$ for which $$H$$ doesn't change, you get an overall complexity of

\begin{align} C_{\text{overall}} &= \mathcal O \left(\frac {\frac 32 N^3 + N^4}{N T_C} + \frac1{2N} N^2\right)\\ &= \mathcal O \left(\frac {\frac 32 N^2 + N^3}{T_C} + \frac12 N\right) \end{align}

per receive symbol (i.e. per element of $$\hat x$$).

Bringing the constellation order into this

As said above, the constellation order only makes a difference to the complexity of the decider. However, we know under ML rule that the likeliest transmit symbol vector is the one geometrically closest to the likeliest transmit symbol vector – and since all elements of that are to be assumed independent from each other, that minimum can be found individually. The complexity of the decision thus only depends on the (SISO) constellation decoder you pick; nothing has been said about that, and there's immensely different implementations of these, so I will not allow myself to give you a complexity estimate here – I'll just allow myself that I can't see the formula as given by the paper appearing anywhere in my head.

It is a very valid question to ask whether it makes sense to apply the ML detection principle to individual elements of the transmit / receive vector. Unless you're in the very massive MIMO case, it makes sense to assume that there's channel coding on these symbols, and that they are, in fact, not stochastically independent from each other. So, classically, a MLSE-based (typically: Viterbi) soft-input channel decoder would be what you use, or some kind of message-passing based channel decoder.

• OK .. thank you so much. So I understand that complexity depends only on Channel $H$ and the constellation orer $M$.. right? – New_student Apr 19 '19 at 9:56
• no. As explicitly said twice in my answer, there's no inherent dependency on $M$. Please re-read my answer. Thank you. – Marcus Müller Apr 19 '19 at 9:58