Given a non-invertible matrix $X \in \mathbb{R}$, let's say that matrix is, e.g. :

$X = \begin{bmatrix} 0.7500& -0.2500 &-0.2500 & -0.2500 \\ -0.2500& 0.7500& -0.2500 & -0.2500\\ -0.2500& -0.2500 & 0.7500& -0.2500\\ -0.2500& -0.2500& -0.2500& 0.7500 \end{bmatrix}$

The matrix $X$ is multiplied with sparse vector $s \in \mathbb{R} $ resulting a vector, called $y = Xs$, we assume the sparsity is known, it means the number of non-zeros elements are known in $s$, let's say we have two non-zeros values in $s$. For example $s = \begin{bmatrix} 0\\ 1\\ -1\\ 0 \end{bmatrix}$. The elements of non-zeros elements are either $1$ or $-1$ but their locations are random. (It means the values of the non-zeros elements belong to known sets, e.g. they are $1$ or $-1$ or $3$ or $-3$)

My question, is it possible to detect the vector $s$ based on $y$ ?

NP : I made the vector $s$ sparse since it's not possible to detect it if it's not sparse. So, in case of the sparsity, I am wondering if we can detect it using compressive sensing or any other algorithm?


1 Answer 1


Answering your verbatim question

My question, is it possible to detect the vector s based on y ?

Yes, it is possible.

This can be shown by considering that there's only 6 ways of picking your non-zero entries, and 4 possible data symbols in these, so 24 possible symbols in total.

A computer can easily precompute these 24 possible symbols. If you have two identical symbols that have different data, these cannot be unambigously detected, when you think about it. (The fact that the matrix isn't invertible doesn't mean it's not invertible on every subset of its image, be sure you actually have a problem you're solving here.)

Hence, your detector just needs to calculate the "right" receive symbol by comparing these 24 precomputed candidates with your receive word. You don't specify any noise, so you're done here – just pick the identical precomputed value.


Noise will make your $y$ look different than the perfect transmit vectors.

Often, you'd want to do a maximum likelihood detection, which incorporates your channel and especially your noise model and calculates the most likely value – often, that boils down to a minimum distance calculation.

calculating 24 distances and selecting the minimum is trivial effort for detection.

Addressing the larger context

For larger problems, i.e. larger vectors or larger alphabets, such a list decoder becomes infeasible. You'd then typically just realize that this is just channel coding (albeit not very good channel coding), and apply appropriate decoding after using some useful algorithm to select symbols and non-zero indices.

However, there's really no reason a decoder for your scheme needs to remain infeasible, even for large vectors; after all, this sounds very iteratively decodable; your code space will never be very complex in nature!

  • $\begingroup$ Yes, I ignored the noise and the case of larger vector for the moment. But, what's about if two different vectors $s_i$ have same output $y$? for example in our example, $s_1 = \begin{bmatrix} 1\\ 1\\ 0\\ 0 \end{bmatrix}$ and $s_2 = \begin{bmatrix} 0\\ 0\\ -1\\ -1 \end{bmatrix}$. $\endgroup$
    – Sajjad
    Oct 11, 2021 at 1:20
  • $\begingroup$ For that, I am asking if there is such algorithm which allows to detect the locations of zeros first. It means doesn't jointly detecting the zeros and non-zeros values. $\endgroup$
    – Sajjad
    Oct 11, 2021 at 1:38
  • $\begingroup$ @Sajjad I explicitly addressed that case: if two $s_i$ have the same $y$, then no unambgious decoding is possible – how would it, logically? It's the same observation. It doesn't matter what you do with it. $\endgroup$ Oct 11, 2021 at 6:12

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.