I have a sparse vector $x \in \mathbb{R}^{N \times 1}$, it's real and positive, the non-zeros values are maximum $N/2$ values. It means, I have at least $N/2$ zeros values in $x$.

My question, is it possible to build a measurement matrix $M$ with dimension $N/2 \times N$ as measurement matrix, where the dimension of the vector $x$ can be reduced into $N/2 \times 1$ real-positive values too?

How can I generate the matrix $M$ such that $M \times x = y$? The indices of non-zeros values in $x$ are not well-known; what is known that at least $N/2$ zeros values are existed in $x$. Is that feasible? what's the process to do that, I mean with which compressive sensing technique I can handle that problem?

  • $\begingroup$ In the preamble you say $x \in \mathbb{R}^{N \times 1}$ and then later you say $x \in \mathbb{R}$. Do you really mean $x$ is as in the preamble and $y \in \mathbb{R}^{N/2 \times 1}$? Do you know something about the non-zero $x$ indices? If so, $\mathbf{M}$ is just a matrix with mostly zeros and ones where the measurement is extracted from $x$. $\endgroup$
    – Peter K.
    Jun 4, 2022 at 21:11
  • $\begingroup$ @PeterK. yes, I mean $x \in \mathbb{R}^{N \times 1}$ and $y \in \mathbb{R}^{N/2 \times 1}$. The non-zeros $x$ indices are changing randomly, their positions are not well-known but what I am sure of is that at least $N/2$-zeros are exist. (I update the questions following your notice too) $\endgroup$
    – Sajjad
    Jun 4, 2022 at 22:25

1 Answer 1


For the specific realization of this specific $ \boldsymbol{x} $ you can easily chose the subset of columns matching the indices of the non zero elements of $ \boldsymbol{x} $.

Yet remember that the model matrix should handle multiple realizations of the signals. Hence it is usually a "fat" matrix.
So different signals can use different atoms (Columns).


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.