# Number of trials to judge performance of Compressive Sensing recovery algorithms

I'm trying to get a conclusive numerical value for Mean Squared Error (MSE) as the performance metric of a few CS sparse recovery algorithms. To do this, I vary the number of measurements ($M$) taken from an $N$-dimensional vector with $M\ll N$ using the sensing matrix $\mathbf A \in \mathbb K^{M\times N}$. The goal is to find the MSE at each $M$.

At the moment, randomly generated sparse signals are sensed using random sensing matrices ($\mathbf A$), leading to $M$ measurements from which the original sparse vectors are then recovered. For each $M$, I generate 30 sensing matrices and 30 signals for each $\mathbf A$. This totals 900 trials for a single $M$. I first find the difference between the original and reconstructed signal. Then I find the $l_2$ norm of the difference (error) vector. This value is found for all trials for a single value of $M$, then squared and averaged to find the MSE at that value of $M$.

I am curious if there is a lower limit to the number of trials I should perform for each MM so that I get a conclusive value of MSE? How do I defend against a person who says I should do more?

Kindly point me to the appropriate forum if the question is not relevant to this domain.

• The $l_2$ norm of error is not a suitable metric for this task. If $A$ is selected from a sub-Gaussian density, then all $s$-sparse vectors can be reconstructed, provided that the number of measurements is greater that $Ks\log(N/s)$, where K is a constant, independent of $N,s$ and $M$. – msm Dec 18 '16 at 10:23
• @msm Could you please elaborate on that? My thinking was that the Restrictred Isometry Property would allow considerable separation between two s-sparse signals in the $\ell_2$ norm of their difference. – user25397 Dec 18 '16 at 12:32
• The reason is $l_2$ norm is the least effected by the sparsity constraint. So you would instead look at the $l_1$ norm. – msm Dec 18 '16 at 22:03