5
$\begingroup$

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 
X = hadamard(32); 
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

$\endgroup$
13
  • $\begingroup$ Do you know something about $ h $? How big is the problem ($ N $)? What's the noise level? $\endgroup$
    – Royi
    Apr 22, 2020 at 15:35
  • $\begingroup$ @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. $\endgroup$
    – Gze
    Apr 23, 2020 at 6:44
  • $\begingroup$ Do we know anything about $ h $? $\endgroup$
    – Royi
    Apr 23, 2020 at 6:58
  • $\begingroup$ 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" $\endgroup$
    – Gze
    Apr 23, 2020 at 7:23
  • 1
    $\begingroup$ So our prior is $ h $ is sparse yet unknown and $ x $ is sparse with known constant values for all non zero elements? $\endgroup$
    – Royi
    Apr 23, 2020 at 13:30

2 Answers 2

4
$\begingroup$

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:

  1. Using Total Variation Denoising to Clean Accelerometer Data.
  2. The Meaning of the Terms Isotropic and Anisotropic in the Total Variation Framework.
  3. Why Sparse Priors Like Total Variation Opts to Concentrate Derivatives at a Small Number of Pixels?
  4. How Can I Use MATLAB to Solve a Total Variation Denoising / Deblurring Problem?
  5. Intuitive Meaning of Regularization in Imaging Inverse Problems.
  6. Estimation / Reconstruction of an Image from Its Missing Data 2D DFT.
  7. Deconvolution of an Image Acquired by a Square Uniform Detector.
$\endgroup$
8
  • $\begingroup$ 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$ $\endgroup$
    – Gze
    Apr 27, 2020 at 20:05
  • $\begingroup$ @Gze, I added some related references. Each of them should assist with some angle. Please mark those which assisted you. $\endgroup$
    – Royi
    Apr 28, 2020 at 5:21
  • $\begingroup$ We set the the first value of $h$ which is $h_i^0$ as known, is that right ? $\endgroup$
    – Gze
    May 1, 2020 at 18:04
  • $\begingroup$ Yep. You can set it uniformly. $\endgroup$
    – Royi
    May 1, 2020 at 18:18
  • $\begingroup$ 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 ? $\endgroup$
    – Gze
    May 2, 2020 at 20:48
2
$\begingroup$

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.
In addition, you need to re-write your sensing equation with a matrix-vector product instead of the convolution as explained in my answer.
Notice that you will not be able to successfully under-sample by more than a factor ½ with this interpretation of the problem - see (Donoho & Tanner, 2010 - Precise Undersampling Theorems ), page 5, Fig. 3.

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.

Finally, a third solution I came to think of is (Yaghoobi, Blumensath, Davies, 2007, Quantized Sparse Approximation with Iterative Thresholding for Audio Coding - DOI). In this framework, your case corresponds to having two quantisation levels; 0 and your known amplitude. The philosophy here is a bit similar to (Nagahara, 2015), but the algorithm is a greedy thresholding algorithm as opposed to the convex optimisation approach in (Nagahara, 2015).

I do not know which of these approaches would work best for your case.

$\endgroup$
19
  • $\begingroup$ 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. $\endgroup$
    – Gze
    Apr 23, 2020 at 11:27
  • 1
    $\begingroup$ Please, when you link to papers, write their titles. One day the link won't be available yet the search will always work :-). $\endgroup$
    – Royi
    Apr 23, 2020 at 19:42
  • $\begingroup$ @Royi I'm trying to explore this idea too, but I still didn't understand it well. Awaiting for Mr. Thomas if he can provide more details about it. $\endgroup$
    – Gze
    Apr 24, 2020 at 7:24
  • $\begingroup$ @Royi good point. It's a reflex from writing research papers 😓 $\endgroup$ Apr 24, 2020 at 13:42
  • 1
    $\begingroup$ Any of the approaches you added assume known $ h $? $\endgroup$
    – Royi
    Apr 25, 2020 at 22:33

Your Answer

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

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