Suppose I want to measure a signal $x \in \mathbb{R}^n$ subject to i.i.d. noise $\epsilon$. In traditional Nyquist Sampling, I can increase my signal-to-noise ratio by measuring $x + \epsilon$ for $k$ times and averaging over the measurements.

$$\overline{x} = \frac{1}{K}\sum_{k=1}^{K}{(x +\epsilon_k)}$$

Instead of $x$ i now have $k$ compressed measurements $y \in \mathbb{R}^m$ and their corresponding k differing measurement matrices $\Psi \in \mathbb{R}^{m*n}$ with $m<n$, that contain e.g. gaussian random entries so that $y = \Psi*(x+\epsilon_k)$. Assuming $x$ is sufficiently sparse so that reconstruction via $l_1$-Norm minimization is possible.

Can I also improve my SNR in the second case?

  1. What are the noise implications if I reconstruct each of the $k$ measurement pairs $(y,\Psi)$ and take the average of the reconstructed signals?

  2. What will be the noise implications of taking the average of all measurements $\overline{y}$ and $\overline{\Psi}$ and recover the signal from the single pair?

  • $\begingroup$ In your first, classic sampling equation, do you perhaps mean that all $K$ samples $x_k$ are in fact identical $x_k = x, \forall k$ and it is the noise realisations $\epsilon$ that actually differ over $k$? I mean: $$\bar x = \frac1K \sum_{k=1}^K (x + \epsilon_k)$$ $\endgroup$ Aug 22, 2019 at 6:40
  • $\begingroup$ yes that's true, I corrected it $\endgroup$
    – Mr Vinagi
    Aug 22, 2019 at 9:04
  • $\begingroup$ Do you know how sparse $ x $ should be? $\endgroup$
    – Royi
    Aug 23, 2019 at 11:28
  • $\begingroup$ Yes, in my case I can assume, that the sparsity is known. $\endgroup$
    – Mr Vinagi
    Aug 26, 2019 at 8:40

1 Answer 1


If you have $k$ individual measured vectors $\mathbf y$, each taken with an individual measurement matrix $\mathbf \Psi$, you actually have an interesting, third option: $$\mathbf y = \begin{bmatrix} \mathbf y_1 \newline \vdots \newline \mathbf y_k \newline \vdots \newline \mathbf{y}_K \end{bmatrix} = \begin{bmatrix} \mathbf \Psi_1 \newline \vdots \newline \mathbf \Psi_k \newline \vdots \newline \mathbf \Psi_K \end{bmatrix} \mathbf x$$ So now you effectively have a (much) taller measurement matrix, so you are effectively "under-sampling less" and that will improve your estimate $\mathbf x$ based on the above equation. How much, I cannot recall an expression for off the top of my head.

Note also that you may have a tall measurement matrix now due to the stacking of the $\mathbf \Psi_k$'s. That is, you do not necessarily have an under-determined system anymore. This gives you the option of for example using least-squares estimation instead of $\ell_1$-norm optimisation. If you know that $\mathbf x$ is sparse, then it still makes sense to use sparse estimation ($\ell_1$-norm optimisation etc.), but if $\mathbf x$ is only approximately sparse, compressible then I would try least squares estimation as well.

  • $\begingroup$ Ah very interesting. So given $m*k \geq n$ least squares is the smartest way to go $\endgroup$
    – Mr Vinagi
    Aug 22, 2019 at 10:05
  • $\begingroup$ I would say I am not sure. It should be possible to get a good estimate from least squares in that situation and it is computationally cheaper. But, if you know your estimate has to be truly sparse and any deviation from that should be considered an estimation error, then least squares cannot enforce that for you. $\endgroup$ Aug 22, 2019 at 18:40
  • $\begingroup$ Nice answer, +1. Though I think that i the original model is Sparse one must add Sparse Regularization into the Matrix Form of the problem you formed. $\endgroup$
    – Royi
    Aug 23, 2019 at 11:29

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.