# Is it possible to detect the sparse vector based on a non-invertible matrix

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?

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

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.

• 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}$. Oct 11, 2021 at 1:20
• @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. Oct 11, 2021 at 6:12