# Estimating the Signal by Deconvolution with a Prior on the Filter Coefficients and the Signal Samples

Assume I have signal $$y[n]$$ which is a result of convolution between channel $$h[n]$$ and signal $$x[n]$$. which means:

$$y[n] = h[n] \ast x[n]$$ where $$\ast$$ is the convolution operation

The signal $$y[n]$$ could be complex since we can consider the channel $$h[n]$$ to be complex too.

In normal case, $$h[n]$$ should be known in order to estimate $$x[n]$$ using deconvolution process.

My question what about if I only know that $$\forall n$$, $$x[n] \in \left\{ -1, 1 \right\}$$ it means $$x[n]$$ is either $$1$$ or $$-1$$, it's a vector and each value in the vector is $$1$$ or $$-1$$ ($$x[n]$$ is a vector of +1/-1 we means I need to estimate the whole vector).

For example if its length is $$4$$ , it could be $$[1,-1,-1,1]$$ or $$[1,1,1,1]$$ and so on. Is it possible in that case to perform anyway, for example, deconvolution or any other method to estimate $$x[n]$$?

NP: The maximum length of $$x[n]$$ can be $$256$$ and maximum length of $$h[n]$$ can be $$64$$ , and we have a known information about vector $$x[n]$$ which is the $$sum(x[n]) = 0$$.

• Could you please clarify your question? For instance, your equation reads $h=h \ast x$ (without $y$); you consider a "partially known signal" while it seems that $h$ is a partially known system (or filter); is $[1,-1]$ an interval, or only a set with two values? This could be an instance of constrained blind deconvolution, or myopic deconvolution – Laurent Duval Feb 21 at 10:20
• @LaurentDuval I modified it. reading h, it's a set of values, it's either 1 or -1, for example, [1, -1,1,-1] or [1,-1,-1,1] and so on. thank you so much. Second, what you mean by blind deconvolution or myopic deconvolution. Could you please describe the details of each method? .. thank you again – Gze Feb 21 at 12:52
• I mean $h$ is a vector where every value of it either $1$ or $-1$, and $x$ is unknown vector. $y$ is the known vector representing the convolution of two vectors. – Gze Feb 21 at 13:00
• This would make more sense to me if x[n] was +1/-1 since h[n] typically refers to the channel, and then in this case x[n] would be your decisions of the binary data that was transmitted using BPSK modulation (for example). Is this what you intend? Also if so, are you able to transmit training sequences where you know what y[n] is, you can receive x[n] and from that establish what h[n] is through deconvolution? And if that is the case, can you provide more details as to what the situation is that you are only able to get +/-1? – Dan Boschen Feb 21 at 16:43
• @DanBoschen first, thanks for you reply. Yes that what I mean, it's the same that x[n] is +1/-1 and h[n] is the channel, but It's different about binary BPSK data because I want to estimate the vector at once. I mean, if x[n] is the binary data, I need to estimate it as vector whose length is for example equals 4. let me provide an example, h[n] is random vector representing the channel with length equal to 3, and x is a vector of length 4, (let's take it as a row from Hadamard-Walsh matrix but we don't know which column because that what I need to estimate in my problem), – Gze Feb 21 at 17:03

I would take approach based on Blind Deconvolution.

Since we're dealing with ill posed problem some assumptions should be made.
The intuitive approach would be using the information as a prior for the signal. Another idea is to add LPF assumption of the Filter by setting the sum of its coefficients to be 1 and non negative. Yet since we have Discrete Prior on the signal we're getting into combinatoric problem.
Which means brute force solution where the number of combinations is $${2}^{n}$$ where $$d$$ is the number of the signal samples.

For $$n \leq 16$$ I'd say it would work for the given input size.
Yet for solution with higher number of samples this method isn't feasible.

In order to deal with higher dimensions (More samples) I'd use a GMM:

Namely the Prior model is a Gaussian Mixture Model (GMM) with 2 Gaussian's centered at $$\left\{ -1, 1 \right\}$$ with very small variance in order to approximate discrete probability function.

So the problem I'm looking to solve is given by:

\begin{aligned} \arg \min_{h, x} \quad & \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & \sum h = 1, \, h \succeq 0 \end{aligned}

## Step 1 - Solving for the Filter $$h$$

Given the signal $$x$$ is known, solving for the filter is pretty easy using matrix form of the problem (Which is convex):

\begin{aligned} \arg \min_{h} \quad & \frac{1}{2} {\left\| X h - y \right\|}_{2}^{2} \\ \text{subject to} \quad & \sum h = 1, \, h \succeq 0 \end{aligned}

I showed, code included, how to solve such problem in my answer to How to Project onto the Unit Simplex as Intersection of Two Sets (Optimizing a Convex Function)?

## Step 2 - Solving for the Signal $$x$$

The model is $$y \mid h \sim \mathcal{N} \left( h \ast x, {\sigma}_{n} I \right)$$ and the prior $${x}_{i} \sim 0.5 \mathcal{N} \left( {\mu}_{1} = -1, {\sigma}_{1}^{2} = {0.1}^{2} \right) + 0.5 \mathcal{N} \left( {\mu}_{2} = 1, {\sigma}_{2}^{2} = {0.1}^{2} \right)$$.

I'd use the MAP so we have:

