The size of the set \(W\), a number that we call \(M\), is the number of matrix elements of \(B\) that are sampled. \(M\) determines the quality of the reconstruction of \(A\).  From compressed sensing theory we can find a lower bound for \(M\) as a function of the sparsity of \(A\) and the change-of-basis transformation.

One important requirement for compressed sensing is that the sparse basis \(\{\psi_i\}\) for \(A\) and the measurement basis \(\{\phi_i\}\) for \(B\) should be \textit{incoherent}, meaning that the maximum overlap between any vector in \(\{\psi_i\}\) and any vector in \(\{\phi_i\}\)
\begin{equation}
\label{eq:coherence}
\mu = \sqrt{N} \max_{i,j} \langle \psi_i | \phi_j \rangle
\end{equation}
should be as \emph{small} as possible (in general \(\mu\) ranges from 1 to \(\sqrt{N}\)).  Intuitively, this incoherence condition means that the change-of-basis matrix \(P\) should thoroughly scramble the entries of \(A\) to generate \(B\). 

It can be proven~\cite{Candes2008} that the number of entries of \(B\) which must be measured in order to fully recover \(A\) by solving the BP problem in eq.~\ref{eq:bpdn} scales as
%
\begin{equation}
\label{eq:csscaling}
M \propto \mu^2 S \log N^2\ .
\end{equation}
%
This scaling equation encapsulates the important aspect of compressed sensing: if a proper measurement basis is chosen, the number of entries which must be measured scales linearly with the sparsity of the matrix and only depends weakly on the full size of the matrix. For the remainder of this paper, we always choose our measurement basis vectors to be the discrete cosine transform (DCT) of the sparse basis vectors, for which the parameter \(\mu\) is equal to \(\sqrt{2}\).

In order to study the numerical properties of the reconstruction method we performed a series of numerical experiments. We generate \(100 \times 100\) matrices of varying sparsity with random values drawn uniformly from the interval \([-1,1]\) and places in random locations in the matrix. Matrix elements were then sampled in the DCT measurement basis, and an attempt was made to recover the original sparse matrix by solving the compressed sensing basis pursuit problem in eq.~\ref{eq:bpdn}.

Fig.~\ref{fig:NumericsResults} illustrates the percent of matrix elements had to be sampled for accurate recovery of the sparse matrix compared with other recovery approaches. If no prior knowledge of a matrix is used for its recovery, then one simply measures each entry; this is the current paradigm in many scientific applications.  If one knows exactly where the non-zeros in a sparse matrix are located, one can simply measure those elements. Compressed sensing interpolates between these two extremes: it provides a method for recovering a sparse matrix when the locations of the non-zeros are not known in advance. Although this lack of knowledge comes with a cost, the recovery  is still consideably cheaper than measuring the entire matrix.