quantify accuracy, then the recovery problem can be expressed as finding the function $\theta$ of the measurements $y$ minimizing the (worst case) approximation error $\inf_{\theta}\sup_{\|b\|\leq 1} \|x - \theta(y)\|_A/\|b\|$ with $x=A^{-1}b$ and $y=\Phi A^{-1} b$. Writing $0<\lambda_1(A)\leq \cdots \leq \lambda_n(A)$, the eigenvalues of $A$ in increasing order, and $a_1,\ldots,a_n$, the corresponding eigenvectors, it is easy to obtain that (1) the best choice for $\Phi$ would correspond to measuring the projection of $x$ on $\operatorname{span}\{a_1,\ldots,a_m\}$ and would lead to the worst approximation error $1/\sqrt{\lambda_{m+1}}$ and (2) the worst choice would correspond to measuring the projection of $x$ on a subspace orthogonal to $a_1$ and would lead to the worst approximation error $1/\sqrt{\lambda_{1}}$. Under the decision $Q=A$ the minimal value of is also $1/\sqrt{\lambda_{m+1}}$ and achieved for $\Img(\Phi^T)=\operatorname{span}\{a_1,\ldots,a_m\}$ and the maximal value of is $1/\sqrt{\lambda_{1}}$ and achieved when $\Img(\Phi^T)$ is orthogonal to $a_1$. The following theorem, which is a direct application of and the estimate derived in [@HalkoMartinssonTropp:2011 p. 10] (see also [@MartinssonRokhlinTygert:2011]), shows that, the subset of measurement matrices that are not *nearly optimal* is of small measure if the rows of $\Phi^T$ are sampled independently on the unit sphere of $\R^n$.

\[thm:duihdi3dw\] If $\Phi$ is a $n\times m$ matrix with 