\begin{aligned} \arg \max_{x} p \left( x \mid y \right) & = \arg \max_{x} p \left( y \mid x \right) p \left( x \right) \\ & = \arg \max_{x} \log p \left( y \mid x \right) + \log p \left( x \right) \\ & = \arg \min_{x} -\log p \left( y \mid x \right) - \log p \left( x \right) \\ & = \arg \min_{x} \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} - \lambda \log p \left( x \right) \\ & = \arg \min_{x} \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} - \lambda \sum \log p \left( {x}_{i} \right) \end{aligned}

Where $$\lambda \propto N {\sigma}_{n}^{2}$$ where $$N$$ is the number of samples (Dimension of $$y$$).

This can be solved by any solver. I'd use MATLAB's fminunc().
Though one could alter (For MAP Estimation) the Expectation Maximization (EM) process for faster and better converging algorithm. Another option would be using Probabilistic Programming with one of the options available today.

Remark: The above is Bayesian Modeling of the problem. One could build optimization problem with some intuition in the form of:

$$\arg \min_{h, x} \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} + \lambda \sum_{i = 1}^{m} {\left( {x}_{i}^{2} - 1 \right)}^{2}$$

Which isn't motivated by Bayesian model but still drives the solution to where we want it.

## Initialization

One approach to initialization of the estimated $$x$$ signal is to use hard threshold. So we set $${x}_{i} = 1$$ if $${y}_{i} \geq 0$$ and $${x}_{i} = -1$$ otherwise.

This approach could also be a greedy method to solve the step for $$x$$. Yet it doesn't take under account the delay of the filter.

After iterating enough for a stable solution one could round the result of $$x$$ such that $${x}_{i} \in \left\{ -1, 1 \right\}$$.

I haven't tested this approach myself, but I really like its model.
I will publish the results of MATLAB simulation soon.

• Thank you for your reply. I will check it and let you know if it works soon. By the way, we have a known constraint that $sum(x) = 0$ since all existed vectors $x$ which will be convoluted with channel $h$ are orthogonal. (I will add that notice to the question) – Gze Feb 25 at 8:06
• I really liked the question. I haven't yet had the time to play with code with those ideas. But it surely be a good start. Adding prior information into the model is the way to go. Enjoy... – Royi Feb 25 at 8:08
• Thank you so much again, I will try to analyse your reply and let you know if it's ok or if I got an problem in implementing that way. I will feedback you soon. I was thinking that is possible to do that by using deep learning model and then train till get the desirable minimum cost function, but it needs time to formulate the problem itself. – Gze Feb 25 at 8:12
• I think probabilistic languages are better fit for this kind of a problem. What I don't like about my model is I use MAP with Bi Modal Prior. It might cause issues. But until implemented and analyzed we can't be sure. – Royi Feb 25 at 8:19
• @Gze, Could you please mark this as an answer? I thought you already did. – Royi May 27 at 15:35

Would that be anything like blind channel estimation using the Constant Modulus Algorithm?

• I think I should read about that. Do you have any idea how that can implemented in our case ?? .. – Gze Feb 24 at 4:04

This sounds like a blind channel estimation problem. Blind channel estimation is used such as in emerging massive MIMO systems where pilot contamination can otherwise limit the advantage of adding additional transmitters.

A very simple example of blind channel estimation is decision directed least squares using the least squares technique that I describe at this post How determine the delay in my signal practically , with an estimate of the transmit signal based on hard decisions at the receiver. This technique works well in higher SNR conditions when the uncorrected error rate is still reasonably low (actual numbers would depend on the actual conditions but I would guess that channels for error rates on the order of $$10^{-2}$$ to $$10^{-3}$$ could still be determined and with that those error rates significantly improved based on decisions alone for the estimated tx signal).

For much more details on blind channel estimation, see this paper and linked references by Xiaotian Li and others that describes statistical methods such as the Signal Subspace Method which is widely used in MIMO and OFDM. This is a good choice when there are a large number of received symbols but the author goes into other deterministic methods based on the least squares methods such as I have linked that would be more appropriate for a smaller number of samples such as with to the OP’s question. The paper is: Xiaotian Li - Blind Channel Estimation Based on Multilevel Lloyd-Max Iteration for Nonconstant Modulus Constellations.

• I agree, that might be like constraint blind channel estimation, but didn't understand how can we implement it into my case. – Gze Feb 23 at 11:20
• Well the simple case of decision directed is very straightforward and would work fine above an SNR threshold- do you see that case? – Dan Boschen Feb 23 at 12:29
• OK, I don't care of SNR for that moment. it's ok if it will work above an SNR threshold. but could you please add more details about that ? – Gze Feb 23 at 13:23
• You make a decision based on the received data of what was transmitted- if you have high SNR and no frequency offset or other distortions that decision will be trivial. The decision then is the “known” tx as if it was a training sequence and then follow the links I gave. Try a test case to experiment with it and see for yourself how far you can distort the signal with the channel. – Dan Boschen Feb 23 at 13:31
• Yes, but in my case I don't have "known" tx. . I was thinking what's about to sum the transmitted signal with ones(x), it means x will become 0 and 2, the results signal will be sparse. then we can implement compressive sensing to detect x back. – Gze Feb 24 at 4:03