Xavier Andrade edited Numerical Foundation 2.tex  over 9 years ago

Commit id: 4c0c351da5c8b8d63dcdf64464f1035725c9ae58

deletions | additions      

       

\label{eq:csscaling}  M \propto \mu^2 S \log N^2\ .  \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\) \(\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 In order to study  the potential advantages numerical properties  of the compressed sensing procedure reconstruction method  we have outlined above. performed a series of numerical experiments.  Square matrices (\(100 \times 100\)) of varying sparsity were generated withnon-zeros in  random locations values  drawn uniformly from the interval \([-1,1]\). \([-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}.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}\)). 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 illustrates the percent of matrix elements had  to be sampled for accurate recovery of the sparse matrix (relative Frobenius norm error \(\lt 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 figure we compare with  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.