Jacob Sanders edited Numerical Foundation 2.tex  over 9 years ago

Commit id: de3307597c7ec23c5a5f60d3dd9a4a7594ecc189

deletions | additions      

       

\end{align}  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. 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. The parameter \(mu\) associated with the DCT is equal to \(\sqrt{2}\), near the lower end of the 1 to \(\sqrt{N}\) range desired for incoherent sampling.  Fig.~\ref{fig:NumericsResults} illustrates the potential advantages of the compressed sensing procedure we have outlined above. Square matrices (\(100 \times 100\)) of varying sparsity were generated with non-zeros in random locations drawn uniformly from the interval \([-1,1]\). 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}. The figure illustrates the percent of matrix elements had to be sampled for accurate recovery of the sparse matrix (relative Frobenius norm error \(\lt 10^-7\)). 10^{-7}\)).  As expected, number of matrix elements which must be sampled in the measurement basis increases as the matrix becomes less sparse in the sparse basis. Fig.~\ref{fig:NumericsResults} also compares compressed sensing to other recovery approaches. If no prior knowledge of a matrix is used for its recovery, then one simply measures each entry individually (horizontal line at the top); 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 (diagonal line). 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 much cheaper than measuring the entire matrix.