# Estimating Convolution Input Under the Assumption of Sparsity and Constant Non Zero Values Using Compressive Sensing Approach

I was wondering about if there is compressive sensing algorithm to estimate the sparse vector where the number of non-zeros values and amplitude of every non-zeros value are known. For example, assume we have a vector $$x$$ whose length is $$N$$x$$1$$ with only $$N/2$$ equal non-zeros known values but unknown location of those values. That vector is convolved with a channel $$h$$ resulting a vector $$y$$. it means that:

$$y = h⊗x$$, where $$⊗$$ is the convolution operation.

Is it possible to use compressive sensing to estimate the locations of non-zeros values in $$x$$ based on $$y$$.

Here is the code of an example where the length of vector $$x$$ is $$32$$ and channel $$h$$ = 16:

clear all; clc;

%%%% Build the sparse vector
X2 = randi([1 length(X)-1], 1);

x = X(1,:) + X(X2+1,:);         % Here the built sparse vector
x = x / max(x);                 % To make the sparse vector either one or zeros

h = randn(1,16);                % channel
y = conv(x,h);
y = y(1:end-length(h)+1);       % To remove the delay of convolution


Thank you

• Do you know something about $h$? How big is the problem ($N$)? What's the noise level? – Royi Apr 22 '20 at 15:35
• @Royi for example let's take $N = 128$ and $h$ a random vector of $32$x$1$. We don't care of the noise for the moment. – Gze Apr 23 '20 at 6:44
• Do we know anything about $h$? – Royi Apr 23 '20 at 6:58
• No .. we don't know anything about it. . . "We know it's sparse too, but I don't know if that will help or no" – Gze Apr 23 '20 at 7:23
• So our prior is $h$ is sparse yet unknown and $x$ is sparse with known constant values for all non zero elements? – Royi Apr 23 '20 at 13:30

Basically your problem is called Blind Deconvolution.
It means we want to estimate both the operator and the input given the output.

You model is Linear Time Invariant Operator so we have LTI Blind Deconvolution.
In general blind deconvolution is ill poised problem.
So we need to make assumptions about the model. The more assumptions the better the chance to solve this really hard problem.

What do we have in your case:

1. The input signal is sparse.
2. The input signal has 2 values, either zero or other known value.

What's missing is some assumptions on the operator $$h$$.

### Deconvolution in Image Processing

The field which pushes the deconvolution problem farther and farther is mostly the image processing field.
There are many models of real world images and convolution kernels.

Let's talk about the most common for each:

• In most cases the convolution kernel is assumed to be LPF with its sum of coefficients equal 1 and each coefficient is non negative.
• In most cases the image is assumed to be "Piece Wise Smooth. Enforcing it using the Total Variation Model which basically says the Gradients are distributed according to Laplace Distribution.

With those 2 models we can model the problem as:

\begin{aligned} \arg \min_{h, x} \quad & \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} + \lambda \operatorname{TV} \left( x \right) \\ \text{subject to} \quad & \sum h = 1 \\ & {h}_{i} \geq 0 \\ \end{aligned}

As can be seen this is highly non convex problem. The method used to solve it is by splitting methods.

So we solve it by iterations:

We set $${h}_{i}^{0} = \frac{1}{N}$$, then:

• For the estimated signal:

\begin{aligned} {x}^{k + 1} = \arg \min_{x} \quad & \frac{1}{2} {\left\| {h}^{k} \ast x - y \right\|}_{2}^{2} + \lambda \operatorname{TV} \left( x \right) \\ \end{aligned}

• For the estimated kernel:

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

So, in your case we can do the following:

1. Replace the regularization by the Sparsity Model. Solve the $$x$$ iteration by the methods in Thomas' answer (Yaghoobi, Blumensath, Davies, 2007, Quantized Sparse Approximation with Iterative Thresholding for Audio Coding - DOI, Nagahara, 2015, Discrete Signal Reconstruction by Sum of Absolute Values - DOI). Solve for $$h$$ as for Least Squares with Simplex Constraint.

2. Use model without convolution using Dictionary and use Dictionary Learning Methods like K-SVD. For the signal estimation iteration still you should use the methods above.

Some related questions:

• Thank you so much ... I will try to write the matlab code for that methods and let you know. . . Do you have the matlab code for them ? What is the $TV$ – Gze Apr 27 '20 at 20:05
• @Gze, I added some related references. Each of them should assist with some angle. Please mark those which assisted you. – Royi Apr 28 '20 at 5:21
• We set the the first value of $h$ which is $h_i^0$ as known, is that right ? – Gze May 1 '20 at 18:04
• Yep. You can set it uniformly. – Royi May 1 '20 at 18:18
• when setting $h_i^0*x$, what you mean $x$ ? Is it $x_i^0$ too, which can be found as $y_i^0/h_i^0$? and $*$ is multiplication or convolution ? – Gze May 2 '20 at 20:48

You can approach this problem as a special case of the "$$k$$-simple bounded signal" class described in (Donoho & Tanner, 2010 - Precise Undersampling Theorems ), see page 2, Example 3. Particularly, your signal is a "0-simple" signal, i.e. your values are either 0 or some constant. The problem can easily be scaled to 0 or "some constant" instead of 0 or 1.
Edit - two more solutions: Another approach can be Masaaki Nagahara's (Nagahara, 2015, Discrete Signal Reconstruction by Sum of Absolute Values - DOI). In particular, your case corresponds to the binary case in the mentioned paper. That is, $$r_1 = 0$$ and $$r_2$$ is your known amplitude or vice versa if the amplitude is negative. Use the probabilities $$p_1$$ and $$p_2$$ to express your known sparsity.
• Thank you so much for your continuous help.. I really appreciate that, but I don't know $h$, so how can I build the measurement matrix ? I still didn't understand your exact meaning,is it possible to add more details to your answer? .. I maybe should read the paper (Donoho & Tanner, 2010) carefully. – Gze Apr 23 '20 at 11:27
• Any of the approaches you added assume known $h$? – Royi Apr 25 '20 at 22:33