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

Question

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?

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

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!